International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jonathan Katz
Yehuda Lindell
Download:
URL: http://eprint.iacr.org/2005/379
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12713,
  title={Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs},
  booktitle={IACR Eprint archive},
  keywords={foundations / expected polynomial-time, simulation, secure protocols},
  url={http://eprint.iacr.org/2005/379},
  note={An extended abstract of this work appeared at TCC 2005. This full version will appear in the Journal of Cryptology. lindell@cs.biu.ac.il 13349 received 20 Oct 2005, last revised 20 Jul 2006},
  author={Jonathan Katz and Yehuda Lindell},
  year=2005
}