About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Computing
Paper
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.