Max-Sum Goes Private

Tamir Tassa, Roie Zivan, Tal GrinshpounIJCAI 2015

Abstract

Distributed Constraint Optimization Problems (DCOPs) provide a powerful framework for coordinating agents in decentralized systems. However, standard DCOP algorithms often require agents to exchange messages that reveal sensitive information, including network topology, local constraint costs, and final assignments. This paper, originally presented at IJCAI 2015, introduces P-MAX-SUM, the first privacy-preserving version of the popular Max-Sum algorithm. By integrating additive secret sharing and homomorphic encryption, P-MAX-SUM ensures robust privacy while maintaining the scalability and performance characteristics that make Max-Sum attractive for large-scale multi-agent systems.

1. Introduction

In a DCOP, a group of agents must coordinate to assign values to variables such that a global cost function—defined by local constraints between neighboring agents—is minimized. While the decentralized nature of DCOPs suggests a level of privacy, standard algorithms are often "chatty," leaking three critical types of information:

  1. Topology Privacy: The structure of the constraint graph (who is connected to whom).
  2. Constraint Privacy: The specific utility or cost values associated with different variable assignments.
  3. Assignment Privacy: The final values chosen by agents.

While previous research has addressed privacy in complete DCOP algorithms, these solutions often suffer from high computational complexity. P-MAX-SUM fills this gap by securing the high-performance, "incomplete" Max-Sum algorithm.

2. The P-MAX-SUM Framework

The authors construct P-MAX-SUM using two primary cryptographic building blocks designed to balance security with computational efficiency.

2.1 Cryptographic Primitives

  • Additive Secret Sharing: Messages are split into two random shares ($s_i$ and $s_j$) such that their sum equals the original value. This ensures that no single agent can reconstruct the actual message content.
  • Additive Homomorphic Encryption (HE): Using systems like Paillier encryption, agents can perform additions on encrypted data without decryption. In P-MAX-SUM, HE allows agents to act as proxies for their neighbors' messages, effectively masking the network topology.

2.2 Protocol Phases

The algorithm operates in three distinct phases:

  1. Initialization: Agents establish keys and generate initial random shares for their local constraints.
  2. Progression (Min-Sum Logic): This core phase implements the iterative message-passing logic. To find the minimum of a sum without revealing individual components, agents use a masking and permutation protocol. One agent adds a random "mask" and permutes the options before sending them to a neighbor for decryption, ensuring the "minimizer" remains ignorant of raw costs and specific assignments.
  3. Termination: A secure selection protocol identifies the optimal assignment for each variable without exposing the total cost distribution to the participating agents.

3. Experimental Evaluation

The authors evaluated P-MAX-SUM using a simulated time approach across several benchmarks, including Graph Coloring (100 agents), Meeting Scheduling (90 agents), and Uniform Random Problems.

3.1 Performance and Scalability

The results demonstrate that P-MAX-SUM maintains practical runtimes despite the cryptographic overhead. A 100-agent graph coloring problem was solved in approximately 0.5 seconds, while a complex 90-agent meeting scheduling problem took roughly 5 seconds.

The runtime of P-MAX-SUM is primarily governed by the maximal degree of nodes in the constraint graph and the domain size, rather than the total number of agents ($n$). This makes the algorithm highly scalable for sparse, large-scale networks.

3.2 Privacy vs. Efficiency Trade-offs

The authors intentionally avoided "perfect" privacy tools like Yao’s Garbled Circuits due to their extreme computational cost. Instead, P-MAX-SUM accepts "benign" leakage—such as the variance of cost values—to achieve runtimes suitable for real-world multi-agent coordination.

4. Conclusion and Future Work

P-MAX-SUM represents a significant step toward practical, private decentralized optimization. By exploiting the fast convergence of the Max-Sum algorithm (often within 5–10 iterations), the authors minimize the impact of cryptographic overhead per round.

Future work includes extending the protocol to handle non-binary constraints and further decentralizing the initialization phase to eliminate the need for a trusted coordinator. Additionally, the authors plan to apply these privacy techniques to other Max-Sum variants, such as Bounded-Max-Sum.

Summary updated

BibTeX
@inproceedings{tassa2015max,
  author = {Tamir Tassa and Roie Zivan and Tal Grinshpoun},
  title = {{Max-Sum Goes Private}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure