Round-Optimal Secure Two-Party Computation from Trapdoor Permutations
In this work we continue the study on the round complexity of secure two-party computation with black-box simulation.
- PDF / 987,678 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 225 Views
DIEM, University of Salerno, Fisciano, Italy {mciampi,lsiniscalchi,visconti}@unisa.it 2 UCLA, Los Angeles, USA [email protected]
Abstract. In this work we continue the study on the round complexity of secure two-party computation with black-box simulation. Katz and Ostrovsky in CRYPTO 2004 showed a 5 (optimal) round construction assuming trapdoor permutations for the general case where both players receive the output. They also proved that their result is round optimal. This lower bound has been recently revisited by Garg et al. in Eurocrypt 2016 where a 4 (optimal) round protocol is showed assuming a simultaneous message exchange channel. Unfortunately there is no instantiation of the protocol of Garg et al. under standard polynomial-time hardness assumptions. In this work we close the above gap by showing a 4 (optimal) round construction for secure two-party computation in the simultaneous message channel model with black-box simulation, assuming trapdoor permutations against polynomial-time adversaries. Our construction for secure two-party computation relies on a special 4-round protocol for oblivious transfer that nicely composes with other protocols in parallel. We define and construct such special oblivious transfer protocol from trapdoor permutations. This building block is clearly interesting on its own. Our construction also makes use of a recent advance on non-malleability: a delayed-input 4-round non-malleable zero knowledge argument.
1
Introduction
Obtaining round-optimal secure computation [14,19] has been a long standing open problem. For the two-party case the work of Katz and Ostrovsky [15] demonstrated that 5 rounds are both necessary and sufficient, with black-box simulation, when both parties need to obtain the output. Their construction relies on the use of trapdoor permutations1 . A more recent work of Ostrovsky et al. [16] showed that a black-box use of trapdoor permutations is sufficient for obtaining the above round-optimal construction. 1
The actual assumption is enhanced trapdoor permutations, but for simplicity in this paper we will omit the word enhanced assuming it implicitly.
c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 678–710, 2017. https://doi.org/10.1007/978-3-319-70500-2_23
Round-Optimal Secure Two-Party Computation from TDPs
679
A very recent work of Garg et al. [12] revisited the lower bound of [15] when the communication channel allows both players to send messages in the same round, a setting that has been widely used when studying the round complexity of multi-party computation. Focusing on the simultaneous message exchange model, Garg et al. showed that 4 rounds are necessary to build a secure two-party computation (2PC) protocol for every functionality with black-box simulation. In the same work they also designed a 4-round secure 2PC protocol for every functionality. However their construction compared to the one of [15] relies on much stronger complexity assumptions. Indeed the security
Data Loading...
