Paper 2021/1357

Two-Round Concurrently Secure Two-Party Computation

Behzad Abdolmaleki, Giulio Malavolta, and Ahmadreza Rahimi

Abstract

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).