**
Round-Optimal Secure Two-Party Computation
**

*
Jonathan Katz, Rafail Ostrovsky
*

**
Abstract:
**

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 \emph{arbitrary} poly-time functionality) was not previously known.

Here, we establish the *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.

**comment:**
In Proceedings of Advances in Cryptology, (CRYPTO-2004)
Springer-Verlag/IACR Lecture Notes in Computer Science.

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.