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.