On Secure Two-Party Computation in Three Rounds
We revisit the exact round complexity of secure two-party computation. While four rounds are known to be sufficient for securely computing general functions that provide output to one party [Katz-Ostrovsky, CRYPTO’04], Goldreich-Krawczyk [SIAM J. Computin
- PDF / 830,731 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 200 Views
University of California Los Angeles, Los Angeles, USA [email protected] 2 Johns Hopkins University, Baltimore, USA [email protected]
Abstract. We revisit the exact round complexity of secure two-party computation. While four rounds are known to be sufficient for securely computing general functions that provide output to one party [KatzOstrovsky, CRYPTO’04], Goldreich-Krawczyk [SIAM J. Computing’96] proved that three rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of secure computation in three rounds using non-black-box simulation. Our main result is a three-round two-party computation protocol for general functions against adversaries with auxiliary inputs of a priori bounded size. This result relies on a new two round input-extraction protocol based on succinct randomized encodings. We also provide a partial answer to the question of achieving security against non-uniform adversaries. Assuming sub-exponentially secure iO and one-way functions, we rule out three-round protocols that achieve polynomial simulation-based security against the output party and exponential indistinguishability-based security against the other party.
1
Introduction
The notion of secure computation [24,39] is fundamental in cryptography. Informally speaking, secure two-party computation allows two mutually distrusting parties to jointly compute a function over their private inputs in a manner such that no one learns anything beyond the function output. An important measure of efficiency of secure computation protocols is round complexity. Clearly, the smaller the number of rounds, the lesser the impact of network latency on the communication between the parties. Indeed, ever since the introduction of secure computation, its round complexity has been the subject of intensive study, both in the two-party and multiparty setting. In this work, we study the exact round complexity of secure two-party computation against malicious adversaries in the plain model (i.e., without any P. Ananth—Supported in part by grant 360584 from the Simons Foundation. A. Jain—Supported in part by a DARPA/ARL Safeware Grant W911NF-15-C-0213 and a sub-award from NSF CNS-1414023. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 612–644, 2017. https://doi.org/10.1007/978-3-319-70500-2_21
On Secure Two-Party Computation in Three Rounds
613
trusted setup assumptions). We focus on the classical unidirectional message model where a round of communication consists of a single message sent by one party to the other. In this setting, constant round protocols can be readily obtained by compiling a two-round semi-honest protocol (e.g., using garbled circuits [39] and oblivious transfer [15,37]) with constant-round zero-knowledge proofs [16,21,26] following the GMW paradigm [24]. Katz and Ostrovsky [30] established an upper bound on the exact round complexity of secure two-party computation by showing that four rounds are sufficient for
Data Loading...
