Arka Rai Choudhuri
ABSTRACT
Secure multiparty computation allows mutually distrusting parties to compute a function on their private inputs such that nothing but the function output is revealed. Achieving fairness --- that all parties learn the output or no one does -- is a long studied problem with known impossibility results in the standard model if a majority of parties are dishonest. We present a new model for achieving fairness in MPC against dishonest majority by using public bulletin boards implemented via existing infrastructure such as blockchains or Google's certificate transparency logs. We present both theoretical and practical constructions using either witness encryption or trusted hardware (such as Intel SGX). Unlike previous works that either penalize an aborting party or achieve weaker notions such as $\Delta$-fairness, we achieve complete fairness using existing infrastructure.
Supplemental Material
- Bar Alon and Eran Omri 2016. Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious TCC, Part I. 307--335.Google Scholar
- Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, and Lukasz Mazurek 2014. Secure Multiparty Computations on Bitcoin. In IEEE Symposium on Security and Privacy. 443--458. Google ScholarDigital Library
- Gilad Asharov. 2014. Towards Characterizing Complete Fairness in Secure Two-Party Computation TCC. 291--316.Google Scholar
- Gilad Asharov, Amos Beimel, Nikolaos Makriyannis, and Eran Omri 2015. Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions TCC, Part I. 199--228.Google Scholar
- Gilad Asharov, Yehuda Lindell, and Tal Rabin. 2013. A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness TCC. 243--262.Google Scholar
- Gilad Asharov, Yehuda Lindell, and Hila Zarosim. 2013. Fair and Efficient Secure Multiparty Computation with Reputation Systems ASIACRYPT. 201--220.Google Scholar
- N. Asokan, Matthias Schunter, and Michael Waidner. 1997. Optimistic Protocols for Fair Exchange. In CCS '97, Proceedings of the 4th ACM Conference on Computer and Communications Security, Zurich, Switzerland, April 1--4, 1997. 7--17.Google Scholar
- N. Asokan, Victor Shoup, and Michael Waidner 1998. Optimistic Fair Exchange of Digital Signatures (Extended Abstract) EUROCRYPT. 591--606.Google Scholar
- Donald Beaver and Shafi Goldwasser 1989. Multiparty Computation with Faulty Majority. In CRYPTO. 589--590. Google ScholarDigital Library
- Amos Beimel, Yehuda Lindell, Eran Omri, and Ilan Orlov. 2011. 1/p-Secure Multiparty Computation without Honest Majority and the Best of Both Worlds CRYPTO. 277--296.Google Scholar
- Michael Ben-Or, Oded Goldreich, Silvio Micali, and Ronald L. Rivest 1985. A Fair Protocol for Signing Contracts (Extended Abstract) ICALP. 43--52.Google Scholar
- Iddo Bentov, Ariel Gabizon, and Alex Mizrahi. 2016. Cryptocurrencies without proof of work. In International Conference on Financial Cryptography and Data Security. Springer, 142--157. Google ScholarCross Ref
- Iddo Bentov and Ranjit Kumaresan 2014. How to Use Bitcoin to Design Fair Protocols. In CRYPTO. 421--439. Google ScholarCross Ref
- Dan Boneh and Moni Naor 2000. Timed Commitments CRYPTO. 236--254.Google Scholar
- Elette Boyle, Kai-Min Chung, and Rafael Pass. 2014. On Extractability Obfuscation. In TCC. 52--73. Google ScholarCross Ref
- Christian Cachin and Jan Camenisch 2000. Optimistic Fair Secure Computation. In CRYPTO. 93--111. Google ScholarCross Ref
- Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish 2007. Universally Composable Security with Global Setup. Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21--24, 2007, Proceedings. 61--85. Google ScholarCross Ref
- Ran Canetti, Abhishek Jain, and Alessandra Scafuro. 2014. Practical UC security with a Global Random Oracle Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3--7, 2014. 597--608.Google Scholar
- Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai 2002. Universally composable two-party and multi-party secure computation Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19--21, 2002, Montréal, Québec, Canada. 494--503.Google Scholar
- Liqun Chen, Caroline Kudla, and Kenneth G. Paterson. 2004. Concurrent Signatures EUROCRYPT. 287--305.Google Scholar
- Richard Cleve. 1986. Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract) STOC. 364--369.Google Scholar
- Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi 2013. Practical Multilinear Maps over the Integers. In CRYPTO. 476--493. Google ScholarCross Ref
- Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi 2015. New Multilinear Maps Over the Integers. In CRYPTO. 267--286. Google ScholarCross Ref
- Ronald Cramer and Victor Shoup 1998. A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack Advances in Cryptology - CRYPTO '98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23--27, 1998, Proceedings. 13--25.Google Scholar
- Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. 2012. Practical Covertly Secure MPC for Dishonest Majority -- or: Breaking the SPDZ Limits. Cryptology ePrint Archive, Report 2012/642. (2012). shownotehttp://eprint.iacr.org/2012/642.Google Scholar
- Yevgeniy Dodis, Pil Joong Lee, and Dae Hyun Yum 2007. Optimistic Fair Exchange in a Multi-user Setting. Public Key Cryptography - PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, April 16--20, 2007, Proceedings. 118--133. Google ScholarCross Ref
- Shimon Even, Oded Goldreich, and Abraham Lempel. 1985. A Randomized Protocol for Signing Contracts. Commun. ACM, Vol. 28, 6 (1985), 637--647. Google ScholarDigital Library
- Juan A. Garay and Markus Jakobsson 2002. Timed Release of Standard Digital Signatures. In Financial Cryptography. 168--182.Google Scholar
- Juan A. Garay, Markus Jakobsson, and Philip D. MacKenzie. 1999. Abuse-Free Optimistic Contract Signing. In CRYPTO. 449--466. Google ScholarCross Ref
- Juan A. Garay, Philip D. MacKenzie, Manoj Prabhakaran, and Ke Yang 2006. Resource Fairness and Composability of Cryptographic Protocols TCC. 404--428.Google Scholar
- Juan A. Garay and Carl Pomerance 2003. Timed Fair Exchange of Standard Signatures: [Extended Abstract] Financial Cryptography, 7th International Conference, FC 2003, Guadeloupe, French West Indies, January 27--30, 2003, Revised Papers. 190--207.Google Scholar
- Sanjam Garg, Craig Gentry, and Shai Halevi. 2013. Candidate Multilinear Maps from Ideal Lattices. In EUROCRYPT. 1--17. Google ScholarCross Ref
- Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. 2013. Witness Encryption and its Applications. Cryptology ePrint Archive, Report 2013/258. (2013). shownotehttp://eprint.iacr.org/2013/258.Google Scholar
- Craig Gentry, Sergey Gorbunov, and Shai Halevi. 2015. Graph-Induced Multilinear Maps from Lattices. In TCC, Part II. 498--527. Google ScholarCross Ref
- Craig Gentry, Allison B. Lewko, and Brent Waters. 2014. Witness Encryption from Instance Independent Assumptions CRYPTO. 426--443.Google Scholar
- Oded Goldreich and Ariel Kahan 1996. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology, Vol. 9, 3 (1996), 167--190. Google ScholarDigital Library
- Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play any mental game. In STOC. Google ScholarDigital Library
- Shafi Goldwasser and Leonid A. Levin 1990. Fair Computation of General Functions in Presence of Immoral Majority CRYPTO. 77--93.Google Scholar
- Shafi Goldwasser and Rafail Ostrovsky 1992. Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract). In CRYPTO. 228--245.Google Scholar
- S. Dov Gordon. 2010. On Fairness in Secure Computation. Ph.D. Dissertation. (2010). shownotehttps://www.cs.umd.edu/ jkatz/THESES/gordon.pdf .Google Scholar
- S. Dov Gordon, Carmit Hazay, Jonathan Katz, and Yehuda Lindell 2008. Complete fairness in secure two-party computation. STOC. 413--422.Google Scholar
- S. Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, and Amit Sahai 2010. On Complete Primitives for Fairness. In TCC. 91--108. Google ScholarDigital Library
- S. Dov Gordon and Jonathan Katz 2009. Complete Fairness in Multi-party Computation without an Honest Majority Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15--17, 2009. Proceedings. 19--35.Google ScholarDigital Library
- S. Dov Gordon and Jonathan Katz 2010. Partial Fairness in Secure Two-Party Computation. EUROCRYPT. 157--176.Google Scholar
- Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol CRYPTO '17.Google Scholar
- Dafna Kidron and Yehuda Lindell 2011. Impossibility Results for Universal Composability in Public-Key Models and with Fixed Inputs. J. Cryptology, Vol. 24, 3 (2011), 517--544. https://doi.org/10.1007/s00145-010--9069--7 Google ScholarDigital Library
- Handan Kilincc and Alptekin Küpccü. 2016. Efficiently Making Secure Two-Party Computation Fair Financial Cryptography and Data Security - 20th International Conference, FC 2016, Christ Church, Barbados, February 22--26, 2016, Revised Selected Papers. 188--207. https://doi.org/10.1007/978--3--662--54970--4_11Google Scholar
- Ranjit Kumaresan and Iddo Bentov 2016. Amortizing Secure Computation with Penalties. In ACM CCS. 418--429. Google ScholarDigital Library
- Ranjit Kumaresan, Tal Moran, and Iddo Bentov. 2015. How to Use Bitcoin to Play Decentralized Poker. In ACM CCS. 195--206. Google ScholarDigital Library
- Alptekin Küpccü and Anna Lysyanskaya 2010. Usable Optimistic Fair Exchange. In CT-RSA. 252--267.Google Scholar
- Yehuda Lindell. 2009. Legally Enforceable Fairness in Secure Two-Party Communication. Chicago J. Theor. Comput. Sci. Vol. 2009 (2009).Google Scholar
- Anna Lysyanskaya. 2002. Unique Signatures and Verifiable Random Functions from the DH-DDH Separation CRYPTO. 597--612.Google Scholar
- Silvio Micali. 2003. Simple and fast optimistic protocols for fair electronic exchange PODC. 12--19.Google Scholar
- Rafael Pass, Elaine Shi, and Florian Tramèr. 2016. Formal Abstractions for Attested Execution Secure Processors. IACR Cryptology ePrint Archive Vol. 2016 (2016), 1027. http://eprint.iacr.org/2016/1027Google Scholar
- Rafael Pass, Elaine Shi, and Florian Tramèr. 2017. Formal Abstractions for Attested Execution Secure Processors EUROCRYPT. 260--289.Google Scholar
- Benny Pinkas. 2003. Fair Secure Two-Party Computation. In EUROCRYPT. 87--105. Google ScholarCross Ref
- Tal Rabin and Michael Ben-Or 1989. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract) STOC. 73--85.Google Scholar
- Andrew Chi-Chih Yao. 1982. Protocols for Secure Computations (Extended Abstract) FOCS. 160--164. endthebibliographyGoogle Scholar
Index Terms
- Fairness in an Unfair World: Fair Multiparty Computation from Public Bulletin Boards
Recommendations
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...
Resource Fairness and Composability of Cryptographic Protocols
We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to ...
Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation
In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed ...
Comments