Abstract
In this paper we show that any two-party functionality can be securely computed in a constant number of rounds, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao’s constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds.
In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round perfect coin-tossing protocol, where by “perfect” we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. Beaver. Foundations of Secure Interactive Computing. In Crypto91, Springer-Verlag LNCS Vol. 576, pages 377–391, 1991.
D. Beaver, S. Micali and P. Rogaway. The Round Complexity of Secure Protocols. In 22nd STOC, pages 503–513, 1990.
M. Blum. Coin Flipping by Phone. IEEE Spring COMPCOM, pages 133–137, February 1982.
G. Brassard, C. Crepeau and M. Yung. Constant-round perfect zero-knowledge computationally convincing protocols. In Theoretical Computer Science, Vol. 84(1), pp. 23–52, 1991.
R. Canetti. Security and Composition of Multi-party Cryptographic Protocols. Journal of Cryptology, Vol. 13, No. 1, pages 143–202, 2000.
I. Damgard, T. Pederson and B. Pfitzmann. On the Existence of Statistically Hiding Bit Commitment Schemes and Fail-Stop Signatures. In Crypto93, Springer-Verlag LNCS Vol. 773, pages 250–265, 1993.
S. Even, O. Goldreich and A. Lempel. A Randomized Protocol for Signing Contracts. Communications of the A CM 28, pp. 637–647, 1985.
U. Feige and A. Shamir. Zero-Knowledge Proofs of Knowledge in Two Rounds. In Crypto89, Springer-Verlag LNCS Vol. 435, pp 526–544.
O. Goldreich. Secure Multi-Party Computation. Manuscript. Preliminary version, 1998. Available from: http://www.wisdom.weizmann.ac.il/~oded/pp.html.
O. Goldreich. Foundations of Cryptography: Volume 1-Basic Tools. Cambridge University Press, 2001.
O. Goldreich and H. Krawczyk. On the Composition of Zero-Knowledge Proof Systems. SIAM Journal on Computing, Vol. 25, No. 1, February 1996, pages 169–192.
O. Goldreich, S. Micali and A. Wigderson. Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. JACM, Vol. 38, No. 1, pages 691–729, 1991.
O. Goldreich, S. Micali and A. Wigderson. How to Play any Mental Game-A Completeness Theorem for Protocols with Honest Majority. In 19th STOC, pages 218–229, 1987. For details see [9].
S. Micali and P. Rogaway. Secure Computation. Unpublished manuscript, 1992. Preliminary version in Crypto’91, Springer-Verlag (LNCS 576), 1991.
M. Naor. Bit Commitment using Pseudorandom Generators. Journal of Cryptology, Vol. 4, pages 151–158, 1991.
M. Naor and M. Yung. Universal One-Way Hash Functions and their Cryptographic Applications. In 21st STOC, pages 33–43, 1989.
A.C. Yao. How to Generate and Exchange Secrets. In 27th FOCS, pages 162–167, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lindell, Y. (2001). Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. In: Kilian, J. (eds) Advances in Cryptology — CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science, vol 2139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44647-8_10
Download citation
DOI: https://doi.org/10.1007/3-540-44647-8_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42456-7
Online ISBN: 978-3-540-44647-7
eBook Packages: Springer Book Archive