Paper 2017/597

Round Optimal Concurrent MPC via Strong Simulation

Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Dakshita Khurana, and Amit Sahai

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 sub- exponentially 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 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 larger than the running time of the simulator.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2017
Keywords
concurrent mpcsuperpolynomial simulationstrong simulationthree rounds.
Contact author(s)
saikrishna @ cs ucla edu
History
2017-09-26: last of 4 revisions
2017-06-21: received
See all versions
Short URL
https://ia.cr/2017/597
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/597,
      author = {Saikrishna Badrinarayanan and Vipul Goyal and Abhishek Jain and Dakshita Khurana and Amit Sahai},
      title = {Round Optimal Concurrent MPC via Strong Simulation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/597},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/597}},
      url = {https://eprint.iacr.org/2017/597}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.