Securely Solving the Distributed Graph Coloring Problem

Yuan Hong, Jaideep Vaidya, Haibing LuarXiv 2018 · arXiv

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.

Distributed views of a 3-colored graph among Alice, Bob, and Carol.

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.

The partitioned adjacency matrix representation used for secure conflict computation.

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

Abstract

Combinatorial optimization is a fundamental problem found in many fields. In many real life situations, the constraints and the objective function forming the optimization problem are naturally distributed amongst different sites in some fashion. A typical approach for solving such problem is to collect all of this information together and centrally solve the problem. However, this requires all parties to completely share their information, which may lead to serious privacy issues. Thus, it is desirable to propose a privacy preserving technique that can securely solve specific combinatorial optimization problems. A further complicating factor is that combinatorial optimization problems are typically NP-hard, requiring approximation algorithms or heuristics to provide a practical solution. In this paper, we focus on a very well-known hard problem -- the distributed graph coloring problem, which has been utilized to model many real world problems in scheduling and resource allocation. We propose efficient protocols to securely solve such fundamental problem. We analyze the security of our approach and experimentally demonstrate the effectiveness of our approach.
BibTeX
@misc{hong2018securely,
  author = {Yuan Hong and Jaideep Vaidya and Haibing Lu},
  title = {{Securely Solving the Distributed Graph Coloring Problem}},
  year = {2018},
  eprint = {1803.05606},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.05606},
}
Figure