Paper 2005/379

Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs

Jonathan Katz and Yehuda Lindell

Abstract

The standard class of adversaries considered in cryptography is that of {\em strict} polynomial-time probabilistic machines. However, {\em 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 {\em 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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. An extended abstract of this work appeared at TCC 2005. This full version will appear in the Journal of Cryptology.
Keywords
expected polynomial-timesimulationsecure protocols
Contact author(s)
lindell @ cs biu ac il
History
2006-07-20: revised
2005-10-23: received
See all versions
Short URL
https://ia.cr/2005/379
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/379,
      author = {Jonathan Katz and Yehuda Lindell},
      title = {Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2005/379},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/379}},
      url = {https://eprint.iacr.org/2005/379}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.