|
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.
Versions
-
Extended abstract in ACM STOC 2002
- SIAM Journal on Computing (SICOMP), Vol. 33 No. 4, pp 783-818, 2004.
Full version
[Acrobat pdf | postscript]
Powerpoint XP presentation
home | research | links | cv | pictures
|