Paper 2002/043
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.
Metadata
- Available format(s)
-
PDF PS
- Publication info
- Published elsewhere. An extended abstract appeared in the 34th STOC, 2002. To appear in the SIAM Journal on Computing.
- Keywords
- Zero-knowledge proof systemsproofs of knowledgeexpected vsstrict polynomial-timeblack-box vsnon-black-box algorithms
- Contact author(s)
- boaz @ ias edu
- History
- 2004-02-02: last of 7 revisions
- 2002-04-07: received
- See all versions
- Short URL
- https://ia.cr/2002/043
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2002/043,
author = {Boaz Barak and Yehuda Lindell},
title = {Strict Polynomial-time in Simulation and Extraction},
howpublished = {Cryptology {ePrint} Archive, Paper 2002/043},
year = {2002},
url = {https://eprint.iacr.org/2002/043}
}