  As large-scale theft of data from corporate servers is becoming increasingly
common, it becomes interesting to examine alternatives to the paradigm of
centralizing sensitive data into large databases. Instead, one could use
cryptography and distributed computation so that sensitive data can be supplied
and processed in encrypted form, and only the final result is made known. In
this paper, we examine how such a paradigm can be used to implement constraint
satisfaction, a technique that can solve a broad class of AI problems such as
resource allocation, planning, scheduling, and diagnosis. Most previous work on
privacy in constraint satisfaction only attempted to protect specific types of
information, in particular the feasibility of particular combinations of
decisions. We formalize and extend these restricted notions of privacy by
introducing four types of private information, including the feasibility of
decisions and the final decisions made, but also the identities of the
participants and the topology of the problem. We present distributed algorithms
that allow computing solutions to constraint satisfaction problems while
maintaining these four types of privacy. We formally prove the privacy
properties of these algorithms, and show experiments that compare their
respective performance on benchmark problems.
