## Strict Polynomial-time in
Simulation and Extraction

### Boaz Barak and Yehuda Lindell

### Abstract:

The notion of efficient computation is
usually identified in cryptography and complexity with
probabilistic polynomial time. However, until recently, in order
to obtain *constant-round* zero-knowledge proofs and proofs
of knowledge (for *NP*), one had to allow simulators and
knowledge-extractors to run in time which is only polynomial
*on the average* (i.e., *expected* polynomial time).
Whether or not allowing expected polynomial-time is
*necessary* for obtaining constant-round zero-knowledge
proofs and proofs of knowledge, has been posed as an important
open question. This question is interesting not only for its
theoretical ramifications, but also because expected polynomial
time simulation is not closed under composition. Therefore, in
some cases security is not maintained when a protocol that
utilizes expected polynomial time simulation (or extraction) is
used as a part of a larger protocol.
A partial answer to the question of the necessity (or
non-necessity) of expected polynomial-time was provided recently
by Barak, who gave the first constant-round zero-knowledge
argument with a *strict* (in contrast to expected)
polynomial-time simulator. His was also the first protocol that is
*not* black-box zero-knowledge. That is, the simulator in his
protocol utilizes the description of the *code* of the
verifier in an essential way.

In this paper, we completely resolve the question of expected
polynomial-time in zero-knowledge arguments and arguments of
knowledge. First, we show that there exist constant-round
zero-knowledge arguments of knowledge with strict polynomial-time
*extractors*. As in the simulator of Barak's zero-knowledge
protocol, the extractor for our proof of knowledge is not
black-box and uses the code of the prover in an essential way.
On the negative side, we show that non-black-box techniques are
*essential* to both strict polynomial-time simulation and
extraction. That is, we show that no constant-round zero-knowledge
argument (or proof) can have a strict polynomial-time
*black-box* simulator. Similarly, we show that no
constant-round zero-knowledge argument (or proof) of knowledge can
have a strict polynomial-time *black-box* knowledge
extractor. Thus, for constant-round black-box zero-knowledge
arguments (resp., arguments of knowledge), it is imperative that
the simulator (resp., extractor) be allowed to run in expected
polynomial-time.

Postscript, gzipped Postscript.

Back Home