Abstract
This paper presents a privacy-preserving protocol for the distributed graph coloring problem. By integrating homomorphic encryption and secure multi-party computation (SMPC) with the Tabucol meta-heuristic, the proposed Privacy Preserving Tabu Search (PPTS) allows multiple parties to collaboratively find near-optimal colorings for a shared graph without revealing local constraints or color assignments. We introduce a "synchronous move" heuristic to mitigate inference attacks that arise from observing changes in conflict counts. Experimental results on synthetic graphs demonstrate that PPTS achieves solution quality comparable to centralized algorithms with manageable computational overhead.
Introduction
Graph coloring is a fundamental NP-hard combinatorial optimization problem with wide-ranging applications in resource allocation, such as radio frequency assignment and job scheduling. In a standard setting, a central authority possesses the entire graph and assigns colors to vertices such that no two adjacent vertices share the same color. However, many real-world scenarios involve distributed data where multiple parties—such as Alice, Bob, and Carol—each own a subset of vertices and their internal conflicts, while also sharing "external" edges with other parties.
The primary challenge addressed in this research is finding a valid $k$-coloring without any party revealing their internal graph structure or final color assignments to others. Centralizing this data poses significant privacy risks, yet standard cryptographic approaches for NP-hard problems are often computationally prohibitive.
Methodology: Privacy-Preserving Tabu Search (PPTS)
The authors propose a protocol named PPTS (Privacy Preserving Tabu Search), built upon the Tabucol meta-heuristic. The protocol enables distributed parties to iteratively improve a coloring through three core components:
1. Secure Conflict Computation
To evaluate a potential color change, parties must calculate the total number of conflicting edges, $\mu(x)$. While internal conflicts are counted locally, external conflicts (edges spanning different parties) are computed using a Secure Scalar Product protocol. This utilizes the Paillier cryptosystem, an additively homomorphic scheme that allows parties to sum conflicts without exposing specific edge existence or color data.
2. Secure Comparison
To decide whether to accept a move, the protocol must determine if a new conflict count is lower than the previous one. This is achieved via FairplayMP, an implementation of Yao’s Garbled Circuits, which securely compares partitioned shares of conflict counts without revealing the absolute values.
3. Synchronous Moves
The authors identify a potential inference attack where a single vertex color change might reveal information about a neighbor's state if the total conflict count changes predictably. To mitigate this, they introduce "synchronous moves," where two parties update colors simultaneously, effectively anonymizing the resulting change in the global conflict count.
Experimental Evaluation
The PPTS protocol was evaluated using synthetically generated random graphs with vertex counts ($N$) ranging from 100 to 1000 and densities ($\rho$) between 2% and 30%. The graphs were partitioned among 10 simulated parties.
Key results include:
- Accuracy: PPTS consistently achieved chromatic numbers comparable to the centralized, non-private Tabucol algorithm across various graph sizes and densities.
- Efficiency: While cryptographic overhead is present, the runtime remains feasible for offline applications. For instance, a 1000-vertex graph with 20% density was solved in approximately 30 hours. While slower than non-private methods, this is practical for high-stakes scheduling tasks.
- Scalability: Communication complexity scales at $O(cn^2\ell)$ for scalar products and $O(cm\ell)$ for comparisons, where $n$ is the number of vertices and $m$ is the number of parties.
Conclusion and Future Work
This research demonstrates that combining well-known heuristics with Secure Multi-Party Computation (SMPC) can yield practical solutions for complex, distributed optimization problems. A significant contribution is the recognition that the output of an algorithm can itself be a leakage vector, addressed here through algorithmic "synchronous moves." While some minor information regarding "border" vertices remains exposed, the protocol successfully hides internal edges and final schedules. Future work may explore alternative data partitioning strategies and the application of similar privacy-preserving wrappers to other meta-heuristics like Simulated Annealing or Genetic Algorithms.
Summary updated