Cryptography Reference
In-Depth Information
concerning parallel composition of zero-knowledge proof systems (i.e., Proposition
4.5.9 and Theorem 4.5.11) are from [106].
Witness Indistinguishability.
The notions of witness indistinguishability and witness-
hiding, were introduced and developed by Feige and Shamir [78]. Section 4.6 is based
on their work.
Proofs of Knowledge.
The concept of proofs of knowledge originates from the paper
of Goldwasser, Micali, and Rackoff [124]. Early attempts to provide a definition of that
concept appear in [75] and [205]; however, those definitions were not fully satisfactory.
The issue of defining proofs of knowledge has been extensively investigated by Bellare
and Goldreich [17], and we follow their suggestions. The application of zero-knowledge
proofs of knowledge to identification schemes was discovered by Feige, Fiat, and
Shamir [80, 75]. The Fiat-Shamir identification scheme [80] is based on the zero-
knowledge proof for Quadratic Residuosity of Goldwasser, Micali, and Rackoff [124].
Computationally Sound Proof Systems (Arguments).
Computationally sound proof
systems (i.e., arguments)
35
were introduced by Brassard, Chaum, and Crepeau [40].
Their paper also presents perfect zero-knowledge arguments for
NP
based on the
intractability of factoring. Naor et al. [171] showed how to construct perfect zero-
knowledge arguments for
based on any one-way permutation, and Construc-
tion 4.8.3 is taken from their paper. The poly-logarithmic-communication argument
system for
NP
NP
(of Section 4.8.4) is due to Kilian [143].
Constant-Round Zero-Knowledge Protocols.
The round-efficient zero-knowledge
proof systems for
, based on any claw-free collection, is taken from [105]. The
round-efficient zero-knowledge arguments for
NP
, based on any one-way function, is
due to [77], yet our presentation (which uses some of their ideas) is different. (The alter-
native construction outlined in Section 4.9.2.3 is much more similar to the construction
in [77].)
NP
Non-Interactive Zero-Knowledge Proofs.
Non-interactive zero-knowledge proof sys-
tems were introduced by Blum, Feldman, and Micali [34]. The constructions presented
in Section 4.10 are due to Feige, Lapidot, and Shamir [76]. For further detail on Remark
4.10.6, see [23].
Multi-Prover Zero-Knowledge Proofs.
Multi-prover interactive proofs were intro-
duced by Ben-Or, Goldwasser, Kilian, and Wigderson [26]. Their paper also presents a
perfect zero-knowledge two-prover proof system for
NP
. The perfect zero-knowledge
two-prover proof for
presented in Section 4.11 follows their ideas; however, we ex-
plicitly state the properties of the two-sender commitment scheme in use. Consequently,
we observe that (sufficiently many) parallel repetitions of this
specific
proof system
will
NP
35
Unfortunately, there is some confusion regarding terminology in the literature: In some work (particularly
[40]), computationally sound proofs (arguments) are negligently referred to as “interactive proofs.”
