Cryptography Reference
In-Depth Information
required. A much better idea is to let Alice augment the bit she sends Carol with a
zero-knowledge proof that this bit is indeed the least significant bit of the message. We
stress that the foregoing statement is of the “
type” (since the proof specified earlier
can be efficiently verified), and therefore the existence of zero-knowledge proofs for
NP
NP
-statements implies that the foregoing statement can be proved without revealing
anything beyond its validity.
The focus of Chapter 4, devoted to zero-knowledge proofs, is on the foregoing result
(i.e., the construction of zero-knowledge proofs for any
-statement). In addition,
we shall consider numerous variants and aspects of the notion of zero-knowledge proofs
and their effects on the applicability of this notion.
NP
1.2. Some Background from Probability Theory
Probability plays a central role in cryptography. In particular, probability is essential
in order to allow a discussion of information or lack of information (i.e., secrecy). We
assume that the reader is familiar with the basic notions of probability theory. In this
section, we merely present the probabilistic notations that are used throughout this topic
and three useful probabilistic inequalities.
1.2.1. Notational Conventions
Throughout this entire topic we shall refer to only
discrete
probability distributions.
Typically, the probability space consists of the set of all strings of a certain length
, taken with uniform probability distribution. That is, the sample space is the set
of all
-bit-long strings, and each such string is assigned probability measure 2
−
.
Traditionally, functions from the sample space to the reals are called
random variables
.
Abusing standard terminology, we allow ourselves to use the term
random variable
also
when referring to functions mapping the sample space into the set of binary strings.
We often do not specify the probability space, but rather talk directly about random
variables. For example, we may say that
X
is a random variable assigned values in
the set of all strings, so that
Pr
1
4
Pr
3
[
X
=
00]
=
and
[
X
=
111]
=
4
. (Such a random
2
, so that
X
(11)
=
00 and
X
(00)
=
X
(01)
=
X
(10)
=
111.) In most cases the probability space consists of all strings of
a particular length. Typically, these strings represent random choices made by some
randomized process (see next section), and the random variable is the output of the
process.
variable can be defined over the sample space
{
0
,
1
}
How to Read Probabilistic Statements.
All our probabilistic statements refer to
functions of random variables that are defined beforehand. Typically, we shall write
Pr
=
1], where
X
is a random variable defined beforehand (and
f
is a function).
An important convention is that
all occurrences of a given symbol in a probabilistic
statement refer to the same (unique) random variable
. Hence, if
B
(
[
f
(
X
)
) is a Boolean
expression depending on two variables and
X
is a random variable, then
·
,
·
Pr
[
B
(
X
,
X
)]
denotes the probability that
B
(
x
,
x
) holds when
x
is chosen with probability
Pr
[
X
=
x
].
