## CryptoDB

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

Authors: Juan A. Garay Philip MacKenzie Ke Yang URL: http://eprint.iacr.org/2004/009 Search ePrint Search Google 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 security. 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.
##### BibTeX
@misc{eprint-2004-11985,
title={Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness},
booktitle={IACR Eprint archive},
keywords={Foundations, cryptographic protocols.},
url={http://eprint.iacr.org/2004/009},
note={ garay@research.bell-labs.com 12430 received 13 Jan 2004},
author={Juan A. Garay and Philip MacKenzie and Ke Yang},
year=2004
}