Welcome to the resource topic for 2002/043
Title:
Strict Polynomial-time in Simulation and Extraction
Authors: Boaz Barak, 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.
ePrint: https://eprint.iacr.org/2002/043
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .