Strict polynomial-time in simulation and extraction

Abstract

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 nonblack-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 nonblack-box techniques are essential for both strict polynomial-time simulation and extraction. That is, we show that no (nontrivial) constant-round zero-knowledge proof or argument can have a strict polynomial-time black-box simulator. Similarly, we show that no (nontrivial) constant-round zero-knowledge proof or argument of knowledge can have a strict polynomial-time black-box knowledge extractor.