Paper 2021/1357

Two-Round Concurrently Secure Two-Party Computation

Behzad Abdolmaleki, Giulio Malavolta, and Ahmadreza Rahimi


In this paper, we study the round complexity of concurrently secure computation protocols in the plain model, without random oracles or assuming the presence of a trusted setup. In the plain model, it is well known that concurrently secure two-party computation with polynomial simulation is impossible to achieve in two rounds. For this reason, we focus on the well-studied notion of security with super-polynomial simulation (SPS). Our main result is the first construction of two-round SPS two-party computation for general functionalities in the plain model. Prior to our work, we only knew three-round constructions [Badrinarayanan et al., TCC 2017] and two-round protocols were not known from any computational assumption. As immediate applications, we establish the feasibility result for a series of cryptographic primitives of interest, such as: Two-round password authentication key exchange (PAKE) in the plain model, two-round concurrent blind signature in the plain model, and two round concurrent computation for quantum circuits (2PQC).

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
concurrent blind signatureconcurrent PAKE2PQC
Contact author(s)
behzad abdolmaleki @ csp mpg de
giulio malavolta @ csp mpg de
ahmadreza rahimi @ csp mpg de
2021-10-12: received
Short URL
Creative Commons Attribution


      author = {Behzad Abdolmaleki and Giulio Malavolta and Ahmadreza Rahimi},
      title = {Two-Round Concurrently Secure Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1357},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.