## 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 *strict* polynomial-time probabilistic machines (or
circuits). However, *expected* polynomial-time machines are
often also considered. For example, there are many zero-knowledge
protocols for which the only simulation techniques known 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 the context of simulation-based
security proofs.

Postscript, gzipped Postscript.

Back Home