Cryptography Reference
In-Depth Information
In general, the question is whether or not
it is possible to prove a statement without
yielding anything beyond its validity
. Such proofs, whenever they exist, are called
zero-knowledge
, and they play a central role in the construction of “cryptographic”
protocols.
Loosely speaking,
zero-knowledge proofs are proofs that yield nothing
(i.e., “no
knowledge”)
beyond the validity of the assertion
. In the rest of this introductory section,
we discuss the notion of a “proof” and a possible meaning of the phrase “yield nothing
(i.e., no knowledge) beyond something.”
4.1.1. The Notion of a Proof
A proof is whatever convinces me.
Shimon Even, answering a student's question
in his graph-algorithms class (1978)
We discuss the notion of a proof with the intention of uncovering some of its underlying
aspects.
4.1.1.1. A Static Object versus an Interactive Process
Traditionally in mathematics, a “proof” is a
fixed
sequence consisting of statements
that either are self-evident or are derived from previous statements via self-evident
rules. Actually, it is more accurate to replace the phrase “self-evident” with the phrase
“commonly agreed.” In fact, in the formal study of proofs (i.e., logic), the commonly
agreed statements are called
axioms
, whereas the commonly agreed rules are referred
to as
derivation rules
. We wish to stress two properties of mathematical proofs:
1.
Proofs are viewed as fixed objects.
2.
Proofs are considered at least as fundamental as their consequences (i.e., the theorems).
However, in other areas of human activity, the notion of a “proof” has a much wider
interpretation. In particular, a proof is not a fixed object, but rather a process by which
the validity of an assertion is established. For example, withstanding cross-examination
in court can yield what can be considered a proof in law, and failure to provide an
adequate answer to a rival's claim is considered a proof in philosophical, political, and
sometimes even technical discussions. In addition, in many real-life situations, proofs
are considered secondary (in importance) to their consequences.
To summarize, in “canonical” mathematics, proofs have a static nature (e.g., they
are “written”), whereas in real-life situations proofs have a dynamic nature (i.e., they
are established via an interaction). A dynamic interpretation of the notion of a proof is
more appropriate to our setting, in which proofs are used as tools (i.e., sub-protocols)
inside “cryptographic” protocols. Furthermore, a dynamic interpretation (at least in a
weak sense) is essential to the non-triviality of the notion of a zero-knowledge proof.
4.1.1.2. Prover and Verifier
The notion of a prover is implicit in all discussions of proofs, be it in mathematics or
in real-life situations: The prover is the (sometimes hidden or transcendental) entity
