Cryptography Reference
In-Depth Information
remaining stages (of Construction 3.6.5). The random variable
H
n
is uniformly
distributed over the (2
n
)
2
k
possible functions (corresponding to all possible choices
of
s
1
,
s
2
,...,
s
2
k
n
). Namely,
∈{
0
,
1
}
def
=
f
U
(1)
n
H
n
,...,
U
(2
k
)
n
where
U
(
j
)
n
's are independent random variables, each uniformly distributed over
{
n
.
At this point it is clear that
H
n
is identical with
F
n
, whereas
H
n
is identical
to
H
n
. Again, as is usual in the hybrid technique, the ability to distinguish the
extreme hybrids yields the ability to distinguish a pair of neighboring hybrids.
This ability is further transformed so that contradiction to the pseudorandomness
of
G
is reached. Further details follow.
We assume, in contradiction to the theorem, that the function ensemble
F
is
not pseudorandom. It follows that there exists a probabilistic polynomial-time
oracle machine
M
and a polynomial
p
(
,
}
0
1
·
) such that for infinitely many
n
's,
=
Pr
M
H
n
(1
n
)
=
1
>
M
F
n
(1
n
)
=
1
−
Pr
1
p
(
n
)
(
n
)
def
Let
t
(
) be a polynomial bounding the running time of
M
(1
n
) (such a polynomial
exists because
M
is a polynomial-time machine). It follows that on input 1
n
, the
oracle machine
M
makes at most
t
(
n
) queries (since the number of queries is
clearly bounded by the running time). Using the machine
M
, we construct an
algorithm
D
that distinguishes the
t
(
·
·
)-product of the ensemble
{
G
(
U
n
)
}
n
∈N
from
the
t
(
·
)-product of the ensemble
{
U
2
n
}
n
∈N
as follows.
2
n
Algorithm
D
:
On input
t
(
n
)), algorithm
D
pro-
ceeds as follows. First,
D
selects uniformly
k
∈{
0
,
1
,...,
n
−
1
}
. This random
choice, hereafter called the
checkpoint
, is the only random choice made by
D
it-
self. Next, algorithm
D
invokes the oracle machine
M
(on input 1
n
) and answers
M
's queries as follows. The first query of machine
M
, denoted
q
1
, is answered by
G
σ
n
···
G
σ
k
+
2
P
σ
k
+
1
(
α
1
)
···
α
1
,...,α
t
∈{
0
,
1
}
(with
t
=
where
q
1
=
σ
1
···
σ
n
,(
α
1
is the first input string) and
P
0
(
α
) (resp.,
P
1
(
α
)) denotes
the
n
-bit prefix of
α
(resp., the
n
-bit suffix of
α
). In addition, algorithm
D
records
this query (i.e.,
q
1
). Each subsequent query is answered by first checking to see
if its
k
-bit-long prefix equals the
k
-bit-long prefix of a previous query. In case the
k
-bit-long prefix of the current query, denoted
q
i
, is different from the
k
-bit-long
prefixes of all previous queries, we associate this prefix with a new input string
(i.e.,
α
i
). Namely, we answer query
q
i
by
G
σ
n
···
G
σ
k
+
2
P
σ
k
+
1
(
α
i
)
···
where
q
i
=
σ
1
···
σ
n
. In addition, algorithm
D
records the current query (i.e.,
q
i
). The other possibility is that the
k
-bit-long prefix of the
i
th query equals the
k
-bit-long prefix of some previous query. Let
j
be the smallest integer such that
the
k
-bit-long prefix of the
i
th query equals the
k
-bit-long prefix of the
j
th query
153
