$${\varvec{1/p}}$$ 1 / p -Secure Multiparty Computation without an Honest Majority and the Best of Both Worlds
- PDF / 3,846,051 Bytes
- 73 Pages / 439.37 x 666.142 pts Page_size
- 76 Downloads / 174 Views
1/ p-Secure Multiparty Computation without an Honest Majority and the Best of Both Worlds∗ Amos Beimel Department of Computer Science, Ben Gurion University, Be’er Sheva, Israel
Yehuda Lindell Department of Computer Science, Bar Ilan University, Ramat Gan, Israel
Eran Omri Department of Computer Science, Ariel University, Ariel, Israel [email protected]
Ilan Orlov Department of Computer Science, Ben Gurion University, Be’er Sheva, Israel Communicated by Jonathan Katz. Received 6 December 2013 / Revised 4 November 2019
Abstract. A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation, where parties give their inputs to a trusted party that returns the output of the functionality to all parties. In particular, in the ideal model, such computation is fair—if the corrupted parties get the output, then the honest parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition—1/ p-secure computation—which guarantees partial fairness. For two parties, they constructed 1/ psecure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/ p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/ psecure protocols that are resilient against any number of corrupted parties provided that the number of parties is constant and the size of the range of the functionality is at most polynomial (in the security parameter n). If fewer than 2/3 of the parties are corrupted,
∗ A preliminary version of this work appeared in CRYPTO 2011 [9]. Amos Beimel: Generously supported by ISF Grant 938/09 and by the Frankel Center for Computer Science. Yehuda Lindell: Generously supported by the European Research Council as part of the ERC project LAST, and by the Israel science foundation (Grant No. 781/07). Eran Omri: Ariel Cyber Innovation Center. Generously supported by the European Research Council as part of the ERC project LAST, and by the Israel science foundation (Grant No. 781/07). Ilan Orlov: Generously supported by ISF Grant 938/09 and by the Frankel Center for Computer Science.
© International Association for Cryptologic Research 2020
A. Beimel et al. the size of the domain of each party is constant, and the functionality is deterministic, then our protocols are efficient even when the number of parties is log log n. On the negative side, we show that when the number of parties is super-constant, 1/ p-secure protocols are not possible when the size of the domain of each party is polynomial. Thus, our feasibility results for 1/ p-secure computation are essentially tight. We further motivate our results by constructing protocols with stronger guarantees: If in the execution of the p
Data Loading...
