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: ia.cr/2017/124