Paper 2002/043

Strict Polynomial-time in Simulation and Extraction

Boaz Barak and Yehuda Lindell


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.

Available format(s)
Publication info
Published elsewhere. An extended abstract appeared in the 34th STOC, 2002. To appear in the SIAM Journal on Computing.
Zero-knowledge proof systemsproofs of knowledgeexpected vsstrict polynomial-timeblack-box vsnon-black-box algorithms
Contact author(s)
boaz @ ias edu
2004-02-02: last of 7 revisions
2002-04-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Boaz Barak and Yehuda Lindell},
      title = {Strict Polynomial-time in Simulation and Extraction},
      howpublished = {Cryptology ePrint Archive, Paper 2002/043},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.