Cryptography Reference
In-Depth Information
2.
Pseudorandomness:
For every probabilistic polynomial-time oracle machine M ,
every polynomial p
(
·
)
, and all sufficiently large n's,
Pr
M
F
n
(1
n
)
1
− Pr
M
H
n
(1
n
)
1
<
1
p
(
n
)
=
=
where F
n
is a random variable uniformly distributed over the multi-set
{
f
s
}
s
∈{
0
,
1
}
n
,
and H
n
is uniformly distributed
9
among all functions mapping arbitrary long
strings to r
(
n
)
-bit-long strings.
A few comments regarding Definition 3.6.12 are in order. First, note that the fact that
the length of the input to
f
s
is not known a priori raises no problems in Item 1, since
the running time of the evaluating algorithm may depend (polynomially) on the length
of the input to
f
s
. Regarding Item 2, because
M
has a-priori-bounded (polynomial)
running time, that upper-bounds the length of the queries made to the oracle. The latter
fact resolves a technical problem that arises in the earlier definition (see footnote 9 ).
In typical applications, one uses
r
(
n
)
n
(or
r
(
n
) that is polynomially related to
n
).
Another special case of interest is the case where
r
=
≡
1, that is, the case of pseudorandom
Boolean functions.
Similarly to Constructions 3.6.5 and 3.6.10, for any
r
:
such that
r
(
n
)is
computable in poly(
n
) time from
n
, we can construct unbounded-input pseudorandom
functions using any pseudorandom generator. Specifically:
N → N
Construction 3.6.13:
Let G be a deterministic algorithm expanding inputs of
length n into strings of length
2
n
+
r
(
n
)
. We denote by G
0
(
s
)
the
|
s
|
-bit-long
prefix of G
(
s
)
,byG
1
(
s
)
the next
|
s
|
bits in G
(
s
)
, and by G
2
(
s
)
the r
(
|
s
|
)
-bit-long
suffix of G
(
s
)(
i.e., G
(
s
)
=
G
0
(
s
)
G
1
(
s
)
G
2
(
s
))
. Then for every s
∈{
0
,
1
}
n
,we
define a function f
s
:
{
0
,
1
}
∗
→{
0
,
1
}
r
(
n
)
such that for every non-negative integer
d and every
σ
1
,...,σ
d
∈{
0
,
1
}
,
G
2
G
σ
d
G
σ
2
G
σ
1
(
s
)
σ
1
σ
2
···
σ
d
)
def
f
s
(
=
···
···
Pictorially, the function
f
s
is defined by walks down an infinite ternary tree having labels
at the vertices. Internal vertices have
)-bit-long
labels. The root of the tree, hereafter referred to as the level-0 vertex of the tree, is labeled
by the string
s
. If an internal vertex is labeled
s
, then its leftmost child is labeled
G
0
(
s
),
its middle child is labeled
G
1
(
s
), and its rightmost child is labeled
G
2
(
s
). The first
two children of each internal vertex are internal vertices, whereas the rightmost child
of an internal vertex is a leaf. The value of
f
s
(
|
s
|
-bit-long labels, and leaves have
r
(
|
s
|
σ
1
···
σ
d
) is the string residing in the leaf
reachable from the root by “following the path
2,” when the root is labeled
by
s
. Again, by extending the proof of Theorem 3.6.6, we obtain the following:
σ
1
,...,σ
d
,
9
Since the running time of
M
is a priori bounded by some polynomial, it follows that for some polynomial
d
and all
n
's, it holds that, on input 1
n
, machine
M
makes only queries of length at most
d
(
n
). Thus,
H
n
can be
defined as the uniform distribution over all functions mapping strings of length up to
d
(
n
)to
r
(
n
)-bit-long strings.
This resolves the technical problem of what is meant by a uniform distribution over an infinite set (i.e., the set of
all functions mapping arbitrary long bit strings to
r
(
n
)-bit-long strings).
