Paper 2017/124

On the Exact Round Complexity of Self-Composable Two-Party Computation

Sanjam Garg, Susumu Kiyoshima, and Omkant Pandey


The round complexity of secure computation has been a fundamental problem in cryptography. Katz and Ostrovsky proved that 5 rounds are both necessary and sufficient for secure computation in the stand alone setting, thus resolving the exact round complexity of standalone secure computation. In contrast, round complexity of secure computation in the concurrent setting, where several protocols may run simultaneously, is poorly understood. Since standard polynomial time simulation is impossible in the concurrent setting, alternative security notions have been proposed, e.g., super-polynomial simulation (SPS). While SPS security can be achieved in constant rounds, the actual constant (> 20) is far from optimal. In this work, we take the first steps towards studying the exact round complexity of concurrent secure computation. We focus on the two party case and present a new secure computation protocol that achieves SPS security under concurrent self-composition. Our protocol has 5 rounds assuming quasi-polynomially-hard injective one-way functions (or 7 rounds assuming standard polynomially-hard collision-resistant hash functions). We also require other standard assumptions, specifically trapdoor OWPs and lossy TDFs. This matches the rounds for standalone secure computation. More specifically, our security proof presents a polynomial time reduction from SPS security to 3-round public-coin non-malleable commitments with appropriate extractability properties. Such commitments are known based on quasi-polynomially-hard injective OWFs. (The reduction also works with a special 6-round non-malleable commitment to yield the 7-round result under CRHFs.)

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2017
secure two-party computationconcurrent securityexact round complexitysuper-polynomial-time simulation security
Contact author(s)
sanjamg @ berkeley edu
kiyoshima susumu @ lab ntt co jp
omkant @ gmail com
2017-02-16: received
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Susumu Kiyoshima and Omkant Pandey},
      title = {On the Exact Round Complexity of Self-Composable Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/124},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.