Paper 2004/009

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

Juan A. Garay, Philip MacKenzie, and 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 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Foundationscryptographic protocols.
Contact author(s)
garay @ research bell-labs com
2004-01-14: received
Short URL
Creative Commons Attribution


      author = {Juan A.  Garay and Philip MacKenzie and Ke Yang},
      title = {Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness},
      howpublished = {Cryptology ePrint Archive, Paper 2004/009},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.