[Resource Topic] 2004/009: Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness

Welcome to the resource topic for 2004/009

Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness

Authors: Juan A. Garay, Philip MacKenzie, Ke Yang


We study the problem of constructing secure multi-party computation
(MPC) protocols that are {\em completely fair} — meaning that either
all the parties learn the output of the function, or nobody does —
even when a majority of the parties are corrupted. We first propose a
framework for fair multi-party computation, within which we formulate
a definition of secure and fair protocols. The definition follows the
standard simulation paradigm, but is modified to allow the protocol to
depend on the runing time of the adversary. In this way, we avoid a
well-known impossibility result for fair MPC with corrupted majority;
in particular, our definition admits constructions that tolerate up to
(n-1) corruptions, where n is the total number of parties. Next,
we define a commit-prove-fair-open'' functionality and construct an efficient protocol that realizes it, using a new variant of a cryptographic primitive known as time-lines.‘’ With this
functionality, we show that some of the existing secure MPC protocols
can be easily transformed into fair protocols while preserving their
Putting these results together, we construct efficient, secure MPC
protocols that are completely fair even in the presence of corrupted
majorities. Furthermore, these protocols remain secure when
arbitrarily composed with any protocols, which means, in particular,
that they are concurrently-composable and non-malleable. Finally, as
an example of our results, we show a very efficient protocol that
fairly and securely solves the socialist millionaires’ problem.

ePrint: https://eprint.iacr.org/2004/009

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 .