Secure DisCSP Protocols   From Centralized Towards Distributed Solutions
Kobbi Nissim and Roie Zivan

Abstract

We present protocols for secure distributed constraint satisfaction problems (DisCSPs). Our first protocol is a centralized protocol, where two of the agents collect  encrypted  data from all other parties, and obliviously run a heuristic. Our protocol does not introduce new servers into the computation, and elimi-nates information leakage to all agents. We demonstrate how to modify our pro-tocol to accomodate some non-trivial heuristics such as backjumping techniques and ordering heuristics. Our second protocol is a distributed protocol, where all agents participate in solving the DisCSP. It forms an alternative network whose nodes are small groups (e.g. pairs) of agents from the original DisCSP. Each such group obliviously perform the roles of all its members in the search algorithm. We also discuss a hybrid solution that combined the centralized and distributed protocols. We Further discuss sources of information leakages in both scenarios, and suggest how to eliminate or diminish them.