Welcome to the resource topic for 2004/333
Title:
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
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.
ePrint: https://eprint.iacr.org/2004/333
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .