The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic polynomial time. However, until recently, in order to obtain *constant-round* zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time that is only polynomial *on the average* (i.e., *expected* polynomial time). Recently Barak gave the first constant-round zero-knowledge argument with a *strict* (in contrast to expected) polynomial-time simulator. The simulator in his protocol is a *non-black-box* simulator (i.e., it makes inherent use of the description of the *code* of the verifier).
In this paper, we further address the question of strict polynomial-time in constant-round zero-knowledge proofs and arguments of knowledge. First, we show that there exists a constant-round zero-knowledge *argument of knowledge* with a *strict* polynomial-time *knowledge extractor*. As in the simulator of Barak's zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that non-black-box techniques are *essential* for both strict polynomial-time simulation and extraction. That is, we show that no (non-trivial) constant-round zero-knowledge proof or argument can have a strict polynomial-time *black-box* simulator. Similarly, we show that no (non-trivial) constant-round zero-knowledge proof or argument of knowledge can have a strict polynomial-time *black-box* knowledge extractor

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., {\em expected} polynomial time). Whether or not allowing expected polynomial-time is {\em 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 may not be 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 {\em strict} (in contrast to expected) polynomial-time simulator. His was also the first protocol that is {\em not} black-box zero-knowledge. That is, the simulator in his protocol makes inherent use of the description of the {\em code} of the verifier.


In this paper, we completely resolve the question of expected polynomial-time in constant-round zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time {\em extractors}. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and makes inherent use of the code of the prover. On the negative side, we show that non-black-box techniques are {\em essential} for 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 {\em black-box} simulator. Similarly, we show that no constant-round zero-knowledge argument of knowledge can have a strict polynomial-time {\em 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.