Cryptography Reference
In-Depth Information
Section 4.5:
Negative results
Section 4.6:
Witness indistinguishability
and
witness hiding
Section 4.7:
Proofs of knowledge
Section 4.8:
Computationally sound proofs
(
arguments
)
Section 4.9:
Constant-round
zero-knowledge systems
Section 4.10:
Non-interactive zero-knowledge
proofs
Section 4.11:
Multi-prover
zero-knowledge proofs
Figure 4.2:
The advanced sections of this chapter.
we present a zero-knowledge proof system for every language in
(Section 4.4).
Sections dedicated to advanced topics follow (see Figure 4.2). Unless stated differently
(in the following list and in Figure 4.3), each of these advanced sections can be read
independently of the others.
NP
•
In Section 4.5 we present some
negative results
regarding zero-knowledge proofs. These
results demonstrate the “optimality” of the results in Section 4.4 and motivate the variants
presented in Sections 4.6 and 4.8.
•
In Section 4.6 we present a major relaxation of zero-knowledge and prove that it is closed
under parallel composition (which is not the case, in general, for zero-knowledge). Here
we refer to a notion called
witness indistinguishability
, which is related to
witness hiding
(also defined and discussed).
•
In Section 4.7 we define and discuss (zero-knowledge)
proofs of knowledge
.
•
In Section 4.8 we discuss a relaxation of interactive proofs, termed
computationally
sound proofs
(or
arguments
).
•
In Section 4.9 we present two constructions of
constant-round
zero-knowledge systems.
The first is an interactive proof system, whereas the second is an argument system. Section
4.8.2 (discussing perfectly hiding commitment schemes) is a prerequisite for the first
construction, whereas Sections 4.8, 4.7, and 4.6 constitute a prerequisite for the second.
4.1 - 4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
Figure 4.3:
The dependence structure of this chapter.