Cryptography Reference
In-Depth Information
Namely,
x
Pr
Pr
[
B
(
X
,
X
)]
=
[
X
=
x
]
·
χ
(
B
(
x
,
x
))
where
1 if event
B
holds, and equals zero oth-
erwise. For example, for every random variable
X
,wehave
χ
is an indicator function, so that
χ
(
B
)
=
Pr
[
X
=
X
]
=
1. We stress
that if one wishes to discuss the probability that
B
(
x
y
) holds when
x
and
y
are chosen
independently with the same probability distribution, then one needs to define
two
inde-
pendent random variables, both with the same probability distribution. Hence, if
X
and
Y
are two independent random variables, then
,
Pr
[
B
(
X
,
Y
)] denotes the probability that
Pr
·
Pr
B
(
x
,
y
) holds when the pair (
x
,
y
) is chosen with probability
[
X
=
x
]
[
Y
=
y
].
Namely,
x
,
y
Pr
Pr
[
B
(
X
,
Y
)]
=
[
X
=
x
]
·
Pr
[
Y
=
y
]
·
χ
(
B
(
x
,
y
))
For example, for every two independent random variables,
X
and
Y
,wehave
Pr
1 only if both
X
and
Y
are trivial (i.e., assign the entire probability
mass to a single string).
[
X
=
Y
]
=
Typical Random Variables.
Throughout this entire topic,
U
n
denotes a random vari-
able uniformly distributed over the set of strings of length
n
. Namely,
Pr
[
U
n
=
α
] equals
2
−
n
n
, and equals zero otherwise. In addition, we shall occasionally use
random variables (arbitrarily) distributed over
{
0
,
1
}
if
α
∈{
0
,
1
}
n
l
(
n
)
or
{
0
,
1
}
for some function
l
:
N→N
. Such random variables are typically denoted by
X
n
,
Y
n
,
Z
n
, etc. We stress that in
some cases
X
n
is distributed over
{
,
}
n
, whereas in others it is distributed over
{
,
}
l
(
n
)
,
0
1
0
1
for some function
l
(
), which is typically a polynomial. Another type of random variable,
the output of a randomized algorithm on a fixed input, is discussed in Section 1.3.
·
1.2.2. Three Inequalities
The following probabilistic inequalities will be very useful in the course of this topic.
All inequalities refer to random variables that are assigned real values. The most ba-
sic inequality is the
Markov inequality
, which asserts that for random variables with
bounded maximum or minimum values, some relation must exist between the devia-
tion of a value from the expectation of the random variable and the probability that the
random variable is assigned this value. Specifically, letting
=
v
Pr
(
X
)
def
E
[
X
=
v
·
v
]
denote the expectation of the random variable
X
, we have the following:
Markov Inequality:
Let X be a non-negative random variable and
v
a real
number. Then
≤
E
(
X
)
v
Pr
[
X
≥
v
]
1
Equivalently,
Pr
[
X
≥
r
·
E
(
X
)]
≤
r
.
