Privacy Preserving Solution of DCOPs by Local Search

1 Introduction

The Distributed Constraint Optimization Problem (DCOP) is a general model for solving distributed combinatorial problems that has a wide range of applications in artificial intelligence. Complete algorithms for DCOP-solving [Modi et al., 2005; Petcu and Faltings, 2005; Gershman et al., 2009] are guaranteed to find the optimal solution, but because DCOPs are NP-hard, these algorithms' worst-case runtime is exponential. Thus, there is a growing interest in incomplete algorithms, which may find sub-optimal solutions but run quickly enough to be applied on large-scale problems or real-time applications [Maheswaran et al., 2004; Zhang et al., 2005; Teacy et al., 2008; Zivan et al., 2014].

Approaches of incomplete DCOP algorithms include inference (Max-Sum [Farinelli et al., 2008]), sampling (DUCT [Ottens et al., 2017], D-Gibbs [Nguyen et al., 2019]), region optimal (KOPT [Katagishi and Pearce,

2007], DALO [Kiekintveld et al., 2010]), and local search (DSA [Zhang et al., 2005], MGM [Maheswaran et al., 2004], and DBA [Hirayama and Yokoo, 2005]). The latter approach is extremely popular due to its simplicity and runtime efficiency.

Privacy is one of the main motivations for solving constraint problems in a distributed manner. Preserving privacy is most important in distributed scenarios in which agents represent people who would not like their personal preferences and actions to be revealed, e.g., meeting scheduling [Gershman et al., 2008], and smart environments (such as smart homes) [Rust et al., 2016; Fioretto et al., 2017]. The term privacy is quite broad, a fact that gave rise to several categorizations of the different types of privacy [L´eaut´e and Faltings, 2013; Greenstadt et al., 2007; Grinshpoun, 2012]. In this paper, we relate to the categorization of L´eaut´e and Faltings [2013] that distinguishes between agent privacy, topology privacy, constraint privacy, and decision privacy.

Most studies that evaluated distributed constraint algorithms in terms of privacy considered complete algorithms [Silaghi and Mitra, 2004; Maheswaran et al., 2006; Greenstadt et al., 2006; Doshi et al., 2008; L´eaut´e and Faltings, 2013; Grinshpoun and Tassa, 2016]. Some work has focused on measuring the extent of constraint privacy loss [Maheswaran et al., 2006; Greenstadt et al., 2006]. Doshi et al. [2008] proposed to inject privacy loss as a criterion to the problem-solving process. Some previous work was also directed towards reducing constraint privacy loss. Most efforts in the development of privacy-preserving search algorithms focused on DCSP, which is the satisfaction variant of DCOP. Examples include [Nissim and Zivan, 2005; Silaghi and Mitra, 2004; Yokoo et al., 2005]. The work of Silaghi and Mitra [2004] addressed both satisfaction and optimization problems. However, the proposed solution is strictly limited to small-scale problems since it depends on an exhaustive search of all possible assignments. Several privacypreserving versions of the DPOP algorithm [Petcu and Faltings, 2005] were proposed in the past [Greenstadt et al., 2007; Silaghi et al., 2006], including a more recent study by L´eaut´e and Faltings [2013] that proposed several versions of DPOP that provide strong privacy guarantees. While these versions have been designed for DCSPs, some of them may also be applicable to DCOPs. Explicitly for DCOPs, Grinshpoun and Tassa [2016] and Tassa et al. [2021] devised variants of SyncBB [Hirayama and Yokoo, 1997], which preserve topology, constraint, and decision privacy.

While the problem sizes for which complete DCOP algorithms are applicable are limited, the problem worsens when privacy-preserving algorithms are considered, due to the substantial runtime overhead that privacy preservation incurs. Consequently, several studies focused on privacypreserving incomplete algorithms. Tassa et al. [2017] and Kogan et al. [2023] proposed variations of an incomplete inference algorithm, Max-Sum [Farinelli et al., 2008], which preserve topology, constraint, and decision privacy. Additionally, Grinshpoun et al. [2019] devised an incomplete regionoptimal algorithm that preserves constraint privacy and partial decision privacy. However, though incomplete, the above algorithms are very elaborate and are inapplicable to largescale problems. Specifically, the runtime of the Max-Sumbased algorithms is exponential in the arity of the constraints, which makes them unsuitable for problems with global constraints, e.g., satellite scheduling [Krigman et al., 2024] and course allocation [Khakhiashvili et al., 2021].

Recently, Vion et al. [2022] proposed a local search algorithm that controls the loss of domain privacy [Grinshpoun, 2012] by following the Utilitarian DCOP model [Doshi et al., 2008; Savaux et al., 2020], in which privacy loss is traded off with solution quality. However, their approach is only relevant in the Open Constraints Programming model [Faltings and Macho-Gonzalez, 2005], where the domains are not known in advance and grow as the solving process advances.

Our contributions. We present here P-DSA, a privacypreserving implementation of the classical local-search algorithm DSA. We show that it offers topology privacy, constraint privacy, and assignment/decision privacy. We compare its performance to that of P-Max-Sum [Tassa et al., 2017], a privacy-preserving implementation of the incomplete DCOP algorithm Max-Sum [Farinelli et al., 2008] which also protects topology, constraint and assignment/decision information. We show that P-DSA is significantly more scalable and issues much better solutions than P-Max-Sum. In fact, while P-DSA was able to solve in short time (3 minutes) problems involving as high as 100 agents, prior studies on privacypreserving DCOP algorithms report experiments with at most 24 agents and runtimes that are significantly higher. 1 Therefore, P-DSA emerges as a suitable choice for solving largescale DCOPs in a privacy-preserving manner.

2 DCOP background

A Distributed Constraint Optimization Problem (DCOP, [Hirayama and Yokoo, 1997]) is a tuple ⟨A,X,D,R⟩ where A = {A1, . . . ,An} is a set of agents, X = {X1, . . . ,Xn} is a set of variables, D = {D1, . . . ,Dn} is a set of finite domains, and R is a set of relations (constraints). Each variable Xi takes values in the domain Di, and it is held by the agent Ai. Each constraint C ∈ R defines for a given pair of variables some non-negative cost; formally, a constraint takes the formCi,j : Di×Dj → [0, q], for some 1 ≤ i ≤ j ≤ n, where q is a publicly known maximal constraint cost q. (Note that if i = j then the constraint is unary.) The goal in constraint optimization problems is to find an assignment of values to all n variables,

1 To the best of our knowledge, the only exception is the work of Damle et al. [2024] that presented P-Gibbs, which is a differentially private implementation of SD-Gibbs [Nguyen et al., 2019]. However, differential privacy is a paradigm that is based on injecting random noise; hence it is not directly comparable to the cryptographic paradigm that does not alter the outputs of the underlying algorithm.

such that the overall incurred cost ∑Ci,j∈R Ci,j(xi, xj) is minimal.

Our framework can also include the case of hard constraints, i.e., combinations of assignments that are strictly forbidden, see [Kumar et al., 2008]. Our framework is the one that is studied in most prior art. Some studies consider extensions to this framework by (a) assuming that each agent may hold more than one variable [Yokoo and Hirayama, 2000; Burke and Brown, 2006; Grinshpoun, 2015; Fioretto et al., 2016], (b) including constraints of arity greater than two [Kim and Lesser, 2013], and (c) assuming asymmetric constraints that incur different costs to each of the involved agents [Grinshpoun et al., 2013]. However, here we focus on the framework as defined above, which already introduces the main challenges of DCOPs.

L´eaut´e and Faltings [2013] distinguished between four notions of privacy: agent privacy (who are the agents in the problem setting), topology privacy (hiding information on the constraint graph), constraint privacy (hiding information on the costs in the constraints), and assignment/decision privacy (protecting the intermediate/final assignments).

2.1 The Distributed Stochastic Algorithm

Here we describe the classic local search DCOP algorithm that was presented by Zhang et al. [2005] - the Distributed Stochastic Algorithm (DSA). We start by introducing a key notion in local search algorithms:

Definition 1 (Neighborhood). The neighborhood of agent Ai is the set of all agents that are constrained with Ai, i.e., N(Ai) := {Aj ∈ A : ∃Ci,j ∈ R}. The complete neighborhood of Ai is N +(Ai) := N(Ai) ∪ {Ai}.

Algorithm 1: The DSA algorithm

1 forall i ∈ [n] do 2 Ai selects at random xi ∈ Di 3 forall ℓ = 1, . . . ,L do 4 forall i ∈ [n] do 5 Ai sends xi to all Aj ∈ N(Ai) 6 forall i ∈ [n] do 7 Ai samples uniformly at random a real x ∈ [0, 1] 8 if x ≤ p then 9 Ai chooses yi ∈ Di that minimizes ∑Aj ∈N(Ai) Ci,j (yi, xj ) 10 Ai updates xi ← yi

Algorithm 1 describes DSA. The algorithm starts by generating an initial random assignment a ∈ D (Lines 1-2). 2 It then keeps updating that assignment by performing a preset number of iterations L (Lines 3-10). The assignment in the final iteration is the algorithm's output. Each iteration starts with each agent updating its neighbors on its current assignment (Lines 4-5). Then, each agent is allowed, with probability p, to change its local assignment to the best possible value (Lines 6-10).

The utilization of the stochastic factor p enables DSA to escape local minima and avoid infinite loops. However, it renders DSA non-monotone in the sense that the cost of the solution in one iteration is not necessarily smaller than the cost of the solution in the previous iteration. It is possible to enhance DSA with a so-called anytime mechanism [Zivan et al., 2014]. Such a mechanism finds the best solution visited throughout the run of the algorithm. In general, in order to report the best solution visited, the algorithm needs to compute the overall cost after each iteration, and if that overall cost is the minimum so far, record that cost and the corresponding assignment.

3 Cryptographic background

Here, we briefly describe the cryptographic machinery we use in our protocols. In Section 3.1 we discuss threshold secret sharing, and then, in Section 3.2, we describe secure computations over secret-shared values.

3.1 Shamir's secret sharing

Secret sharing schemes [Shamir, 1979] are protocols that enable distributing a secret scalar s among a set of agents, A1, . . . ,An. Each agent, Ah, h ∈ [n], gets a random value [[s]]h, called a share, so that some subsets of those shares enable the reconstruction of s, while each of the other subsets of shares reveals no information on s. In its most basic form, called Threshold Secret Sharing, there is a threshold value t ≤ n, and then a subset of shares enables the reconstruction of s iff its size is at least t.

Shamir's t-out-of-n threshold secret sharing scheme [Shamir, 1979] operates over a finite field Zq, where q > n is a prime sufficiently large so that all possible secrets may be represented in Zq. It has two procedures: Share and Reconstruct:

• Sharet,n(s). The procedure samples a uniformly random polynomial f(·) over Zq, of degree at most t - 1, where the free coefficient is the secret s. That is, f(x) = s + a1x + a2x2 +. . .+at-1xt-1 , where aj , 1 ≤ j ≤ t-1, are selected independently and uniformly at random from Zq. The procedure outputs n values, [[s]]h = f(h), h ∈ [n], where [[s]]h is the share given to Ah. The entire set of sheares, denoted [[s]] := {[[s]]h : h ∈ [n]}, is called a (t, n)-sharing of s.

· Reconstructt([[s]]). The procedure is given any selection of t shares out of the (t, n)-sharing of s. It then interpolates a polynomial f(·) of degree at most t-1 using the given points and outputs s = f(0). Any selection of t shares will yield the secret s, as t points determine a unique polynomial of degree at most t-1. On the other hand, any selection of t-1 shares or less reveals nothing about the secret s.

2 Throughout this paper, for any integer n, [n] := {1, . . . , n}.

Hereinafter, we set the secret sharing threshold to be

Namely, to reconstruct the secret, at least half of the agents must collaborate. Hence, if the set of n agents has an honest majority (in the sense that more than n/2 agents would not try to combine their shares in order to recover secret values), all shared values will remain fully protected.

In what follows, we shall use the following terminology and notations. Let s be a secret known to some agent Ai, i ∈ [n]. Then if Ai performs the procedure Sharet,n(s), we will simply say that Ai distributes a (t, n)-sharing of s.

If the agents have a (t, n)-sharing [[s]] in some secret s and they wish to let one of them, say Ai, reconstruct the secret s, then at least t - 1 agents would send their shares to Ai who will proceed to apply the Reconstruct procedure on the t shares it has. We will describe this procedure shortly by writing s ← Reconstruct([[s]]; Ai).

If s = (s1, . . . , sm) ∈ Zmq is a vector of secrets held by Ai, then by saying that Ai distributes a (t, n)-sharing of s we mean that Ai distributes a (t, n)-sharing of each of the entries of s, independently.

Let a ∈ Zq be any value that is publicly known to all agents. Then by [[a]] we mean the set of (t, n)-shares {[[a]]h = a : h ∈ [n]}. It is easy to see that this set of shares indeed defines a unique polynomial of degree at most t - 1, which is the constant polynomial f(·) ≡ a, and therefore it is a proper (t, n)-sharing of the value a. Such a sharing does not require any communication between the agents nor any polynomial computations, since a is publicly known.

Let a, b, c ∈ Zq be three values publicly known to all, and let s and s′ be two secrets in which the agents already hold (t, n)-sharings, denoted [[s]] and [[s′ ]]. Then

is a proper (t, n)-sharing of ˆ s := a+bs+cs′ , and its computation needs no interaction between the agents, thanks to the affinity of secret sharing. By writing

we mean that each agent Ah, h ∈ [n], sets [[ˆ s]]h ← a + b[[s]]h + c[[s′ ]]h, so that now the agents hold a (t, n)-sharing of ˆ s = a + bs + cs′ without needing to interact or perform any further polynomial computations.

3.2 Secure computations over secret sharings

Let a and b be two secret values in the field Zq, and assume that A1, . . . , An hold (t, n)-sharings in them, denoted [[a]] = {[[a]]h : h ∈ [n]} and [[b]] = {[[b]]h : h ∈ [n]}. A secure multiplication protocol is a protocol of the form

that takes the (t, n)-sharings of a and b and computes from them a (t, n)-sharing of c = a · b in a secure manner, namely, without revealing to the agents any information on a, b, or c = ab. Damg˚ard and Nielsen [2007] designed such a secure multiplication protocol. In our experiments, we used that protocol with the performance improvements that were proposed by Chida et al. [2018].

Another computation on secret shares that we will need is secure comparison. Under the same assumptions as above, a secure comparison protocol is a protocol of the form

that takes the (t, n)-sharings of a and b and computes from them a (t, n)-sharing of c = 1a<b, where hereinafter if P is a predicate then 1P is a bit that equals 1 if the predicate P holds and equals 0 otherwise. As before, such a protocol is secure in the sense that it does not reveal to the agents any information on a, b, or c = 1a<b. Nishide and Ohta [2007] proposed such a secure comparison protocol.

4 Private DSA

In this section, we describe Private DSA (P-DSA), an implementation of DSA that preserves topology, constraint, and decision privacy. In order to achieve those privacy goals, PDSA employs the following principles:

1. To achieve topology privacy, every pair of agents that are not constrained creates a zero constraint matrix between themselves, and, subsequently, the algorithm acts on a complete constraint graph. None of the other agents is able to distinguish between fake constraint matrices (i.e., zero matrices) and genuine ones due to the next principle in P-DSA's design, which distinguishes its operation from that of the basic DSA.
2. To achieve constraint privacy, all constraint matrices are secret-shared among all agents, and all computations that rely on those matrices use the shares rather than the actual constraint matrices.
3. To achieve decision privacy, in each iteration of the algorithm whenever an agent selects an assignment to its variable, it does not send that assignment to its neighbors; instead, it secret shares information on the costs that such an assignment incurs vis-a-vis each of the other agents.

The latter principle raises a considerable computational challenge: how can each of the agents perform the computations that DSA mandates when it does not know the current assignments of its neighboring agents? We tackle that challenge by designing multi-party sub-protocols to be run jointly by all agents. In those collaborative sub-protocols, all agents use the secret shares they hold in order to enable each agent to compute the next assignment from its domain. In doing so, none of the agents get any wiser about that assignment or any other private information.

We assume hereinafter that all agents know the sizes of all domains, namely, mi := |Di| for all i ∈ [n]. Moreover, each agent Ai, i ∈ [n], generates an ordering of the values in its domain, Di = {ai1 , . . . , aimi }, and publishes that ordering to each of its neighbors, Aj ∈ N(Ai). Therefore, each constraint Ci,j can be described as a matrix of mi rows and mj columns, where Ci,j(r, s) equals the value of the constraint when Xi = air and Xj = ajs . In what follows, we will think of Ci,j as a matrix rather than a function over Di ×Dj .

Protocol 2 describes P-DSA - a private implementation of DSA. First, each agent Ai selects a random assignment to its variable. Ai does that by selecting a random index ri ∈ [mi], and then the corresponding assignment to Xi is airi , i ∈ [n] (Lines 1-2).

The main loop takes place in Lines 3-15. First, each agent Ai, i ∈ [n], secretly shares its current assignment, airi , with all agents. To do that, Ai distributes to all agents (t, n)-shares in the ri-th row in each of the constraint matrices that it has vis-a-vis each of the other n - 1 agents (namely, also with agents outside its neighborhood). Let wi,j denote the ri-th row in the constraint matrix Ci,j , for some j ∈ [n] \ {i}, i.e.,

Ai distributes (t, n)-shares in each of the mj entries of that vector, where the sharing of wi,j(u) is denoted [[wi,j(u)]] = {[[wi,j(u)]]h : h ∈ [n]}, while the sharing of the entire vector is denoted [[wi,j]]. The overall number of scalars that Ai shares at this stage (Lines 4-6) is ∑j∈[n]\{i} mj.

We would like to clarify that the secret sharing done in Lines 4-6 is excessive. Indeed, if a ̸= b ∈ [n] then the scalar Ca,b(ra, rb) is shared when i = a and j = b, as it is in the rath row of the matrix Ca,b, but also when i = b and j = a, as it is in the rb-th row of the matrix Cb,a which is the transpose of Ca,b. However, this excessive secret sharing will pay off later on in the computation.

Before moving on, let us fix i ∈ [n] and j ∈ [n] \ {i}. Then for any u ∈ [mi], wj,i(u) is the cost that Ai would pay if it sets Xi = aiu , given the current assignment of Aj to its variable, Xj = ajrj . Therefore, if we define

we have by Eq. (5) and the symmetry of the constraints (in the sense that Ci,j = C T j,i ),

Hence, wi(u) is the overall cost for Ai if it sets Xi = aiu , given the current assignments that all other agents have for their variables. In Lines 7-9 all agents compute (t, n)-shares in wi(u) for all i ∈ [n] and for all u ∈ [mi]. Note that it is a local computation that does not require the agents to communicate.

Next, the main task of each agent Ai is to find the best assignment to its variable given the current assignments of all neighboring variables (as encoded in the secret shares that all agents have distributed in Lines 4-6) and storing the index of that assignment in ri. However, we recall that such a computation takes place only in probability p, while otherwise, in probability 1 - p, Ai retains its current assignment. Hence, Ai starts by generating a uniformly random real number x ∈ [0, 1] (Line 11), and only if x ≤ p it proceeds to the computational task of finding the best assignment for its variable, given the current assignments of its neighboring agents. That computation is carried out in the subprotocol FindBestAssignment (Line 13). In that sub-protocol, the agents jointly and securely compute a (t, n)-sharing of the index ki ∈ [mi] of the currently best assignment to Xi from Di. After its completion, all agents send to Ai their shares in ki, and Ai proceeds to recover ki (Line 14) and store it in ri (Line 15).

After performing L such iterations (Lines 3-15), each of the agents stores the last assignment to its variable (Lines 1617).

Protocol 2: P-DSA - Private DSA

1 forall i ∈ [n] do 2 Ai selects at random ri ∈ [mi] 3 forall ℓ = 1, . . . ,L do 4 forall i ∈ [n] do 5 forall j ∈ [n] \ {i} do 6 Ai distributes a (t, n)-sharing of [[wi,j]] 7 forall i ∈ [n] do 8 forall u ∈ [mi] do 9 [[wi(u)]] ← ∑j∈[n]\{i} [[wj,i(u)]] 10 forall i ∈ [n] do 11 Ai samples uniformly at random x ∈ [0, 1] 12 if x ≤ p then 13 FindBestAssignment(i; [[ki]]) 14 ki ← Reconstruct([[ki]]; Ai) 15 Ai sets ri ← ki 16 forall i ∈ [n] do 17 Ai sets Xi ← airi

4.1 The sub-protocol FindBestAssignment

Here, we describe Sub-protocol 3, called FindBestAssignment. The sub-protocol, which is executed by all agents, scans the values in Xi's domain, Di = {aiu : u ∈ [mi]}, and computes a (t, n)-sharing [[ki]] in the index ki ∈ [mi] that issues the currently minimal aggregated cost for Ai.

Before describing the computations in the sub-protocol, we make the following observations. Let ci and cj be two indexed scalars, where i < j. Then

and

(by argmin we mean the smallest index in which the minimum is attained). Hence, if the agents hold (t, n)-shares in ci and in cj, they can jointly compute (t, n)-shares in min(ci, cj) and in argmin(ci, cj), without learning any information on ci and cj, by invoking the secure comparison and multiplication protocols from Section 3.2. Specifically, they will first run

(see Eq. (4)) so that they will hold (t, n)-shares in the bit β := 1cj<ci . Then they will run the secure multiplication protocol (see Eq. (3)),

to get (t, n)-shares in γ := 1cj<ci · (cj - ci). Finally, each agent Ah, h ∈ [n], will compute

In view of Eq. (8), the set [[w]] = {[[w]]h : h ∈ [n]} is a (t, n)-sharing of w := min(ci, cj). In the process of computing those shares, the agents remain completely oblivious to the values of ci, cj, and w. A similar course of action can issue to the agents a (t, n)-sharing of argmin(ci, cj), using Eq. (9).

We now turn to Sub-protocol 3. Its input is the index i of the agent who looks for the currently best assignment to its variable. Recall that FindBestAssignment is invoked from Protocol 2 in Line 13. At that stage in Protocol 2, all agents hold (t, n)-shares in wi(u) for all i ∈ [n] and all u ∈ [mi], being the aggregated cost for Ai if it sets Xi ← aiu , given the current assignments to the variables held by its neighbors.

The sub-protocol scans Ai's domain, Di, and updates two values: ki that will hold the index of the currently best assignment and wi that will hold the corresponding cost. Those two values will not be computed explicitly; instead, the agents will hold secret shares in them.

Initially (Lines 1-2), the agents set ki = 1 and wi = wi(1). Since the agents already hold a secret sharing of the latter value, they simply set [[wi]]h = [[wi(1)]]h, h ∈ [n]. As for ki = 1, since it is a publicly known value, then, in view of our discussion in Section 3.1, each agent sets [[ki]]h = 1, h ∈ [n].

Next, the agents scan the remaining values in Di (Lines 3-8). First, they compute shares in β := 1wi(u)<wi , using SecureCompare (see Eq. (4)), in order to compare wi, the minimum found so far, to the cost of the next assignment, wi(u) (Line 4). Then, they use SecureMult (see Eq. (3)) to compute shares in γ := β·(wi(u)-wi) and in δ := β·(u-ki) (Lines 5-6). (Recall that since u is a publicly known value, each agent Ah, h ∈ [n], sets locally [[u]]h = u.) Finally, they update the shares in wi and ki using Eqs. (8) and (9), respectively (Lines 7-8). At the end of the loop, ki equals the index of the best assignment, and wi equals the associated cost. Since P-DSA needs only [[ki]], the sub-protocol issues that sharing as its output.

Comment. The computation of wi (Lines 5+7) is needed for the computation of β (Line 4) in the subsequent iteration, a value that is used in updating ki (Lines 6+8). Hence, since wi is not a desired output of the sub-protocol, it is possible to skip Lines 5+7 in the last iteration (u = mi).

Sub-protocol 3: FindBestAssignment - Computing a (t, n)-sharing of the index ki of the currently best assignment for Xi.

Input: i - the index of agent Ai 1 forall h ∈ [n] do 2 Ah sets [[ki]]h ← 1 and [[wi]]h ← [[wi(1)]]h 3 forall u = 2, . . . ,mi do 4 [[β]] ← SecureCompare([[wi(u)]], [[wi]]) 5 [[γ]] ← SecureMult([[β]], [[wi(u)]] - [[wi]]) 6 [[δ]] ← SecureMult([[β]], [[u]] - [[ki]]) 7 [[wi]] ← [[wi]] + [[γ]] 8 [[ki]] ← [[ki]] + [[δ]] Output: A (t, n)-sharing of [[ki]]

4.2 Privacy

Protocol 2 preserves topology, constraint, and assignment/decision privacy, owing to the cryptographic machinery that we use - see Theorem 1. It does not respect agent privacy since it requires all n agents to have a full communication network between them.

Theorem 1. Under the assumption of honest majority, Protocol 2 preserves topology, constraint, and assignment/decision privacy.

Proof. The honest majority assumption means that if there exist agents that will try combining their shares in attempt to recover some of the secret-shared values, their number will be smaller than the threshold t = ⌊(n + 1)/2⌋, see Eq. (1). Shamir's secret sharing scheme is perfect, in the sense that any number of shares smaller than the threshold exposes zero information on the shared secret [Shamir, 1979]. Therefore, the secret shares in each of the private values that are secret-shared during P-DSA reveal no information on the underlying private value. Apart from secret sharing, the agents engage also in multi-party protocols for performing secure multiplication and secure comparison, see Eqs. (3) and (4). The protocols that we use are information-theoretic secure, see [Damg˚ard and Nielsen, 2007; Nishide and Ohta, 2007]. Given all of the above, it follows the P-DSA fully preserves all constraint information under the honest majority assumption; hence, it offers constraint privacy.

P-DSA operates over a complete constraint graph, in which every pair of agents has a constraint matrix between them. Since all matrices are secret-shared using the threshold t in Eq. (1), which guarantees perfect privacy under the assumption of honest majority, zero matrices are indistinguishable frommatrices that represent actual constraints. Therefore, PDSA offers also topology privacy.

As also all indices of all assignments are encoded through secret shares, we infer that all assignment information, as well as the final decisions, remain fully protected. Hence, P-DSA offers also assignment/decision privacy.

Note that while Protocol 2 hides from each agent the sequence of assignments of other agents, it does reveal to each agent its own sequence of assignments. Protocol 2 can be further enhanced to also hide from each agent the sequence of value assignments to its own variable, including the initial random value assignment. Due to space limitations, we omit the details of this enhancement.

5 Experiments

We implemented P-DSA and compared its performance to PMax-Sum [Tassa et al., 2017], which is a privacy-preserving implementation of an incomplete DCOP algorithm (MaxSum [Farinelli et al., 2008]).

Experiments were conducted on a machine equipped with an Intel i5-10400 CPU @ 2.90GHz, 2904 Mhz, 6 Core(s), 12 Logical Processor(s), 16GB DDR4 RAM. The system ran Microsoft Windows 10 Pro, and the code was written in Java 1.8.0 using the SinAlgo simulation framework. The source code is available on https://github.com/dcop2025/dcop-sim/tree/main.

P-DSA was implemented over Zq with q = 231 - 1. PMax-Sum was implemented with 512-bit homomorphic encryption.

In our experiments, we compared the quality of the solutions issued by each of those two algorithms within a given time frame. We used the following settings of the main parameters that affect the algorithms' runtimes:

• Number of agents n ∈ {10, 20, 30, 40, . . . , 100}.
• Domains' size m ∈ {5, 10, 15, 20, 25}. For simplicity, we assumed that all domains have the same size m.
• Constraint density, d ∈ {0.2, 0.4, 0.6, 0.8, 1.0} - the fraction of constrained pairs of variables out of all (n2 ) pairs.

To test the effect of each of those three parameters, we set the other two to the value that is underlined in their respective set of tested values and varied the value of the tested parameter. For example, in testing the effect of the number of agents, we set all domain sizes to be m = 10 and used constraint density of d = 0.4 and then ran experiments with n ∈ {10, . . . , 100}.

We refer to each triple ⟨n, m, d⟩ as a configuration. In each tested configuration, we evaluated both algorithms in the following manner: We selected a new random problem (where a problem consists of the constraint graph as well as the constraint matrices), ran both algorithms on the same problem, and evaluated the cost of their output after T = 1, 2, 3 minutes of execution. We repeated that experiment 20 times, and we report the average of the costs obtained by each of the two algorithms within each of the prescribed time frames.

In one set of experiments we used random constraint graphs, where each graph is a random graph of n nodes in which each pair of nodes is connected by an edge in probability d. In another set of experiments we generated scale-free random graphs [Barab´asi and Albert, 1999] with an initial clique of size 5, and 4 backward edges for each additional node. In all experiments, each constraint matrix was a random m × m matrix with entries that distribute uniformly on the interval [0, 10].

Number of agents in random graphs. We compared the average cost of solutions issued by each of the two algorithms within each of the three prescribed time frames for a varying number of agents n (where in all problems, the domain size was m = 10 and the network density was d = 0.4). Table 1 shows the average costs issued by the two algorithms (rounded to the nearest integer). The symbol ⊥ indicates that the algorithm did not manage to complete even one iteration within the time frame.

We see the overwhelming advantages of P-DSA over PMax-Sum in terms of scalability and quality of solutions. Indeed, while P-Max-Sum could not produce a solution within 1 minute already for n = 40 and could not produce a solution within 3 minutes for n ≥ 60, P-DSA was able to produce solutions within 1 minute for all n ≤ 60 and managed to produce a solution within 3 minutes for all tested values of n. Furthermore, the solutions produced by P-DSA were better than those issued by P-Max-Sum by more than 50% for n = 10 and by 20% for the largest problem in which PMax-Sum issued a solution. In addition, we see that P-DSA

always improves the quality of its output when allowed to run for more time, while P-Max-Sum sometimes fluctuates (see, e.g., its outputs when n = 30). That is why it is sometimes executed with the anytime mechanism [Zivan et al., 2014] that outputs the best solution visited throughout the run of the algorithm. Such a mechanism has its overhead, and in P-DSA, it appears that there is less need to apply it. (It is important to stress that P-DSA and P-Max-Sum issue the very same intermediate and final assignments as DSA and MaxSum, respectively. Namely, the cryptographic layer protects the underlying private information but does not alter it.)

Number of agents in scale-free graphs. We repeated the previous experiment, but this time with scale-free graphs. The results are given in Table 2. Here, too, we see that PDSA is more scalable and issues better solutions.

Domain size in random graphs. Here we fixed n = 30 and d = 0.4 and varied the domain size m. The results are given in Table 3. As already demonstrated, P-DSA is more scalable than P-Max-Sum and managed to issue outputs to problems in which P-Max-Sum failed to complete even one iteration within the same time frame. Moreover, when both algorithms issued outputs, those of P-DSA had costs lower than those of P-Max-Sum, with improvements ranging from 22% to 38%.

Constraint density in randomgraphs. Here we fixed n = 30 and m = 10 and varied the constraint density d. The results are given in Table 4. As before, P-DSA issues solutions with costs that are significantly lower than P-MaxSum's (where in one configuration, the improvement was as high as 47%). As for scalability, P-DSA's runtime does not depend on the network density since it operates on the complete graph, where non-constrained pairs of agents are connected by an edge with a zero constraint matrix. P-Max-Sum, on the other hand, works on the original constraint graph, and therefore, its runtime does depend on the network density. Hence, it failed to issue an output on dense networks for which P-DSA did issue an output.

Due to lack of space we omit description of experiments that compare the runtimes of P-DSA and the basic DSA, in order to illustrate the price of privacy. We intend to include such experiments in the full version of this study.

6 Conclusion

We presented here P-DSA - the first privacy-preserving implementation of a DCOP algorithm that is based on local search. It offers topology, constraint, and assignment/decision privacy. The algorithm is much more scalable than P-Max-Sum, a privacy-preserving implementation of another incomplete DCOP algorithm. It also offers solutions with much better costs than those issued by P-MaxSum. Since P-DSA was able to solve in short time (3 minutes) problems involving as high as 100 agents, while all prior studies on privacy-preserving DCOP algorithms report experiments of much smaller scale and runtimes that are significantly higher, P-DSA emerges as a suitable choice for solving large-scale DCOPs in a privacy-preserving manner.

Our approach can also be extended to develop a privacypreserving version of MGM [Maheswaran et al., 2004], another local search algorithm for DCOPs. Even though the "basic plot" in MGM is similar to DSA's, it is more involved as the decision to update local assignments is taken based on a competition among agents and not by a coin-toss. Implementing the more intricate logic of MGM in a privacy-preserving manner is a challenge that we intend to undertake in a future research.

Acknowledgments

This work was partially supported by the Ministry of Innovation, Science and Technology, Israel.