Cryptography Reference
In-Depth Information
CHAPTER
4
Zero-Knowledge Proof Systems
In this chapter we discuss zero-knowledge (ZK) proof systems. Loosely speaking, such
proof systems have the remarkable property of being convincing
and
yielding nothing
(beyond the validity of the assertion). In other words, receiving a zero-knowledge
proof that an assertion holds is equivalent to being told by a trusted party that the
assertion holds (see illustration in Figure 4.1). The main result presented in this chapter
is a method for constructing zero-knowledge proof systems for every language in
NP
. This method can be implemented using any bit-commitment scheme, which in
turn can be implemented using any pseudorandom generator. The importance of this
method stems from its generality, which is the key to its many applications. Specifically,
almost all statements one may wish to prove in practice can be encoded as claims
concerning membership in languages in
. In addition, we discuss more advanced
aspects of the concept of zero-knowledge and their effects on the applicability of this
concept.
NP
Organization.
The basic material is presented in Sections 4.1 through 4.4. In parti-
cular, we start with motivation (Section 4.1), next we define and exemplify the notions
of interactive proofs (Section 4.2) and of zero-knowledge (Section 4.3), and finally
X is true!
X
???
!!
Figure 4.1:
Zero-knowledge proofs: an illustration.
