**Secure Multi-party Computation for selecting a solution according to a uniform distribution over all solutions of a general combinatorial problem**

*Marius-Calin Silaghi*

**Abstract: **Secure simulations of arithmetic circuit and boolean circuit
evaluations are known to save privacy while providing solutions to any
probabilistic function over a field. The problem we want to solve is
to select a random solution of a general combinatorial problem. Here
we discuss how to specify the need of selecting a random solution of a
general combinatorial problem, as a probabilistic function. Arithmetic
circuits for finding the set of all solutions are simple to
design.

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

[ Cryptology ePrint archive ]