We know no arithmetic circuit proposed in the past, selecting a single solution according to a uniform distribution over all solutions of a general constraint satisfaction problem. The only one (we) are able to design has a factorial complexity in the size of the search space (O(d^m!d^m) multiplications of secrets), where m is the number of variables and d the maximal size of a variable's domain.
Nevertheless, we were able to develop a methodology combining secure arithmetic circuit evaluation and mix-nets, able to compile the problem of selecting a random solution of a CSP to a n/2-private multi-party computation assuming passive attackers. The complexity of this solution is more acceptable, O(d^m) multiplications, being therefore applicable for some reasonable problems, like meeting scheduling.
Constraint satisfaction is a framework extensively used in some areas of artificial intelligence to model problems like meeting scheduling, timetabling, the stable marriages problem, and some negotiation problems. It is based on abstracting a problem as a set of variables, and a set of constraints that specify unacceptable combination of values for sets of distinct variables.
Category / Keywords: cryptographic protocols / Date: received 29 Nov 2004 Contact author: msilaghi at cs fit edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20041202:194344 (All versions of this report) Short URL: ia.cr/2004/333 Discussion forum: Show discussion | Start new discussion