Cryptography Reference
In-Depth Information
decrease the error probability to a negligible one.
36
(The efficiency improvement, briefly
mentioned at the end of Section 4.11.3, is due to [66].)
We mention that multi-prover interactive proof systems are related to probabilisti-
cally checkable proof (PCP) systems. The complexity-theoretic aspects of these proof
systems have been the focus of much interest. The interested reader is referred to
Sections 2.4 and 2.5.2 of [97] (and to the references therein).
4.12.2. Suggestions for Further Reading
A wider perspective on probabilistic proof systems is offered by Goldreich [97]: In
particular, Chapter 2 of [97] contains further details on interactive proof systems, an
introduction to probabilistically checkable proof (PCP) systems and discussions of other
types of probabilistic proof systems. The exposition focuses on the basic definitions and
results concerning such systems and emphasizes both the similarities and differences
between the various types of probabilistic proofs. Specifically, like zero-knowledge
proof systems, all probabilistic proof systems share a common (untraditional) feature:
They carry a probability of error. Yet this probability is explicitly bounded and can
be reduced by successive applications of the proof system. The gain in allowing this
untraditional relaxation is substantial, as demonstrated by three well-known results
regarding
interactive proofs
,
zero-knowledge proofs
, and
probabilistic checkable proofs
:
In each of these cases, allowing a bounded probability of error makes the system much
more powerful and useful than the traditional (errorless) counterparts.
Since their introduction a decade and a half ago, zero-knowledge proofs have been
the focus of much research. We refrain from offering a comprehensive list of suggestions
for further reading. Instead, we merely point out some works that address obvious gaps
in the current chapter.
•
A uniform-complexity treatment
of zero-knowledge is provided in [94]. In particular,
it is shown how to use (uniformly) one-way functions to construct interactive proof
systems for
NP
such that it is infeasible to find instances in which the prover leaks
knowledge.
•
Statistical
(a.k.a
almost-perfect
)
zero-knowledge proofs
offer absolute levels of security
for both the prover and the verifier; that is, both the zero-knowledge and soundness con-
ditions are satisfied in a strong probabilistic sense rather than in a computational one.
The class of problems possessing statistical zero-knowledge proofs, denoted
,is
quite intriguing (e.g., it contains some hard problems [124, 109], has complete prob-
lems [194, 118, 120], and is closed under complementation [180, 194, 118]). The inter-
ested reader is directed to Vadhan's thesis [206].
We mention that some of the techniques developed toward studying
SZK
are
also applicable in the context of ordinary (computational) zero-knowledge proofs
(e.g., the transformation from public-coin proof systems that are zero-knowledge with
respect to an honest verifier to similar systems that are zero-knowledge in general
[118]).
SZK
36
This observation escaped the authors of [146], who, being aware of the problematics of parallel repetitions
(of general multi-prover systems), suggested an alternative construction.
