Cryptology ePrint Archive: Report 2004/333

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)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]