Hiding Absence of Solution for a Distributed Constraint Satisfaction Problem

All Papers

A distributed constraint satisfaction problem (DisCSP) is defined by a set of agents, trying to find assignments for a set of variables with known domains and subject to secret constraints. They can model applications like auctions, distributed team-making, scheduling, and configuration. Secure multiparty computations (MPC) can pick and reveal randomly one of the solutions of any distributed constraint satisfaction and optimization problem. Our previous algorithms are based on an arithmetic circuit for selecting a random element out of the elements with a given value in a secret array. Here we show an improvement based on a very simple and elegant (optimized) version of the involved functions and on the usage of CSP solvers to exploit public constraints. The technique can hide the absence of solutions.