Max-Sum Goes Private

1 Introduction

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

The MAX-SUM algorithm [Farinelli et al., 2008] is an incomplete, GDL-based, algorithm that has drawn considerable attention in recent years, including being proposed for multiagent applications such as sensor systems [Teacy et al., 2008; Stranders et al., 2009] and task allocation for rescue teams in disaster areas [Ramchurn et al., 2010]. Agents in MAX-SUM propagate cost/utility information to all neighbors. This contrasts with other inference algorithms such as ADPOP [Petcu and Faltings, 2005a], in which agents only propagate costs up a pseudo-tree structure.

One of the main motivations for solving constraint problems in a distributed manner is that of privacy. The term pri-

Tal Grinshpoun

Ariel University Ariel, Israel talgr@ariel.ac.il

vacy is quite broad, a fact that gave rise to several categorizations of the different types of privacy [Greenstadt et al., 2007; Grinshpoun, 2012; L´eaut´e and Faltings, 2013]. In this paper we relate to the categorization of L´eaut´e and Faltings [2013] that distinguish between agent privacy, topology privacy, constraint privacy, and assignment/decision privacy.

Most studies that evaluated distributed constraint algorithms in terms of privacy considered either search algorithms or complete inference algorithms. Some examples are Maheswaran et al. [2006] who proposed the VPS framework that was initially used to measure the constraint privacy loss in SyncBB and OptAPO. Later, VPS was also applied to DPOP and ADOPT [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. Several privacy-preserving versions of DPOP were proposed in the past [Greenstadt et al., 2007; Silaghi et al., 2006] including a recent study by L´eaut´e and Faltings [2013] that proposed several versions of DPOP that provide strong privacy guarantees. Another recent paper [Grinshpoun and Tassa, 2014] devises a variation of SyncBB that preserves constraint privacy.

In this paper we propose the first private algorithm that is based on MAX-SUM. The proposed algorithm, P-MAXSUM, has multiple agents preforming the role of each node in the factor graph, on which the MAX-SUM algorithm operates. Using secret sharing and homomorphic encryption, the agents may execute the nodes' role without revealing the content of the messages they receive or the details of the computation they perform and the messages that they generate. Thus, the proposed algorithm prevents agents from revealing the identity of other agents with which their neighbors are constrained (topology privacy), the costs their neighbors assign to value assignments (constraint privacy), or the assignment selection of their neighbors (assignment/decision privacy). By allowing a single call to a trusted coordinator, P-MAX-SUM can also preserve agent privacy.

2 Preliminaries

A Distributed Constraint Optimization Problem (DCOP) [Hirayama and Yokoo, 1997] 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 nonnegative cost for every possible value combination of a set of variables, and is of the form C : Di1 × · · · ×Dik → R+ := [0,∞), for some 1 ≤ i1 < · · · < ik ≤ m.

A value assignment is a pair including a variable and a value from that variable's domain. A complete assignment consists of value assignments to all variables in X. The objective is to find a complete assignment of minimal cost.

For simplicity, we make the common assumption 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. For the same reasons we also concentrate on binary DCOPs, in which all constraints are binary, i.e., they refer to exactly two variables. Such constraints take the form Ci,j : Di × Dj → R+. These assumptions are customary in DCOP literature (e.g., [Modi et al., 2005; Petcu and Faltings, 2005b]).

Each DCOP induces a graph G = (V, E) where V = X , and an edge connects the nodes Xi,Xj ∈ V if there is a constraint C ∈ R that is defined on Di ×Dj . The corresponding factor graph is a bipartite graph G′ = (V ′ ,E′ ) which is defined as follows.

• V ′ has two types of nodes: (a) variable nodes - X1, . . . ,Xn, and (b) function nodes - for each e = (Xi,Xj) ∈ E there is a node Xe in V ′ .
• E′ contains an edge that connects Xi with Xe if and only if e is an edge in G which is adjacent to Xi.

Knowledge Assumptions. We make the following commonly used assumptions (see, e.g. [L´eaut´e and Faltings, 2013]): A variable and its domain are known only to its owner agent and to the agents owning neighboring variables. In addition, a constraint is fully known to all agents owning variables in its scope, and no other agent knows anything about the constraint (not even its existence).

We describe a variant of our protocol that maintains also agent privacy. For this variant we make also the additional assumption that each agent knows all agents that own a variable that is a neighbor of their own variable in the constraint graph, but does not know any of the other agents, not even their existence.

Communication Assumptions. Here too we make the standard communication assumptions (see, e.g. [Modi et al., 2005]): Each agent can send messages to any of its neighboring agents. The communication system is resilient in the sense that messages do not get lost and they are received by their intended recipient in the same order that they were sent out.

2.1 The Max-Sum algorithm

The MAX-SUM algorithm performs synchronous steps (iterations) that in each of them a couple of messages are sent along each edge of G′ in both directions. Let us consider the edge that connects Xi with Xe, where e = (Xi,Xj). The messages, in both directions, will be vectors of dimension |Di| and they will be denoted by either Qki→e or Rk e→i , depending on the direction, where k is the index of the synchronous step.

If x is one of the elements in Di then its corresponding entry in the message will be denoted by Qki→e (x) or Rk e→i (x).

In the first step all messages are zero. After completing the kth step, the messages in the next step will be as follows. Fixing a variable node Xi and letting Ni be its set of neighbors, then for each Xe ∈ Ni, Xi will send to Xe the vector

Fixing a function node Xe, where e = (Xi,Xj), then for each x ∈ Di,

while for each y ∈ Dj ,

Finally, after completing a preset number K of steps, each variable node Xi computes Mi := ∑Xe∈Ni RK e→i and then selects x ∈ Di for which Mi(x) is minimal.

In order to prevent the entries in the messages from growing uncontrollably, it is customary to reduce from each entry in each message Qk+1 i→e , where e = (Xi,Xj), the value αk+1 i,j := (∑x∈Di Qk+1 i→e (x))/|Di| or αk+1 i,j := minx∈Di Qk+1 i→e (x). (The latter option ensures that all message entries always remain nonnegative.)

3 The P-Max-Sum algorithm

It can be shown that a na¨ıve execution of MAX-SUM may reveal private information. For example, assume that agent Ai is the only neighbor of agent Aj. The function e between them is represented by the node Xe and the messages Rk e→i include costs that are derived only from the constraint between them. Thus, Ai can learn that Aj has no other neighbors. In case Aj has additional neighbors, the messages Rk e→i include costs of constraints that Aj has with its other neighbors. Thus, Ai may learn information that should not be revealed to it. To avoid such leakage of information, it is imperative to hide from each node Xi (which is controlled by agent Ai) the content of the messages it receives from its neighbors in Ni. To achieve that, any message Qki→e or Rk e→i (where e = (Xi,Xj)) will be split into two random additive shares that will be held by Ai and Aj. Each of these shares, on its own, does not reveal any information on the underlying message. Our secure protocols will take as input those shares, but they will make sure that none of the interacting agents reveal the value of the complementing share so that it remains oblivious of the value of the underlying message. Moreover, the classic MAX-SUM dilemma of "which agent controls the function node Xe?" becomes irrelevant since the operation of Xe will be jointly performed by Ai and Aj .

Let p be a very large integer and let Zp be the additive group modulo p. Then each of the entries in any of the messages Qki→e or Rk e→i will be treated by our secure protocols as an element in Zp. As will be clarified later, p will be of the size of typical moduli of public-key cryptosystems. (Usually, modern public-key cryptography uses moduli of size 1024

bits.) Let c denote an upper bound on the entries of all messages Qki→e and Rk e→i . Applying the procedure described at the end of Section 2.1 usually prevents an overflow from a standard double-precision arithmetic, namely, it guarantees that all entries remain bounded by c = 264 . However, as we work in very large arithmetic size (modulo p), all we need to assume is that all entries in all messages remain bounded by some constant c ≪ p. (So, if log2 p ≈ 1024, we may assume that, say, log2 c ≈ 950.)

Let Xi and Xj be two variable nodes that are connected through a constraint edge e = (Xi, Xj), and let w denote one of the entries in one of the messages that are sent between the corresponding two agents in step k (namely, one of the four messages Qki→e , Rk e→i , Qkj→e , or Rk e→j ). Then the two agents Ai and Aj will engage in a secure protocol that will provide each of them a random element in Zp, denoted si and sj , such that si + sj = w (where all additions hereinafter are modulo p, unless stated otherwise). The sharing procedure will be carried out for all entries in all messages independently (namely, the selection of random shares for one entry will be independent of the selection of shares in other entries, or the selection of shares in the same entry in another synchronous step).

For any 0 ≤ k ≤ K let us denote by M k the set of all messages that are transmitted along the edges of G′ in the kth synchronous step. Eqs. (1)-(3) describe how each of the messages in M k+1 is computed from the messages in M k . Let Xi,Xj be two nodes in V that are connected through an edge e = (Xi, Xj). Then each message Qki→e will be split to two random additive shares as follows:

the first share will be known only to Ai and the second one only to Aj. Similar sharing will be applied to messages that emerge from function nodes; i.e.,

(Recall that the messages and the shares in Eqs. (4) and (5) are vectors in Z|Di| p .)

Now, let Sk denote the set of all shares of M k . Then we should devise a secure computation protocol that will take us from Sk to Sk+1 . In doing so we shall assume that all agents are curious-but-honest. Namely, their honesty implies that they will follow the protocol and will not collude, but they will try to use their legal view in the secure protocols in order to extract private information on constraints of other agents.

We proceed to describe our secure protocols, starting with the initial creation of shares in step k = 0. Then, in the main body of our work, we describe the computation of shares in the progression between successive steps, i.e., the computation of Sk+1 from Sk . Finally, we discuss the secure computation of assignments from the shares that were obtained in the last step.

3.1 Initialization

For k = 0 all messages are zero. To create random shares of all those vectors, every pair of neighboring agents, say Ai and Aj, generate the initial splitting to random shares. To create a splitting as in Eq. (4), Ai and Aj create jointly a random vector S0,i i→e ∈ Z|Di| p , that will be Ai's share, and then they set S0,j i→e = -S0,i i→e as Aj's share. Similar initial splitting will be used for the zero message R0 e→i in Eq. (5).

3.2 Progression

Here we describe the protocols that allow the agents to compute Sk+1 from Sk . We begin with a preliminary discussion about homomorphic encryption and its usage in our protocols.

Using homomorphic encryption

An additive homomorphic encryption is an encryption function E : ΩP → ΩC where ΩP and ΩC are the domains of plaintexts and ciphertexts, respectively, ΩP is an additive group, ΩC is a multiplicative group, and E(x + y) = E(x) · E(y) for all x, y ∈ ΩP . Examples for such ciphers are Benaloh [1994] and Paillier [1999] ciphers.

In our secure protocols we assume that every agent has a public key additive homomorphic cryptosystem. The encryption of messages under the cryptosystem of agent Ai will be denoted Ei, 1 ≤ i ≤ n. It will be used by agents Aj that are constrained with Ai in order to send encrypted messages to Ai; the private decryption key of Ei will be known only to Ai. In addition, we assume that every set of agents of the form A-i := {Aj : 1 ≤ j ≤ n, j ̸= i} has an additive homomorphic cryptosystem, in which the encryption function is denoted Fi. The private key in Fi is known to all agents in A-i (namely, to all agents except for Ai). That encryption will be used by the neighbors of Ai in G in order to convey messages between them. Since the topology of the graph is private, the neighbors of Ai do not know each other and hence they will send those messages through Ai; the encryption will guarantee that Ai cannot recover those messages.

Letting m(Ei) and m(Fi) denote the moduli of Ei and Fi respectively, 1 ≤ i ≤ n, then a good selection of p (the size of the domain Zp in which all shares take value) would be p = min{m(Ei), m(Fi) : 1 ≤ i ≤ n}.

Computing shares in messages that emerge from a variable node

Fix a variable node Xi. As discussed earlier, for each Xe ∈ Ni (namely, a function node adjacent to the variable node Xi in G′ ), Xi needs to send to Xe the vector Qk+1 i→e := ∑Xf∈Ni\{Xe} Rk f→i (see Eq. (1)). Let us denote t := |Ni| and let 1 ≤ j1 < j2 < · · · < jt ≤ n be the indices of all variables that are constrained with Xi so that Ni = {Xeℓ : 1 ≤ ℓ ≤ t}, where eℓ = (Xi,Xjℓ ). Let us concentrate on one of the function nodes adjacent to Xi, say Xe1 . Then

We start by dealing with the case t ≥ 2. In that case, the sum on the right-hand side of Eq. (6) is non-empty. Each of the vectors in the sum on the right-hand side of Eq. (6) is shared between Ai and Ajℓ , 2 ≤ ℓ ≤ t. Therefore, the two shares in Qk+1 i→e1 := Sk+1,i i→e1 + Sk+1,j1 i→e1 (see Eq. (4)) can be computed as follows:

• The share that Ai will get, denoted Sk+1,i i→e1 , is the sum of the t-1 shares that Ai has for the t-1 messages Rk eℓ→i , 2 ≤ ℓ ≤ t. Ai can compute it on its own.
• The share that Aj1 will get, Sk+1,j1 i→e1 , is the sum of the t-1 shares that Aj2 , . . . , Ajt have in step k for the t-1 messages Rk eℓ→i , 2 ≤ ℓ ≤ t. This is done in a secure manner as described in Protocol 1 below.

Protocol 1 describes the process of share generation in messages that emerge from a fixed variable node, Xi. Let Sk,i eℓ→i and Sk,jℓ eℓ→i be the shares that Ai and Ajℓ hold, respectively, in Rk eℓ→i , 1 ≤ ℓ ≤ t. Those shares will be the inputs that Ai and its neighbors Ajℓ , 1 ≤ ℓ ≤ t, bring to Protocol 1. The output to Ai will be the shares Sk+1,i i→eℓ for each 1 ≤ ℓ ≤ t. The output to the neighboring agent Ajℓ , 1 ≤ ℓ ≤ t, will be Sk+1,jℓ i→eℓ , which is the complement share in Qk+1 i→eℓ .

In Steps 1-3 of Protocol 1, all neighbors send to Ai their shares, encrypted with Fi, to prevent Ai from recovering them. (The encryption Fi(·) is applied independently on each of the |Di| components of the share Sk,jℓ eℓ→i .) The subsequent loop in Steps 4-8 describes the interaction of Ai vis-a-vis each of the neighboring agents Ajℓ , 1 ≤ ℓ ≤ t. In Step 5, Ai computes its share in Qk+1 i→eℓ . In Step 6, Ai sends to Ajℓ a message Wℓ where, owing to the additive homomorphic property of Fi, Wℓ = Fi(∑1≤ℓ′ ̸=ℓ≤t Sk,jℓ′ eℓ′→i ). Hence, Ajℓ recovers in Step 7 its share Sk+1,jℓ i→eℓ = ∑1≤ℓ′ ̸=ℓ≤t Sk,jℓ′ eℓ′→i as required.

Protocol 1 Computing shares in messages that emerge from a variable node

• 1: for ℓ = 1, . . . , t do
• 2: Ajℓ sends to Ai the encryption of its share Fi(Sk,jℓ
• eℓ′→i ) and sends it to
• eℓ→i ). 3: end for 4: for ℓ = 1, . . . , t do 5: Ai computes Sk+1,i i→eℓ ← ∑1≤ℓ′̸=ℓ≤t Sk,i eℓ′ →i . 6: Ai computes Wℓ := ∏1≤ℓ′̸=ℓ≤t Fi(Sk,jℓ′ Ajℓ . 7: Ajℓ sets Sk+1,jℓ i→eℓ ←F -1 i (Wℓ). 8: end for

Note that if the graph topology was not private, then each of the neighbors Ajℓ of Ai could have obtained its share Sk+1,jℓ i→eℓ if all other neighboring agents of Ai would have sent their shares directly to Ajℓ , in the clear, without involving Ai. However, such a course of action would reveal to each neighbor of Ai the entire neighborhood of Ai. The solution that we suggest here hides the topology by using Ai as a proxy for those messages. Using encryption hides the content of the sent shares from Ai. Using homomorphic encryption allows Ai to perform the computation in Step 6 and then send to Ajℓ just a single message. Without the homomorphic property Ai would have needed to send all t - 1 messages to Ajℓ , thus revealing to Ajℓ the number of Ai's neighbors.

We now attend to the case where t = 1. In such a case Qk+1 i→e1 is zero. Here, Steps 1-3 are redundant (but are still carried out in order to hide fromAj1 the fact that it is the single neighbor of Ai). Then, instead of Step 5 in Protocol 1, Ai will generate a new random share for itself, denoted Sk+1,i i→e1 . Then, in Step 6, Ai will set W1 := Fi(-Sk+1,i i→e1 ). Hence, Aj1 will recover in Step 7 the share Sk+1,j1 i→e1 = -Sk+1,i i→e1 as required, obliviously of the fact that t = 1.

In view of the discussion at the end of Section 2.1, Protocol 1 must be augmented by a post-processing procedure in which every pair of neighbors Ai and Aj compute αk+1 i,j and then Aj decreases αk+1 i,j from its share Sk+1,j i→e . We omit the details of that procedure due to lack of space.

Computing shares in messages that emerge from a function node

Fix a function node Xe, where e = (Xi,Xj). Eqs. (2)-(3) describe the messages emerging from Xe. Those messages consist of |Di|+|Dj | scalars, that Ai and Aj have to share between themselves. Let us concentrate on one of those scalars, say Rk+1 e→i (x) for some x ∈ Di. The secure multiparty problem that Ai and Aj are facing is as follows: if sk,i (y) and sk,j (y) are the two scalar additive shares that Ai and Aj hold in Qkj→e (y), for some y ∈ Dj, then they need to get two random additive shares sk+1,i (x) and sk+1,j (x) so that

where all additions are modulo p, but when computing the minimum in Eq. (7), the numbers in the brackets are viewed as nonnegative integers.

Such computations can be carried out with perfect privacy using Yao's garbled circuit protocol [Yao, 1982]. However, implementing Yao's protocol for each entry in each transmitted message emerging from a function node in each of the algorithm's steps is impractical due to the hefty computational toll of that protocol. Therefore, we proceed to describe a much simpler and more efficient protocol that Ai and Aj can execute for carrying out the same secure computation. Protocol 2, which we describe below, is not perfectly secure as it leaks some excessive information. But, as we argue later on, that excessive information is benign and of no practical use; on the other hand, the gain in efficiency (in comparison to a solution that relies on Yao's garbled circuit protocol) is enormous since choosing Protocol 2 makes the difference between a theoretical solution and a practical one.

Protocol 2 Computing shares in messages that emerge from a function node

• 1: Ai sends to Aj the value Ei(sk,i (y)) for all y ∈ Dj.
• 2: Aj selects uniformly at random a scalar integer r ∈ [0, p-c-1].
• 3: Aj computesW(y) := Ei(sk,i (y))·Ei(Ci,j(x, y)+sk,j (y)+r) for all y ∈ Dj .
• 4: Aj sends a permutation of {W(y) : y ∈ Dj} to Ai.
• 5: Ai computes E -1 i (W(y)) = Ci,j(x, y)+sk,i (y)+sk,j (y)+r for all y ∈ Dj .
• 6: Ai computes w :=miny∈Dj E -1 i (W(y)).
• 7: Ai generates a random share for itself sk+1,i (x) ∈ Zp.
• 8: Ai sends to Aj the value w′ = w- sk+1,i (x).
• 9: Aj computes sk+1,j (x) = w′ - r.

In Step 1 of Protocol 2, Ai sends to Aj an encryption of its share sk,i (y) for all y ∈ Dj. It uses its own encryption function Ei so that Aj will not be able to recover Ai's private shares. However, as Ei is homomorphic, Aj can perform the needed arithmetics on the received shares.

In Step 2, Aj selects at random a masking scalar r ∈ [0, p-c-1] which will be used to protect private information from Ai, as we shall see shortly. (Recall that c is a publicly known upper bound on all entries in all messages.) Then, the computation in Step 3 results, for each y ∈ Dj, in a value W(y) that equals Ei(w(y)) where

owing to the additive homomorphism of Ei. Since sk,i (y) + sk,j (y) = Qkj→e (y), the value of w(y) in Eq. (8) equals the corresponding argument in the minimum on the right-hand

shifted by the random mask r. In Step 4, Aj sends all W(y), y ∈ Dj, to Ai but it randomly permutes them so that Ai will not be able to associate any value of W(y) to any assignment y ∈ Dj. After Ai decrypts the received values it recovers in Step 5 all values w(y), y ∈ Dj .

Let us now examine w(y). As discussed above, it equals m(y) + r. Since m(y) is an integer in the range [0, c] (by our assumption) and as r ∈ [0, p - c - 1], then w(y) equals m(y) + r, where the sum is in the usual sense of a sum of integers. Namely, even though all sums in our discussion are sums modulo p, in this particular case, the equality holds in the stronger sense of sum of integers. Hence, miny∈Dj [m(y) + r], which is the value w that Ai computes in Step 6, equals r +miny∈Dj m(y) (where, again, the latter sum is a regular sum of integers, and not just a modular sum). Next, Ai generates for itself a random share sk+1,i (x) ∈ Zp (Step 7) and sends to Aj the value w′ = w - sk+1,i (x) (Step 8), where the subtraction is modulo p. Finally, Aj computes its share in Step 9, sk+1,j (x) = w′ - r, where once again the subtraction is modulo p. As a result, Ai and Aj end up with random shares, sk+1,i (x) and sk+1,j (x) respectively, whose sum modulo p equals miny∈Dj m(y), as required.

We now turn to discuss the privacy provided by Protocol 2. The only information that Aj receives in the course of the protocol is the encryption of Ai's shares by Ei. Assuming that Ei is based on a strong key, then Protocol 2 provides computational privacy against Aj. As for Ai, it gets all values m(y) + r, y ∈ Dj. The usage of the random shift r ensures that in very high probability, 1 - 2c p-c , Ai can learn absolutely no information on m(y), while in probability 2c p-c it may learn either a lower or an upper bound on m(y) for some y ∈ Dj. (We omit further discussion here; the interested reader is referred to [Tassa and Bonchi, 2014, Theorem 4.1].) In addition, the usage of the secret permutation, which Aj selects, prevents Ai from associating any value of m(y)+r to any particular y ∈ Dj . However, Ai may sort the values m(y)+r in a non-decreasing order and find the correct differences between consecutive entries in the corresponding ordering ofm(y). In addition, it may compute any function of those differences, such as the variance of the sequence m(y). We consider this leakage of information completely benign, and certainly a modest price to pay for a fully practical secure implementation of this part of the P-MAX-SUM algorithm.

3.3 Termination

After completing K iterations, the sum of the last incoming messages from all function nodes that are adjacent to Xi is Mi := ∑tℓ=1 RK eℓ→i (recall that Ni = {Xeℓ : 1 ≤ ℓ ≤ t}, where eℓ = (Xi,Xjℓ )). Then, Ai needs to assign Xi the value xi for which the corresponding entry in Mi is minimal. RK eℓ→i = SK,i eℓ→i + SK,jℓ eℓ→i where SK,i eℓ→i is held by Ai and SK,jℓ eℓ→i is held by Ajℓ . We proceed to describe Protocol 3 that performs that computation securely.

In Steps 1-3, all agents that are connected to Ai send to it an Fi-encryption of their share in the last message sent from their respective function node to Xi. Then, in Step 4, Ai selects a random masking scalar r ∈ [0, p - c - 1], defines Sr = (r, . . . , r) ∈ Z|Di| p , and computes

Owing to the homomorphic property of Fi, the vector ˆM equals Fi(Sr +∑tℓ=1 SK,jℓ eℓ→i +∑tℓ=1 SK,i eℓ→i ) = Fi(Sr +Mi), where Mi is as defined above. In Steps 5-6, Ai sends a secret and random permutation of the entries of ˆM to one of its neighbors who proceeds to decrypt it and notify Ai of the index h in which a minimum was obtained. Finally (Step 7), Ai assigns to Xi the value x ∈ Di in which Sr +Mi (and consequently also Mi) was minimal.

We omit a discussion of the privacy of Protocol 3 due to space limitations.

Protocol 3 Computing the best assignment for Xi

• 1: for ℓ = 1, . . . , t do
• 2: Ajℓ sends to Ai the encryption of its share Fi(SK,jℓ eℓ→i ).
• 3: end for
• 4: Ai selects Sr = (r, . . . , r) ∈ Z|Di| p , where r ∈ [0, p - c - 1], and computes ˆM = Fi(Sr) · ∏tℓ=1 Fi(SK,jℓ eℓ→i ) · Fi(∑tℓ=1 SK,i eℓ→i ).
• 5: Ai selects a secret random permutation π on Di and sends π( ˆM) to Aj1 .
• 6: Aj1 decrypts the entries of the received vector and informs Ai of the index h of the minimal entry.
• 7: Ai assigns to Xi the value that was mapped by π to h.

4 Privacy analysis (overview)

Our proposed algorithm preserves three types of privacy: topology privacy (by using the homomorphic encryption functions Fi), constraint privacy, and assignment/decision privacy (by using the homomorphic encryption functions Ei, secret sharing, random maskings and random permutations). In the version presented in the paper, the algorithm does not preserve agent privacy due to the need for generating the private keys in the encryption functions Fi. This problem can be resolved by the use of a trusted coordinator that intervenes only in the initialization stage. Each agent Ai will tell the coordinator who are its neighbors. The coordinator can then create key pairs for Fi and send them to all of Ai's neighbors, for all 1 ≤ i ≤ n.

There exist several complete privacy-preserving DCOP algorithms. While there is no point to compare their efficiency to that of P-MAX-SUM (for obvious scaling problems of complete algorithms), it is interesting to observe their privacy features. The algorithm P-SyncBB [Grinshpoun and Tassa, 2014] preserves constraint and topology privacy, but not agent or decision privacy. As for the study of L´eaut´e and Faltings [2013], they presented a sequence of three privacypreserving versions of DPOP: P-DPOP(+) , P3/2 -DPOP(+) , and P2 -DPOP(+) . All three versions preserve agent privacy and partial topology privacy. The least private and most efficient version, P-DPOP(+) , preserves constraint and decision privacy only partially, as it may leak related information. P3/2 -DPOP(+) preserves decision privacy fully but it still respects constraint privacy only partially. The last version, P2 - DPOP(+) (most private, least efficient), preserves constraint and decision privacy fully.

5 Efficiency analysis

We analyze here the computational cost of P-MAX-SUM. We focus on analyzing the induced cost in the progression steps, since both initialization and termination steps are performed only once. In addition, we count only encryption and decryption operations, since the other performed operations (random numbers' generation, additions, multiplications, and computing minima) have computational costs which are few orders of magnitude smaller than those of the cryptographic operations. Let us fix an agent Ai and assume that it has t neighboring agents. Let us also denote the costs of encryption and decryption by Ce and Cd, respectively. Finally, let ˆ d := max1≤j≤n |Dj| denote the size of the largest variable domain. Then, Protocol 1 involves t concurrent encryptions (Steps 1-3) followed by t non-concurrent decryptions (Step 7). Hence, the non-concurrent runtime of Protocol 1 for Ai in any given synchronous step is Ce + tCd. As for Protocol 2, Ai has to run it vis-a-vis each of its neighbors. In Step 1 it performs up to ˆ d encryptions vis-a-vis each of its t neighbors. Hence, the non-concurrent runtime of that step is bounded by t ˆ dCe. Then, in Step 3 all neighboring agents have to performup to ˆ d encryptions, concurrently. Finally, Step 5 entails up to t ˆ d non-concurrent decryptions. Hence, the overall nonconcurrent runtime for Ai due to Protocol 2 in any given step is bounded by (t + 1) ˆ dCe + t ˆ dCd. Letting ˆ t denote the maximal degree of a node in the graph G, we conclude that the overall runtime of the P-MAX-SUM algorithm is (roughly) bounded by (Ce · [(ˆ t + 1) ˆ d+1] +Cd · ˆ t( ˆ d + 1)) ·K, where K is the number of synchronous steps.

We note that the runtime of P-MAX-SUM is independent of n, the number of agents. However, it does depend on the maximal degree of a node in the constraint graph.

To realize the actual time it will take P-MAX-SUM to run we followed the simulated time approach [Sultanik et al., 2008] by measuring the time of atomic operations performed in the algorithm and then counting the non-concurrent times these operations are performed. We measured the runtimes of the encryption and decryption operations by averaging multiple runs of the common Java implementation of the Paillier cryptosystem 1 on a hardware comprised of an Intel i7-4600U processor and 16GB memory. Our tests show that Ce takes at most 2 msec, while Cd takes at most 3 msec.

There are a number of indications that MAX-SUM performs best in the first few iterations of its run [Zivan and Peled, 2012; Zivan et al., 2014]. The experiments presented by Zivan et al. [2014] indicate this phenomenon on various benchmarks. We reproduced these experiments to investigate the number of iterations required for MAX-SUM to find a solution of high quality on realistic and structured benchmarks, where privacy is expected to be important, as well as on uniform random problems.

The results were conclusive. The best solutions for relatively large graph coloring problems (including 100 agents, three colors in each domain and constraint density of 0.05) and meeting scheduling problems (including 90 agents, 20 meetings among them) 2 were found within the first 5 and 10 iterations, respectively. Thus, all iterations following the tenth iteration in each run were redundant. For uniform random problems, the average result was also the best after a small number of iterations. However, occasionally, the exploration in further iterations revealed higher quality solutions. That been said, the fact that MAX-SUM is not guaranteed to converge indicates the need for the use of the anytime framework as proposed by Zivan et al. [2014]. The privacy preserving methods presented in this paper can be used to generate a private version of the anytime framework. A comprehensive discussion of those issues is delayed to the full version of this paper due to space limitations.

Considering the limited number of needed iterations along with the overhead of its cryptographic operations, P-MAXSUM needs at most a few seconds to complete the run of a large-scale structured or realistic problem. For instance, a graph coloring problem with 100 agents takes about 0.5 seconds, while a common meeting scheduling problem takes about 5 seconds. Such running times are clearly acceptable considering the privacy preservation requirement.

A detailed efficiency analysis (computational and communication costs), comparing P-MAX-SUM to the original nonprivate MAX-SUM algorithm, is omitted due to space limitations.

6 Conclusion

One of the most important motivations for solving a problem distributively is preserving the privacy of agents. Therefore, a number of recent studies proposed private versions of existing DCOP-solving algorithms. Yet, no such study was based on the MAX-SUM algorithm, which has recently been in the focus of both algorithmic and applicative DCOP research.

1 http://www.csee.umbc.edu/∼kunliu1/research/Paillier.html

2 For more details on the setup see [Zivan et al., 2014].

In this paper we proposed P-MAX-SUM, a privacypreserving version of MAX-SUM. The proposed algorithm preserves topology, constraint and assignment/decision privacy. It may be enhanced to preserve also agent privacy by issuing a single call to a trusted coordinator.

In future work we shall extend P-MAX-SUM so that it handles non-binary constraints. We also plan to devise similar privacy-preserving versions to extensions of MAX-SUM, e.g., BOUNDED-MAX-SUM [Rogers et al., 2011] and MAXSUM ADVP [Zivan and Peled, 2012].