Cryptography Reference
In-Depth Information
that may try to extract knowledge from the smart-cards (so as to enable impersonation
by their own agents).
4.12. Miscellaneous
4.12.1. Historical Notes
Interactive proof systems were introduced by Goldwasser, Micali, and Rackoff [124].
33
A restricted form of interactive proof, known by the name
Arthur-Merlin game
(or
public-coin
proof), was introduced in [8] and shown in [128] to be equivalent to gen-
eral interactive proofs. The interactive proof for Graph Non-Isomorphism is due to
Goldreich, Micali, and Wigderson [112]. The amazing theorem-proving power of in-
teractive proofs was subsequently demonstrated in [157, 198], showing interactive
proofs for co
, respectively.
The concept of zero-knowledge was introduced by Goldwasser, Micali, and Rackoff
in the very same paper [124]. That paper also contained a perfect zero-knowledge proof
for Quadratic Non-Residuosity. The perfect zero-knowledge proof system for Graph
Isomorphism is due to Goldreich, Micali, and Wigderson [112].
The zero-knowledge proof systems for all languages in
NP
and (more generally) for
PSPACE
, using any (non-uniform
secure) commitment scheme, are also due to Goldreich, Micali, and Wigderson [112].
34
(Zero-knowledge proof systems for all languages in
NP
IP
have been presented in [136]
and [25].)
The cryptographic applications of zero-knowledge proofs were the very motivation
for their introduction in [124]. Zero-knowledge proofs were applied to solve crypto-
graphic problems in [81] and [54]. However, many more applications became possible
once it was shown how to construct zero-knowledge proof systems for every language
in
NP
. In particular, general methodologies for the construction of cryptographic
protocols have appeared in [112, 113].
The construction of commitment schemes based on one-way permutations can be
traced to [31]. The construction of commitment scheme based on pseudorandom gen-
erators is due to Naor [170].
Credits for the Advanced Sections
Negative Results.
The results demonstrating the necessity of randomness and inter-
action for zero-knowledge proofs are from [115]. The results providing upper bounds on
the complexity of languages with almost-perfect zero-knowledge proofs (i.e.,
Theorem 4.5.8) are from [83] and [2]. The results indicating that one-way functions
are necessary for non-trivial zero-knowledge are from [181]. The negative results
33
Earlier versions of their paper date to early 1983. Yet the paper, having been rejected three times from major
conferences, first appeared in public only in 1985, concurrently with the paper of Babai [8].
34
A weaker result was shown
later
in [41]: It provides an alternative construction of zero-knowledge proof
systems for
NP
, using a
stronger
intractability assumption (specifically, the intractability of the Quadratic Resid-
uosity problem).
