International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Marius-Calin Silaghi
Download:
URL: http://eprint.iacr.org/2004/333
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12297,
  title={Secure Multi-party Computation for selecting a solution according to a uniform distribution over all solutions of a general combinatorial problem},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols /},
  url={http://eprint.iacr.org/2004/333},
  note={ msilaghi@cs.fit.edu 12751 received 29 Nov 2004},
  author={Marius-Calin Silaghi},
  year=2004
}