International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Strict Polynomial-time in Simulation and Extraction

Authors:
Boaz Barak
Yehuda Lindell
Download:
URL: http://eprint.iacr.org/2002/043
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2002-11567,
  title={Strict Polynomial-time in Simulation and Extraction},
  booktitle={IACR Eprint archive},
  keywords={Zero-knowledge proof systems, proofs of knowledge, expected vs. strict polynomial-time, black-box vs. non-black-box algorithms},
  url={http://eprint.iacr.org/2002/043},
  note={An extended abstract appeared in the 34th STOC, 2002. To appear in the SIAM Journal on Computing. boaz@ias.edu 12450 received 7 Apr 2002, last revised 2 Feb 2004},
  author={Boaz Barak and Yehuda Lindell},
  year=2002
}