**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 (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.

**Category / Keywords: **Zero-knowledge proof systems, proofs of knowledge, expected vs. strict polynomial-time, black-box vs. non-black-box algorithms

**Publication Info: **An extended abstract appeared in the 34th STOC, 2002. To appear in the SIAM Journal on Computing.

**Date: **received 7 Apr 2002, last revised 2 Feb 2004

**Contact author: **boaz at ias edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20040202:150505 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]