A Privacy Preserving Collusion Secure DCOP Algorithm

1 Introduction

Constraint optimization [Meseguer and Larrosa, 1995] is a powerful framework for describing optimization problems in terms of constraints. In many practical domains, such as Meeting Scheduling [Maheswaran et al., 2004], Mobile Sensor nets [Farinelli et al., 2008], and the Internet of Things [Lezama et al., 2017], the constraints are enforced by distinct participants (agents). Hirayama and Yokoo [1997] termed such problems as Distributed Constraint Optimization Problems (DCOPs). Various algorithms for solving DCOPs have been proposed, some of which are complete [Gershman et al., 2009; Hirayama and Yokoo, 1997; Mailler and Lesser, 2004; Modi et al., 2005; Petcu and Faltings, 2005; Yeoh et al., 2010], and some are incomplete [Farinelli et al., 2008; Katagishi and Pearce, 2007; Ottens et al., 2017; Zhang et al., 2005].

The main motivation for DCOP research stems from the inherent distributed structure of many real-world problems, and the privacy concerns that are associated with this distribution. L´eaut´e and Faltings [2013] offered the basic definitions of privacy in this framework. The four notions of privacy that they describe are: agent privacy, topology privacy, constraint privacy and decision privacy (see Section 2). Several studies considered a solution of DCOPs in a manner that preserves (some of) those privacy types.

This line of research began with the work of Silaghi and Mitra [2004]. They proposed a privacy-preserving solution to Distributed Weighted Constraint Satisfaction Problems (DisWCSPs); those are distributed problems that are similar to DCOPs, but differ from them in the distribution model and, consequently, in the related privacy targets. Their solution is strictly limited to small scale problems since it depends on an exhaustive search over all possible assignments. As their solution is based on the BGW protocol [Ben-Or et al., 1988], it is immune against coalitions that involve less than half of the agents.

All of the subsequent studies considered DCOPs. The main motif in those studies was to develop privacy-preserving versions of existing algorithms. Greenstadt et al. [2007] devised a version of the DPOP algorithm [Petcu and Faltings, 2005], called SSDPOP. L´eaut´e and Faltings [2013] proposed three privacy-preserving versions of DPOP that differ in their privacy guarantees and in their runtime performance. Grinshpoun and Tassa [2016] developed P-SyncBB, a privacypreserving version of the complete search algorithm SyncBB [Hirayama and Yokoo, 1997]. Tassa et al. [2017] presented P-Max-Sum, a privacy-preserving version of the incomplete inference-based Max-Sum algorithm [Farinelli et al., 2008]. Lastly, Grinshpoun et al. [2019] devised P-RODA, a secure implementation of region-optimal algorithms.

All of the above described works based their security on assuming solitary conduct of the agents. Alas, subsets of agents may try to collude and combine the information which they have in order to infer information on other agents. In this paper we suggest the first privacy-preserving DCOP algorithm that is immune against such coalitions. We depart from the SyncBB algorithm and devise a privacy-preserving algorithm that simulates its operation and provides topology, constraint and decision privacies, even in the presence of a coalition of agents, under the assumption of an honest majority (i.e., the size of the coalition is smaller than half the number of agents).

2 Definitions and Assumptions

A Distributed Constraint Optimization Problem (DCOP) is a tuple 〈A,X,D,R〉 where A is a set of agents A1,A2, . . . ,An, X is a set of variables X1,X2, . . . ,Xm, D is a set of finite domains D1,D2, . . . ,Dm, and R is a set of relations (constraints). Each variable Xi takes values in the domain Di, and it is held by a single agent. Each constraint C ∈ R defines a non-negative cost for every possible value combination of a set of variables, and is of the form C : Di1 × · · · × Dik → [0, q], for some 1 ≤ i1 < · · · < ik ≤ m, and a publicly known maximal constraint cost q.

An assignment is a pair including a variable, and a value from that variable's domain. We denote by ai the value assigned to the variable Xi. A partial assignment (PA) is a set of assignments in which each variable appears at most once. A constraint C ∈ R is applicable to a PA if all variables that are constrained by C are included in the PA. The cost of a PA is the sum of all applicable constraints to the PA. A full assignment is a partial assignment that includes all of the variables. The goal in Constraint Optimization Problems is to find a full assignment of minimal cost.

For simplicity, we assume that each agent holds exactly one variable, i.e., n = m. We let n denote hereinafter the number of agents and the number of variables. We consider a binary version of DCOPs, in which every C ∈ R constraints exactly two variables and takes the form Ci,j : Di × Dj → [0, q]. These assumptions are customary in DCOP literature [Modi et al., 2005; Petcu and Faltings, 2005].

L´eaut´e and Faltings [2013] have distinguished between four notions of privacy. The notions of privacy which our proposed algorithm respects are: (a) Topology privacy - hiding from each agent the topological structures in the constraint graph beyond his 1 own direct neighborhood in the graph; (b) Constraint privacy - hiding from each agent the constraints in which he is not involved; and (c) Decision privacy - hiding from each agent the final assignments to other variables.

Like in all prior art on privacy-preserving DCOP algorithms, we too assume that the agents are semi-honest, namely, they follow the prescribed protocol but try to glean more information than allowed from the protocol transcript. In contrast to prior art, we assume that (less than half of the) agents may collude in order to combine their inputs and messages received during the execution of the protocol, for the purpose of extracting private information on other agents.

3 A Secure Synchronous Branch and Bound

Synchronous Branch-and-Bound (SyncBB) [Hirayama and Yokoo, 1997] was the first complete algorithm for solving DCOPs. SyncBB operates in a completely sequential manner, a fact that inherently renders its synchronous behavior. It assumes a static public ordering of the agents, A1, . . . , An. The search space of the problem is traversed by each agent assigning a value to his variable and passing the current partial assignment (CPA) to the next agent in the order, along with the current cost of the CPA. After an agent completes assigning all values in the domain to his variable, he backtracks, i.e., he sends the CPA back to the preceding agent. To prevent exhaustive traversal of the entire search space, the agents maintain an upper bound, which is the cost of the best solution that was found thus far. The algorithm keeps comparing the costs of CPAs and the current upper bound, in order to prune the search space.

1 We use the masculine form for simplicity.

Herein we devise a secure implementation of SyncBB, called PC-SyncBB (Privacy-preserving and Collusionresistant SyncBB). Another secure implementation of SyncBB, called P-SyncBB, was previously introduced by Grinshpoun and Tassa [2014; 2016]. The two algorithms are fundamentally different. While in P-SyncBB agents are exposed to sensitive information such as assignments of other agents, costs of CPAs, and the value of the upper bound, PCSyncBB totally avoids such information disclosure. Hence, the outline of PC-SyncBB is simpler than that of P-SyncBB, because there is no need to implement mechanisms for preventing illegal inferences that can be deduced from such information. On the other hand, as in PC-SyncBB much less information is revealed, and as PC-SyncBB is designed to be resistant to coalitions (while P-SyncBB's security is jeopardized already when two agents collude), the secure multiparty computational tasks in PC-SyncBB are much harder. Hence, the cryptographic approach taken in PC-SyncBB is completely different, and it is much more involved than the corresponding one in P-SyncBB.

3.1 Preliminaries

General Assumptions and Notations

The design of PC-SyncBB is based on the following general assumptions:

• There is a static public ordering of the agents, A1, . . . , An.
• The upper bound on the cost of any possible solution is q∞ := (n2 )q + 1, and it is known to all agents. In addition, all agents agree upfront on an integer S greater than 2q∞.
• For every pair of indices 1 ≤ t < k ≤ n, Γ(t, k) is a Boolean predicate that equals true iff Xt and Xk are constrained. Then, I - k := {t : 1 ≤ t < k and Γ(t, k)} and I + k := {t : k < t ≤ n and Γ(k, t)} are sets containing the indices of all agents that precede/follow Ak in the order and whose variable is constrained with Xk. We also let Ik := I - k ∪ I + k .

Value Ordering

Each agent Ak maintains two value orderings over his domain Dk. Each of those orderings can be described by a vector of length |Dk|. The first ordering, denoted uk, is fixed and known to all agents At such that t ∈ Ik. Then if At and Ak are constrained, they can describe their constraint Ct,k as a matrixMt,k of |Dt| rows and |Dk| columns, where the value in the r-th row and s-th column is

The second ordering, denoted wk, is generated at random by Ak whenever he begins a new traversal over his domain. That ordering, which is kept secret from all other agents, determines the order in which that agent will scan the values in his domain during that stage of the search. Agent Ak generates such an ordering each time a CPA is passed to him from the preceding agent Ak-1.

Internal Variables

Every agent Ak maintains the following variables:

• sCPAk is an array of length n that holds additive shares in the cost of the CPA. Assume that agents At and Ak are constrained and that Ct,k is applicable to the CPA. Then the cost of the CPA includes, as one of its addends, the value Ct,k(Xt,Xk). In such a case sCPAk(t) and sCPAt(k) will both store random values in ZS so that

If, on the other hand, Ct,k is not applicable to the CPA (i.e. the CPA does not include Xk or Xt or both), then sCPAk(t) = sCPAt(k) = 0. In view of the above, the overall cost of the CPA, at any stage of the algorithm's run, equals

• sUBk holds an additive share in the upper bound (the cost of the best full assignment that was discovered thus far). Each such share is random and uniformly distributed over ZS. At any stage of the algorithm's run,

• pk is a pointer to a value in the ordering wk. The current assignment to Xk is given by wk(pk).
• OptimalSettingk stores the assignment to Xk in the currently best full assignment that was found thus far.

3.2 The PC-SyncBB Algorithm

The PC-SyncBB algorithm is given in Algorithm 1, which we proceed to describe.

The Procedure init

Every agent Ak initializes all entries in his vector sCPAk as well as pk to zero (Lines 1-2). Then, every agent Ak, k > 1, initializes sUBk to zero, while A1 initializes it to q∞ (Lines 3-6). Such settings imply that ∑nk=1 sUBk = q∞ mod S, in agreement with Eq. (4) (since the initial upper bound is set to q∞). Finally, the procedure init triggers the search by having A1 call the procedure assign CPA (Line 7).

The Procedure assign CPA

If this procedure is called when pk = 0, it means that Ak now begins a new traversal over his domain. Hence, in such a case he generates a new random ordering, wk, of Dk (Lines 8-9). In order to move to the next value in wk, Ak increments the pointer pk (Line 10). If pk becomes greater than |Dk| it means that the domain Dk was already fully scanned, so Ak performs the procedure backtrack (discussed below) in order to return the search torch back to the preceding agent Ak-1 (Lines 11-12). Otherwise, Ak assigns v := wk(pk) to Xk (Line 14). Consequently, as Xk has a new value, the CPA's cost is changed, so new random shares of that cost must be computed. This is done by calling the

Algorithm 1 - PC-SyncBB (executed by agent Ak)

procedure init

1: sCPAk(t) ← 0 for all 1 ≤ t ≤ n

3: if k > 1 do

4:

sUBk ← 0

• 5: else
• 6: sUBk ← q∞
• 7: assign CPA()

procedure assign CPA

• 8: if pk = 0 do

9: Generate a new random ordering of Dk into wk 10: pk ← pk +1 11: if pk > |Dk| do 12: backtrack() 13: else 14: Xk ← v := wk(pk) 15: update shares in CPA(k, v) 16: if k = n do 17: if compare CPA cost to upper bound() = true do 18: broadcast(NEW OPTIMUM FOUND) 19: assign CPA() 20: else 21: if compare CPA cost to upper bound() = false do 22: assign CPA() 23: else 24: send(CPA MSG) to Ak+1

procedure backtrack

• 25: if k > 1 do
• 26: sCPAk(t) ← 0 for all t ∈ I - k
• 27: send(ZERO SHARE MSG,k) to At for all t ∈ I - k
• 28: send(BACKTRACK MSG) to Ak-1

• 29: else
• 30: broadcast(COMPLETE)

when received (NEW OPTIMUM FOUND) do

32: OptimalSettingk ←Xk

when received (CPA MSG) do

34: assign CPA()

when received (ZERO SHARE MSG,k′ ) do

35: sCPAk(k′ ) ← 0

when received (BACKTRACK MSG) do

36: assign CPA()

when received (COMPLETE) do

37: Xk ←OptimalSettingk

38: Terminate

sub-protocol update shares in CPA(k, v) (Line 15), which recomputes sCPAk(t) and sCPAt(k), for all t ∈ I - k , so that the right-hand side of Eq. (3) equals the new CPA's cost. (We discuss that sub-protocol in Section 3.3.)

We now separate the discussion according to the index k of the operating agent. If k = n, then a new full assignment is reached. It is needed to compare its cost, which equals ∑nk=1 ∑t∈Ik sCPAk(t) mod S, Eq. (3), to the current upper bound, ∑nk=1 sUBk mod S, (Eq. (4)). This comparison must be done in a secure manner. To that end, An invokes compare CPA cost to upper bound (Line 17), a secure multi-party sub-protocol that we discuss in Section 3.4. It returns true if the cost of the current full assignment is lower than the upper bound, namely, if

and false otherwise. If the current full assignment does improve the upper bound, then An broadcasts the message NEW OPTIMUM FOUND (Line 18). Upon receiving such a message, every agent Ak stores the sum of his current shares, ∑t∈Ik sCPAk(t), in sUBk and he also stores the current assignment of Xk in OptimalSettingk (Lines 31-32). Finally, whether the current full assignment is a new optimum or not, An calls the procedure assign CPA again in order to test the next value in his domain (Line 19).

If k < n, the agents examine the possibility to prune the search space: they first check whether the CPA's cost is already greater than or equal to the upper bound, by invoking compare CPA cost to upper bound (Line 21). If it returns false then Eq. (5) does not hold, i.e., the cost of the CPA is already greater than or equal to the upper bound. In such a case there is no point in pursuing the current path in the search space, so Ak calls the procedure assign CPA again in order to test the next value in his domain (Line 22). Otherwise, Ak passes the torch onward to Ak+1 (by sending him the message CPA MSG in Line 24) in order to continue the search over CPAs with the current k-prefix. When Ak+1 receives the message CPA MSG, he zeroes the pointer pk+1 to his domain Dk+1, in order to start traversing all values in Dk+1 as possible extensions to the current k-CPA, and then he calls the procedure assign CPA (Lines 33-34).

The Procedure backtrack

When agent Ak, k > 1, executes the procedure backtrack, he does two things. First, he zeros all entries in sCPAk (Line 26) and sends a ZERO SHARE MSG message, with his index k, to all agents that precede him and are constrained with him (Line 27). Any such agent, upon receiving the ZERO SHARE

MSG message, zeroes the relevant share in his own array (Line 35). As a result of the above two actions, Eq. (3) still holds for the reduced CPA that is obtained after this backtracking. Afterwards, Ak sends a BACKTRACK MSG message to Ak-1 (Line 28). When the latter receives that message, he calls assign CPA in order to change the assignment of his variable to the next value in his domain and proceed the search with the new modified CPA (Line 36).

When A1 performs backtrack, it means that he completed a traversal of D1, and, consequently, the entire search space (D1×· · ·×Dn) was scanned. Therefore, the algorithm terminates with the last optimum found being the global optimum. In such a case A1 broadcasts the message COMPLETE (Line 30). When receiving such a message, every agent Ak assigns to his variable Xk the value OptimalSettingk (which was his assignment in the last optimal solution that was found) and then he terminates (Lines 37-38).

3.3 The Sub-protocol update shares in CPA

Before starting PC-SyncBB, each of the agents Ak, k < n, creates a key pair in a Paillier cipher [Paillier, 1999] and sends the corresponding public key to At for all t ∈ I + k . Denote by Ek the encryption function in Ak's cipher and by νk the corresponding modulus. Then Ek is a function from Zν to Z∗ν 2 and it is additively homomorphic, in the sense that for every two plaintexts x and y, Ek(x+y) = Ek(x) · Ek(y), where addition is modulo ν and multiplication is modulo ν 2 . The Paillier cipher is probabilistic, in the sense that the encryption function depends also on a random string (so that every plaintext x has a large number of possible ciphertexts Ek(x)). It is known to be semantically secure [Goldwasser and Micali, 1982].

After creating Ek, Ak computes a vector z1k of length |Dk| where z1k (1) = Ek(1) and z1k (i) = Ek(0) for all 2 ≤ i ≤ |Dk|. It is important to compute the latter |Dk|-1 encryptions with |Dk|-1 independently selected random strings. Then, Ak defines the vectors zik = CRS (zi-1 k ), for 2 ≤ i ≤ |Dk|, where CRS(·) is a circular right-shift by one position of the vector entries. Hence, zik encrypts the vector (0, . . . , 0, 1, 0, . . . , 0) where the 1 appears in the ith entry, 1 ≤ i ≤ |Dk|. Given the manner in which those vectors were computed and the probabilistic and semantic security properties of the Paillier cipher, a polynomially-bounded adversary who gets any random sequence of those vectors (i.e. zi1 k , zi2 k , . . .) will not be able to distinguish between the Ek(1) and the Ek(0) entries in them (with a non-negligible probability of success).

We are now ready to describe the sub-protocol update shares in CPA (Algorithm 2). It is triggered by Ak whenever he assigns a new value v to his variable, Xk. When that happens, it is needed to update the shares of all agents A1, . . . ,Ak so that the validity of Eq. (3) is maintained. The shares that should be modified in wake of such an assignment are sCPAk(t) and sCPAt(k) for all t ∈ I - k . Those shares will be modified so that, in view of Eq. (2), the sum of sCPAk(t) and sCPAt(k), for any fixed t ∈ I - k , will equal Ct,k(Xt,Xk) for the current assignments of Xt and Xk (Xk's assignment equals v, and it is passed to the sub-protocol as an input).

Assume that t ∈ I - k . Then the contribution of the pair Xt and Xk to the CPA is Mt,k(r, s), where ut(r) = Xt and uk(s) = Xk (see Eq. (1)). Recall that At does not know s while Ak does not know r. In order to compute the new respective shares, sCPAk(t) and sCPAt(k), so that Eq. (2) holds, these two agents perform the following computation.

When At performed last time the procedure assign CPA and set there the current assignment to Xt, he called update shares in CPA (Algorithm 2), see Line 15 in PCSyncBB. In Line 8 of Algorithm 2 he sent to all agents in I + t the vector zjt which encodes his current assignment. Going back to the present, when Ak executes update shares in CPA he holds a vector zt that he received fromAt for every t ∈ I - k . That vector equals zrt , where r is the index in ut in which the current assignment to Xt is stored. Even though Ak cannot infer from zt the current value of Xt, he can still correctly update his shares vis-a-vis At. To that end, he computes

Algorithm 2 The sub-protocol update shares in CPA

when received k, the index of the agent Ak that invokes the procedure, and v, Ak's current assignment

• 1: for all t ∈ I - k do
• 2: Ak selects uniformly at random ρ ∈ ZS.
• 3: Ak computes yt as given in Eq. (6), where zt is the vector that Ak received fromAt in the last time.
• 4: Ak sends the computed yt to At.
• 5: At sets sCPAt(k) ← E -1 t (yt).
• 6: Ak sets sCPAk(t) ← ρ.
• 7: if k < n do
• 8: Ak sends to all At where t ∈ I + k the vector zjk where j is the index for which uk(j) = v.

where s is the index of the entry in uk that holds v - the current assignment to Xk, and ρ is a value selected uniformly at random (independently for each At) from ZS. The key observation here is the following.

Lemma 3.1 The homomorphism of Et implies that yt = Et ([(Mt,k(r, s) - ρ) mod S]).

Next, Ak sends yt to At who decrypts it and stores it in sCPAt(k). In view of Lemma 3.1, At obtains sCPAt(k) = (Mt,k(r, s) - ρ) mod S whereas Ak sets sCPAk(t) = ρ mod S (Algorithm 2, Lines 5-6). Those two uniformly random shares satisfy sCPAt(k) + sCPAk(t) = Mt,k(r, s) mod S, which fulfils the required equality in Eq. (2).

The above described updates are carried out by Ak and At for all t ∈ I - k . After completing all those updates, the updated shares satisfy Eq. (3).

3.4 compare CPA cost to upper bound

The sub-protocol compare CPA cost to upper bound verifies the inequality in Eq. (5). Agent Ak, 1 ≤ k ≤ n, holds two integers modulo S: ak := ∑t∈Ik sCPAk(t) mod S and bk := sUBk mod S. The goal is to determine whether α := ∑nk=1 ak mod S is smaller than β := ∑nk=1 bk mod S or not. To this end, we make use of a secure multi-party computation (MPC) protocol [Yao, 1982]. An MPC protocol for some function f allows a set of n distrustful parties A1, . . . ,An, where Ai possesses a private input xi, to compute y ← f(x1, . . . , xn), while preserving the privacy of the parties. Namely, at the end of the protocol the parties learn y, but nothing beyond that on inputs of other parties. Almost all practical MPC protocols work with the underlying Boolean/Arithmetic circuit as the computational model. Therefore, to securely compute the function f , the parties first need to agree on a Boolean/Arithmetic circuit C that implements f. The runtime of such computations depends on n and the size |C| of the circuit C (the number of gates in it).

In PC-SyncBB, we managed to shrink the usage of a general purpose MPC protocol to the computation of Eq. (5). Specifically, we use the protocol of Ben-Efraim and Omri [2017] for the function f(x1, . . . , xn) where Ak's input is xk = bk - ak mod S and the function f returns true if Eq. (5) holds and false otherwise.

The protocol of Ben-Efraim and Omri [2017] is secure under the assumption that less than n/2 parties collude. It proceeds in two phases, called "offline" and "online". In the offline phase the parties do not yet know their inputs, but can prepare the raw materials required for the computation. The online phase begins once the parties know their inputs. In practice, this allows the parties to perform the offline phase in advance, even without having their inputs (or even knowing the domains), and perform the fast online phase once the inputs are ready. Due to page limitations, we defer the detailed description of this sub-protocol to the full version.

3.5 Properties of PC-SyncBB

The main properties of this algorithm are stated below. 2

Theorem 3.2 PC-SyncBB is complete and sound.

Theorem 3.3 PC-SyncBB provides constraint-, topology-, and assignment/decision-privacy. Even if any subset B ⊊ A of agents collude, where |B| < n/2, they would not be able to infer information on (values or existence of) constraints between two agents outside the coalition, or on value assignments or final decisions of such agents.

It is important to note that, like all preceding papers on privacy-preserving solution of DCOPs, our algorithm does not guarantee perfect privacy, as it may leak some very benign information on the constraint graph topology. While achieving perfect privacy is possible, in theory, in any multi-party computation, it is very hard to do so while maintaining practicality. Hence, in almost all studies that deal with privacypreserving solutions of practical problems, one accepts benign information leakages.

4 Experimental Evaluation

We begin by evaluating the runtime of the compare CPA cost to upper bound sub-protocol, which is a central and computationally expensive part of PC-SyncBB. For efficiency and reproducibility we used the original implementation of Ben-Efraim and Omri [2017]. 3 The executions were over LAN with EC2 machines of type c5.large in Amazon's North Virginia data center with every agent running on a separate machine. We measured performance for various values of n, where q (the maximum value of a single binary constraint) is set to 100. Hence, as the maximum cost of any solution is q∞ := (n2 )q + 1 and S is set to be the smallest power of 2 greater than 2q∞, then n fully determines ℓ = logS and, consequently, also the size of the circuit C that the protocol uses. Table 1 gives, for each n, the bit-length ℓ of the agents' inputs, the overall circuit size (number of gates), and the average runtimes over 100 executions for the offline and online phases of the protocol.

Now we turn to the runtime performance evaluation of the full PC-SyncBB algorithm. In order to asses the toll of privacy preservation, we compare PC-SyncBB (offline+online) to other algorithms that maintain the Branch & Bound structure - P-SyncBB [Grinshpoun and Tassa, 2016] that preserves privacy only under the assumption of non-colluding agents, and the basic insecure SyncBB [Hirayama and Yokoo, 1997]. We also present separately the online requirements of PC-SyncBB. The algorithms were implemented and executed in the AgentZero simulator [Lutati et al., 2014], running on a hardware comprised of an Intel i7-6820HQ processor and 32GB memory, except for the calls to the compare CPA cost to upper bound procedure that were executed on the machines from Amazon's North Virginia data center, in order to simulate as realistically as possible a truly distributed environment. We followed the simulated time [Sultanik et al., 2008] approach in all the subsequent experiments. The results are shown in a logarithmic scale and are the average over 50 problem instances (for each setting/benchmark).

2 Proofs are given at http://arxiv.org/abs/1905.09013.

3 https://github.com/cryptobiu/Protocols/tree/master/Concrete Efficiency Improvements to Multiparty Garbling with an Honest Majority

The first benchmark consists of unstructured randomly generated DCOPs on which we perform two experiments. In the first experiment, presented in Figure 1, we fix the number of agents to n = 7 and the domain sizes to 6, and vary the constraint density 0.3 ≤ p1 ≤ 0.9. (Using lower density values p1 < 0.3 results in unconnected constraint graphs.) It is clear that constraint density only mildly affects the runtime performance of all the evaluated algorithms. However, the toll of privacy preservation is evidently high, with each layer of protection adding about two orders of magnitude to the runtime. Specifically, the online part of PC-SyncBB requires about one order of magnitude more time than P-SyncBB.

In the second experiment, shown in Figure 2, we fix the constraint density to p1 = 0.3 and the domain sizes to 6, and vary the number of agents 5 ≤ n ≤ 9. Here and in the following scalability experiments we use a cutoff time of 30 minutes for online PC-SyncBB. It is clear that the number of agents has a major effect on the performance of all the evaluated algorithms, in accordance with known results regarding the scalability of Branch & Bound algorithms in computationally hard problems. Interestingly, P-SyncBB scales slightly better, probably due to its inherent use of sorted value ordering.

Similar scalability phenomena are also observed in more structured benchmarks. Figure 3 depicts the runtime performance on distributed 3-color graph coloring problems (p1 =

PC-SyncBB PC-SyncBB-online P-SyncBB SyncBB

Figure 3: Varying n (graph coloring problems).

0.4, 5 ≤ n ≤ 19) in which each pair of equal values of constrained agents imposes a random and private cost. The structure in these problems lies in the diagonal constraint matrices between every pair of neighboring agents. An experiment on scale-free networks, generated according to the Barab´asiAlbert model [Barab´asi and Albert, 1999], produced almost the same graph as in Figure 2 and is thus omitted.

5 Conclusion

We proposed herein PC-SyncBB, the first privacy-preserving DCOP algorithm which is secure against coalitions. We analyzed the properties of the algorithm and evaluated its performance. Our experiments demonstrate that PC-SyncBB is feasible for moderately-sized problems.

A major limitation on scalability is due to the protocol of Ben-Efraim and Omri [2017] that is invoked by compare CPA cost to upper bound. In the future we intend to explore other directions that could yield much more efficient implementations of that sub-protocol. If those constructions prove more efficient, we intend to consider more challenging settings, with larger coalitions or malicious agents. While raising the security bar usually increases runtime and communication costs, it is important to come up with such solutions in order to enlarge and diversify the toolkit available for implementations in various application settings. Finally, as all existing privacy-preserving DCOP algorithms base their security on assuming solitary conduct of the agents, we view this study as an essential first step towards lifting this potentially harmful assumption in all those algorithms. In particular, it is necessary to develop privacy-preserving and collision-secure implementations of other DCOP algorithms (e.g., inference-based), and especially of incomplete algorithms that could offer better scalability.