Cryptography Reference
In-Depth Information
first. Suppose that for some polynomials
s
and
p
there exist infinitely many
's violat-
ing Eq. (3.5). Then there exists an infinite set
N
such that for every
n
∈
N
, there exists
a string
w
n
∈{
0
,
1
}
w
def
=
C
w
n
, we obtain a contradiction
n
violating Eq. (3.5). Letting
C
n
to the requirement of the definition.
We note that allowing probabilistic circuits in the preceding definition does not
increase its power (see Exercise 8). Consequently, in accordance with our meta-
theorem (see Section 1.3.3), indistinguishability by polynomial-size circuits (as per
Definition 3.2.7) implies indistinguishability by probabilistic polynomial-time ma-
chines (as per Definition 3.2.2); see Exercise 10. The converse is false (see Exercise 10).
Finally, we note that indistinguishability by polynomial-size circuits is preserved
under repeated experiments, even if both ensembles are not efficiently constructible
(see Exercise 9).
3.2.5. Pseudorandom Ensembles
One special, yet important, case of computationally indistinguishable pairs of ensembles
is the case in which one of the ensembles is uniform. Ensembles that are computationally
indistinguishable from a uniform ensemble are called pseudorandom. Recall that
U
m
denotes a random variable uniformly distributed over the set of strings of length
m
.
The ensemble
{
U
n
}
n
∈N
is called the
standard uniform ensemble.
Yet, it will also be
convenient to call
uniform
those ensembles of the form
{
U
l
(
n
)
}
n
∈N
, where
l
:
N → N
.
Definition 3.2.8 (Pseudorandom Ensembles):
The ensemble X
={
X
n
}
n
∈N
is
called
pseudorandom
if there exists a uniform ensemble U
={
U
l
(
n
)
}
n
∈N
such
that X and U are indistinguishable in polynomial time.
We stress that
|
X
n
|
is not necessarily
n
(whereas
|
U
m
|=
m
). In fact, for polynomial-
time-computable
l
:
N → N
and
X
={
X
n
}
n
∈N
as in Definition 3.2.8, with very high
probability,
|
X
n
|
equals
l
(
n
).
In the foregoing definition, as well as in the rest of this topic, pseudorandomness is
shorthand for
pseudorandomness with respect to polynomial time
.
3.3. Definitions of Pseudorandom Generators
A pseudorandom ensemble, as defined here, can be used instead of a uniform ensem-
ble in any efficient application, with, at most, negligible degradation in performance
(otherwise the efficient application can be transformed into an efficient distinguisher
of the supposedly pseudorandom ensemble from the uniform one). Such a replace-
ment is useful only if we can generate pseudorandom ensembles at a lower cost than
that required to generate the corresponding uniform ensemble. The cost of generating
an ensemble has several aspects. Standard cost considerations include the time and
space complexities. However, in the context of randomized algorithms, and in particu-
lar in the context of generating probability ensembles, a major cost consideration is the
quantity and quality of the random source used by the algorithm. In particular, in many
