Meeting Scheduling Guaranteeing n/2-Privacy and Resistant to Statistical Analysis (Applicable to any DisCSP)
Marius Calin Silaghi · 2004
Distributed problems raise privacy issues. The user would like to specify securely his constraints (desires, availability, money) on his computer once. The computer is expected to compute and communicate for searching an acceptable solution while maintaining the privacy of the user. Even without computers infested with spy viruses that capture the interaction with the user, most agent based approaches reveal parts of one agent’s secret data to its partners in distributed computations [7]. Some cryptographic multi-party computation protocols [1] succeed to avoid leaking secrets at the computation of some functions with private inputs. They have been applied to find the set of all solutions for the meeting scheduling problem [3]. However, nobody yet succeeded to apply those techniques for finding a random solution to the meeting scheduling problem. Note that revealing all solutions, when you only need a single one, leaks a lot of data about when others are, or are not, available. Some answers were proposed in our previous approaches to distributed constraint problems [4]. They guarantee that no agent can infer with certitude a secret from the identity of the solution of the problem (other than the acceptance of the solution), but guarantee nothing about inference of probabilistic information about secrets. Our new technique answers this problem, too. 1.