Round Optimal Concurrent MPC via Strong Simulation
In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with p
- PDF / 1,808,178 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 226 Views
UCLA, Los Angeles, USA {saikrishna,dakshita,sahai}@cs.ucla.edu 2 Carnegie Mellon University, Pittsburgh, USA [email protected] 3 Johns Hopkins University, Baltimore, USA [email protected]
Abstract. In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We obtain the following results: – Three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE. – Two-round concurrent MPC with SPS security against Byzantine adversaries for input-less randomized functionalities, assuming subexponentially secure indistinguishability obfuscation and DDH. In particular, this class includes sampling functionalities that allow parties to jointly sample a secure common reference string for cryptographic applications. Prior to our work, to the best of our knowledge, concurrent MPC with SPS security required roughly 20 rounds, although we are not aware of any work that even gave an approximation of the constant round complexity sufficient for the multi-party setting. We also improve over the previous best round complexity for the two-party setting, where 5 rounds S. Badrinarayanan, D. Khurana and A. Sahai—Research supported in part from a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, NSF grants 1619348, 1228984, 1136174, and 1065276, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. Government. A. Jain—Research supported in part by a DARPA/ARL Safeware Grant W911NF15-C-0213 and a sub-award from NSF CNS-1414023. D. Khurana—Research supported in part by the UCLA Dissertation Year Fellowship. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 743–775, 2017. https://doi.org/10.1007/978-3-319-70500-2_25
744
S. Badrinarayanan et al. were needed (Garg, Kiyoshima, and Pandey, Eurocrypt 2017). To obtain our results, we compile protocols that already achieve security against “semi-malicious” adversaries, to protocols secure against fully malicious adversaries, additionally assuming sub-exponential DDH. Our protocols develop new techniques to use two-round zero-knowledge with super-polynomial strong simulation, defined by Pass (Eurocrypt 2003) and very recently realized by Khurana and Sahai (FOCS 2017). These remain zero-knowledge against adversaries running in time
Data Loading...
