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
-
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},
url = {https://eprint.iacr.org/2005/379}
}
