Cryptography Reference
In-Depth Information
phenomenon. We disagree with that assessment. Our feeling is that the behavior of
protocols and “games” under parallel composition is, in general (i.e., not only in the
context of zero-knowledge), a much more complex issue than their behavior under
sequential composition: in fact, in several other cases (e.g., computationally sound
proofs, proofs of knowledge, and multi-prover proof systems; see Sections 4.8, 4.7,
and 4.11, respectively), parallel composition lags behind sequential composition. Fur-
thermore, the only advantage of parallel composition over sequential composition is in
efficiency. Hence, we do not consider the non-closure under parallel composition to be
a fundamental weakness of the formulation of zero-knowledge. Yet the “non-closure”
of zero-knowledge motivates the search for alternative (related) notions that are pre-
served under parallel composition. (Such notions may be either weaker or stronger
than the formulation of zero-knowledge.) For further details, the reader is referred to
Sections 4.9 and 4.6.
4.4. Zero-Knowledge Proofs for
NNP
This section presents the main thrust of this chapter, namely, a method for constructing
zero-knowledge proofs for every language in
NP
. The importance of this method stems
from its generality, which is the key to its many applications. Specifically, almost all
statements one might wish to prove in practice can be encoded as claims concerning
membership in languages in
NP
. In particular, the construction of zero-knowledge
proofs for such statements provides a tool for “forcing” parties to properly execute any
given protocol.
The method for constructing zero-knowledge proofs for
NP
languages makes es-
sential use of the concept of bit commitment . Hence, we start with a presentation of the
latter concept. (A reader who wishes to have more of the flavor of this application of
commitment schemes before studying them is encouraged to read Section 4.4.2.1 first.)
4.4.1. Commitment Schemes
Commitment schemes are basic ingredients in many cryptographic protocols. They are
used to enable a party to commit itself to a value while keeping it secret. In a later stage
the commitment is “opened,” and it is guaranteed that the “opening” can yield only a
single value determined in the committing phase. Commitment schemes are the digital
analogues of non-transparent sealed envelopes. By putting a note in such an envelope,
a party commits itself to the content of the note while keeping the content secret.
4.4.1.1. Definition
Loosely speaking, a commitment scheme is an efficient two-phase two-party protocol
through which one party, called the sender , can commit itself to a value such that the
following two conflicting requirements are satisfied.
Search WWH ::




Custom Search