TL;DR
This paper introduces PC-SyncBB, the first algorithm for Distributed Constraint Optimization Problems (DCOPs) that is secure against coalitions of agents, assuming an honest majority. It builds upon the classical SyncBB algorithm to provide constraint, topology, and decision privacy, even when a subset of agents collude.
What Problem Does This Paper Address?
Distributed Constraint Optimization Problems (DCOPs) are used to model real-world scenarios where multiple agents need to coordinate to solve an optimization problem, with each agent controlling a subset of variables and constraints. A significant challenge in DCOPs is privacy: agents want to solve the problem without revealing sensitive information about their variables, constraints, or decisions to other agents. While previous research has developed privacy-preserving DCOP algorithms, they generally assume that agents act independently. This paper addresses the critical gap of collusion, where a group of agents might combine their knowledge to infer private information about other agents. The authors aim to create a DCOP algorithm that remains secure even if a subset of agents (less than half) colludes.
Methods
The core of this work is the PC-SyncBB algorithm, a secure implementation of the Synchronous Branch and Bound (SyncBB) algorithm. PC-SyncBB achieves privacy through a combination of techniques:
- Secure Multi-Party Computation (MPC): This is the backbone for ensuring privacy. PC-SyncBB heavily relies on MPC sub-protocols, particularly for comparing the current partial assignment's cost to the global upper bound (
compare_CPA_cost_to_upper_bound). This sub-protocol is based on the work of Ben-Efraim and Omri [2017] and is designed to be secure against coalitions of less than half the agents. - Additive Shares: To protect constraint and decision privacy, costs and upper bounds are broken down into additive shares distributed among agents. For instance, the cost of a constraint between agents $A_t$ and $A_k$ is split into shares $sCPA_k(t)$ and $sCPA_t(k)$ such that their sum (modulo a large number $S$) equals the actual constraint cost. This ensures no single agent knows the full cost.
- Randomized Value Ordering: Each agent generates a random ordering ($w_k$) of its variable's domain values for each new traversal. This ordering is kept secret, contributing to decision privacy by obscuring the exact order in which an agent explores its options.
- Paillier Cryptography: The
update_shares_in_CPAsub-protocol uses Paillier encryption to securely update the additive shares. This allows agents to compute their share of a constraint cost without revealing their specific value assignment to the other agent involved in the constraint.
What's novel is the integration of these MPC and cryptographic techniques to specifically counter collusion, a threat not addressed by prior privacy-preserving DCOP algorithms. Unlike previous methods that might be vulnerable to even two colluding agents, PC-SyncBB aims for robustness against larger coalitions.
Datasets
The paper evaluates PC-SyncBB on two types of benchmarks:
- Unstructured randomly generated DCOPs: These are used to test the algorithm's performance across varying constraint densities and numbers of agents.
- Distributed 3-color graph coloring problems: This represents a more structured benchmark where constraint matrices are diagonal, and costs are random.
No new datasets were introduced; existing DCOP benchmarks were used.
Key Insights and Ideas
- Collusion is a real threat: The paper highlights that assuming agents act in isolation is a significant limitation in privacy-preserving DCOP research, and addressing collusion is crucial for practical applications.
- MPC is essential for coalition-secure DCOPs: The authors demonstrate that achieving security against coalitions necessitates the use of sophisticated secure multi-party computation techniques, particularly for critical operations like cost comparison.
- Trade-off between privacy and performance: The experimental results clearly show that enhancing privacy, especially against collusion, comes at a significant computational cost, increasing runtime by orders of magnitude compared to non-private or less secure algorithms.
- Honest majority assumption is key: The security against coalitions is predicated on the assumption that the colluding agents constitute less than half of the total number of agents. This is a common assumption in MPC literature for achieving security.
Key Results
- Feasibility for moderately-sized problems: PC-SyncBB is shown to be feasible for moderately-sized DCOP instances.
- Significant runtime overhead: The "online" phase of PC-SyncBB (which includes the MPC computations) is about an order of magnitude slower than P-SyncBB (a privacy-preserving algorithm without collusion resistance). The overall PC-SyncBB runtime is two orders of magnitude higher than the non-private SyncBB.
- Scalability challenges: The runtime of the
compare_CPA_cost_to_upper_boundsub-protocol, a core component, grows with the number of agents and the complexity of the MPC circuit. This is a primary bottleneck for scalability. - Constraint density has minor impact: Varying constraint density had a relatively small effect on runtime for random DCOPs.
- Number of agents has a major effect: As expected for Branch & Bound algorithms, the number of agents significantly impacts performance, with runtimes increasing substantially.
Limitations and Future Work
- Scalability bottleneck: The primary limitation acknowledged is the scalability of the
compare_CPA_cost_to_upper_boundsub-protocol, which relies on a general-purpose MPC protocol. Future work aims to explore more efficient MPC constructions. - Limited coalition size: The algorithm's security is guaranteed only for coalitions smaller than half the agents. Extending this to larger or even malicious coalitions is a future research direction.
- Need for more efficient implementations: The authors emphasize the need for more efficient privacy-preserving implementations of other DCOP algorithms, especially inference-based and incomplete ones, to improve scalability.
- Perfect privacy vs. practicality: The paper notes that achieving perfect privacy in MPC is theoretically possible but practically challenging. The current approach accepts benign information leakages for the sake of practicality, a common trade-off in the field.
Summary updated