Paper 2021/1470

Concurrent-Secure Two-Party Computation in Two Rounds from Subexponential LWE

Saikrishna Badrinarayanan, Rex Fernando, and Amit Sahai


Very recently, two works were able to construct two-round secure multi-party computation (MPC) protocols in the plain model, without setup, relying on the superpolynomial simulation framework of Pass [Pas03]. The first work [ABG+21] achieves this relying on subexponential non-interactive witness indistinguishable arguments, the subexponential SXDH assumption, and the existence of a special type of non-interactive non-malleable commitment. The second work [FJK21] additionally achieves concurrent security, and relies on subexponential quantum hardness of the learning-with-errors (LWE) problem, subexponential classical hardness of SXDH, the existence of a subexponentially-secure (classically-hard) indistinguishablity obfuscation (iO) scheme, and time-lock puzzles. This paper focuses on the assumptions necessary to construct secure computation protocols in two rounds without setup, focusing on the subcase of two-party functionalities. In this particular case, we show how to build a two-round, concurrent-secure, two-party computation (2PC) protocol based on a single, standard, post-quantum assumption, namely subexponential hardness of the learning-with-errors (LWE) problem. We note that our protocol is the first two-round concurrent-secure 2PC protocol that does not require the existence of a one-round non-malleable commitment (NMC). Instead, we are able to use the two-round NMCs of [KS17a], which is instantiable from subexponential LWE.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
two-party computationlearning with errors
Contact author(s)
bsaikrishna7393 @ gmail com
rex1fernando @ gmail com
amitsahai @ gmail com
2021-11-06: received
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayanan and Rex Fernando and Amit Sahai},
      title = {Concurrent-Secure Two-Party Computation in Two Rounds from Subexponential LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1470},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.