Paper 2022/1719

Two-Round Concurrent 2PC from Sub-Exponential LWE

Behzad Abdolmaleki, University of Sheffield, UK
Saikrishna Badrinarayanan, LinkedIn, USA
Rex Fernando, Carnegie Mellon University, USA
Giulio Malavolta, Max Planck Institute for Security and Privacy, Germany and Bocconi University, Italy
Ahmadreza Rahimi, Max Planck Institute for Security and Privacy, Germany
Amit Sahai, UCLA, Los Angeles, USA

Secure computation is a cornerstone of modern cryptography and a rich body of research is devoted to understanding its round complexity. In this work, we consider two-party computation (2PC) protocols (where both parties receive output) that remain secure in the realistic setting where many instances of the protocol are executed in parallel (concurrent security). We obtain a two-round concurrent-secure 2PC protocol based on a single, standard, post-quantum assumption: The subexponential hardness of the learning-with-errors (LWE) problem. Our protocol is in the plain model, i.e., it has no trusted setup, and it is secure in the super-polynomial simulation framework of Pass (EUROCRYPT 2003). Since two rounds are minimal for (concurrent) 2PC, this work resolves the round complexity of concurrent 2PC from standard assumptions. As immediate applications, our work establishes feasibility results for interesting cryptographic primitives, such as the first two-round password authentication key exchange (PAKE) protocol in the plain model and the first two-round concurrent secure computation protocol for quantum circuits (2PQC).

Note: Full version

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
post-quantum two-party computationstwo-round post-quantum PAKEPlain model
Contact author(s)
abdolmaleki behzad @ yahoo com
bsaikrishna7393 @ gmail com
rex1fernando @ gmail com
giulio malavolta @ mpi-sp org
ahmadreza rahimi @ mpi-sp org
sahai @ cs ucla edu
2023-09-22: revised
2022-12-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Behzad Abdolmaleki and Saikrishna Badrinarayanan and Rex Fernando and Giulio Malavolta and Ahmadreza Rahimi and Amit Sahai},
      title = {Two-Round Concurrent 2PC from Sub-Exponential LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1719},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.