Skip to main content
Top

2004 | OriginalPaper | Chapter

Round-Optimal Secure Two-Party Computation

Authors : Jonathan Katz, Rafail Ostrovsky

Published in: Advances in Cryptology – CRYPTO 2004

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

We consider the central cryptographic task of secure two-party computation: two parties wish to compute some function of their private inputs (each receiving possibly different outputs) where security should hold with respect to arbitrarily-malicious behavior of either of the participants. Despite extensive research in this area, the exact round-complexity of this fundamental problem (i.e., the number of rounds required to compute an arbitrary poly-time functionality) was not previously known.Here, we establish the exact round complexity of secure two-party computation with respect to black-box proofs of security. We first show a lower bound establishing (unconditionally) that four rounds are not sufficient to securely compute the coin-tossing functionality for any super-logarithmic number of coins; this rules out 4-round protocols for other natural functionalities as well. Next, we construct protocols for securely computing any (randomized) functionality using only five rounds. Our protocols may be based either on certified trapdoor permutations or homomorphic encryption schemes satisfying certain additional properties. The former assumption is implied by, e.g., the RSA assumption for large public exponents, while the latter is implied by, e.g., the DDH assumption. Finally, we show how our protocols may be modified – without increasing their round complexity and without requiring erasures – to tolerate an adaptive malicious adversary.

Metadata
Title
Round-Optimal Secure Two-Party Computation
Authors
Jonathan Katz
Rafail Ostrovsky
Copyright Year
2004
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-540-28628-8_21

Premium Partner