Cryptology ePrint Archive: Report 2017/124

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

Sanjam Garg and Susumu Kiyoshima and Omkant Pandey

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

Category / Keywords: secure two-party computation, concurrent security, exact round complexity, super-polynomial-time simulation security

Original Publication (in the same form): IACR-EUROCRYPT-2017

Date: received 13 Feb 2017

Contact author: sanjamg at berkeley edu, omkant@gmail com, kiyoshima susumu@lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20170216:215933 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]