FairplayMP: a system for secure multi-party computation

ABSTRACT

We present FairplayMP (for "Fairplay Multi-Party"), a system for secure multi-party computation. Secure computation is one of the great achievements of modern cryptography, enabling a set of untrusting parties to compute any function of their private inputs while revealing nothing but the result of the function. In a sense, FairplayMP lets the parties run a joint computation that emulates a trusted party which receives the inputs from the parties, computes the function, and privately informs the parties of their outputs. FairplayMP operates by receiving a high-level language description of a function and a configuration file describing the participating parties. The system compiles the function into a description as a Boolean circuit, and perform a distributed evaluation of the circuit while revealing nothing else. FairplayMP supplements the Fairplay system [16], which supported secure computation between two parties. The underlying protocol of FairplayMP is the Beaver-Micali-Rogaway (BMR) protocol which runs in a constant number of communication rounds (eight rounds in our implementation). We modified the BMR protocol in a novel way and considerably improved its performance by using the Ben-Or-Goldwasser-Wigderson (BGW) protocol for the purpose of constructing gate tables. We chose to use this protocol since we believe that the number of communication rounds is a major factor on the overall performance of the protocol. We conducted different experiments which measure the effect of different parameters on the performance of the system and demonstrate its scalability. (We can now tell, for example, that running a second-price auction between four bidders, using five computation players, takes about 8 seconds.)

REFERENCES

• 1: D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100287]
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: . Bogetoft, D.L. Christensen, I. Dåmgard, M. Geisler, T. Jakobsen, M. Krøigaard, J.D. Nielsen, J.B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft. Multi-Party Computation Goes Live Cryptology ePrint Archive, Report 2008/068, 2008.
• 4: . Bogetoft, I. Damgård, T. Jakobsen, K. Nielsen, J. Pagter, and T. Toft. A practical implementation of secure auctionsbased on multi-party integer computation. Proc. of Financial Cryptography, LNCS vol. 4107,Springer-Verlag, 2006.
• 5: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 6: . Cramer, I. Damgrd and Y. Ishai. Share conversion, pseudorandom secret-sharing and applications to secure computation. In 2nd TCC, pages 342--362, 2005.
• 7: . Damgård and Y. Ishai. Constant-Round Multi-Party Computation Using a Black-Box Pseudorandom Generator. In Crypto '2005, pp. 378-394, 2005.
• 8: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 9: Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277716]
• 10: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 11: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 12: . Lindell and B. Pinkas. A Proof of Yao's Protocol for Secure Two-Party Computation. To appear in the Journal of Cryptology. Also appeared as Cryptology ePrint Archive, Report 2004/175, 2004.
• 13: Yehuda Lindell , Benny Pinkas, An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries, Proceedings of the 26th annual international conference on Advances in Cryptology, p.52-78, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_4]
• 14: Yehuda Lindell , Benny Pinkas , Nigel P. Smart, Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries, Proceedings of the 6th international conference on Security and Cryptography for Networks, September 10-12, 2008, Amalfi, Italy [doi>10.1007/978-3-540-85855-3_2]
• 15: Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
• 16: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 17: Janus Dam Nielsen , Michael I. Schwartzbach, A domain-specific programming language for secure multiparty computation, Proceedings of the 2007 workshop on Programming languages and analysis for security, June 14-14, 2007, San Diego, California, USA [doi>10.1145/1255329.1255333]
• 18: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  D. Software
  D.0 GENERAL

General Terms:
Design, Security

Keywords:
cryptography, secure multi-party computation