Abstract
The standard class of adversaries considered in cryptography is that of strict polynomial-time probabilistic machines. However, expected polynomial-time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) polynomial time. In addition, it has been shown that expected polynomial-time simulation is essential for achieving constant-round black-box zero-knowledge protocols. This reliance on expected polynomial-time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected polynomial-time adversaries in simulation-based security proofs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Barak, How to go beyond the black-box simulation barrier, in 42nd FOCS, 2001, pp. 106–115
B. Barak, O. Goldreich, Universal arguments and their applications, in 17th IEEE Conference on Computational Complexity, 2002, pp. 194–203
B. Barak, Y. Lindell, Strict polynomial-time in simulation and extraction, SIAM J. Comput. 33(4), 783–818 (2004)
P. Billingsley, Probability and Measure, 2nd edn. (Wiley, New York, 1986)
R. Canetti, Security and composition of multiparty cryptographic protocols, J. Cryptol. 13(1), 143–202 (2000)
R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in 42nd FOCS, 2001, pp. 136–145
R. Canetti, O. Goldreich, S. Goldwasser, S. Micali, Resettable zero-knowledge, in 32nd STOC, 2000, pp. 235–244
U. Feige, Alternative models for zero knowledge interactive proofs. Ph.D. Thesis, Weizmann Institute, 1990
U. Feige, A. Shamir, Zero-knowledge proofs of knowledge in two rounds, in CRYPTO’89. LNCS, vol. 435 (Springer, Berlin, 1989), pp. 526–544
O. Goldreich, Basic Tools. Foundations of Cryptography, vol. 1 (Cambridge University Press, Cambridge, 2001)
O. Goldreich, Basic Applications. Foundations of Cryptography, vol. 2 (Cambridge University Press, Cambridge, 2004)
O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for NP, J. Cryptol. 9(3), 167–190 (1996)
O. Goldreich, Y. Oren, Definitions and properties of zero-knowledge proof systems, J. Crypt. 7(1), 1–32 (1994)
O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions, J. ACM 33(4), 792–807 (1986)
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—a completeness theorem for protocols with honest majority, in 19th STOC, 1987, pp. 218–229. For details see [11]
O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, J. ACM 38(1), 691–729 (1991)
S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comput. 18(1), 186–208 (1989)
J. Håstad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function, SIAM J. Comput. 28(4), 1364–1396 (1999)
Y. Lindell, Parallel coin-tossing and constant-round secure two-party computation, J. Cryptol. 16(3), 143–184 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Oded Goldrech
An extended abstract of this work appeared in the 2nd Theory of Cryptography Conference (TCC), 2005. This research was supported in part by Grant No. 2004240 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.
Yehuda Lindell: Some of this work was carried out while Y. Lindell was at IBM T.J. Watson.
Rights and permissions
About this article
Cite this article
Katz, J., Lindell, Y. Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs. J Cryptol 21, 303–349 (2008). https://doi.org/10.1007/s00145-007-9004-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-007-9004-8