Cryptography Reference
In-Depth Information
Proof Sketch:
Intuitively, oracle access to
G
◦
H
n
is equivalent to being given
multiple independent samples from the distribution
G
(
U
n
), whereas oracle ac-
cess to
H
n
is equivalent to being given multiple independent samples from
the distribution
U
r
(
n
)
. Using the pseudorandomness of
{
G
(
U
n
)
}
n
∈N
, the claim
follows.
In the actual proof, we transform the oracle machine
M
into an ordinary ma-
chine
M
that gets a sequence of samples and emulates an execution of
M
while
using its input sequence in order to emulate some related oracle for
M
. Specif-
ically, on input
α
1
,...,α
T
, machine
M
invokes
M
, and answers its
i
th distinct
query with
α
i
. (Without loss of generality, we can assume that
M
never issues the
same query twice.)
1.
Indeed, on input a sequence of samples from distribution
G
(
U
n
), machine
M
emulates an execution of
M
G
◦
H
n
(1
n
).
(The key observation is that the responses of oracle
G
◦
H
n
to a sequence
q
t
of distinct queries are
G
(
s
q
1
)
G
(
s
q
t
), where the
s
q
i
's are uniformly
q
1
,...,
,...,
n
.)
2.
On the other hand, on input a sequence of samples from distribution
U
r
(
n
)
, machine
M
emulates an execution of
M
H
n
(1
n
).
(The key observation is that the responses of oracle
H
n
to a sequence
q
1
,...,
and independently distributed in
{
0
,
1
}
q
t
r
(
n
)
.)
of distinct queries are uniformly and independently distributed in
{
0
,
1
}
Thus, if
M
violates the statement of the claim, then
M
violates the pseudo-
randomness of
{
G
(
U
n
)
}
n
∈N
, in contradiction to the theorem's hypothesis.
Claim 3.6.11.2:
For every probabilistic polynomial-time oracle machine
M
,
every polynomial
p
(
·
), and all sufficiently large
n
's,
Pr
M
F
n
(1
n
)
=
1
<
M
G
◦
H
n
(1
n
)
=
1
−
Pr
1
p
(
n
)
Proof Sketch:
Any function
f
s
(as defined in Construction 3.6.10) can be written
as
f
s
(
x
)
=
G
(
f
s
(
x
)), where
f
s
is defined by
f
s
σ
1
σ
2
···
σ
d
(
n
)
def
=
G
σ
d
(
n
)
···
G
σ
2
G
σ
1
(
s
)
···
(3.16)
f
s
}
We have already established that
is a generalized pseudorandom function
ensemble (i.e.,
f
s
corresponds to the case where
G
is the identity), and so by
incorporating
G
in the distinguisher, the claim follows.
In the actual proof, we transform the oracle machine
M
into an oracle machine
M
that emulates
M
while using its own oracle in order to emulate some related
oracle for
M
. Specifically, when
M
issues a query
q
, machine
M
forwards
q
to
its own oracle, applies
G
to the answer that it receives, and forwards the result
to
M
.
{
1.
Indeed, when given oracle access to
h
, machine
M
emulates an execution of
M
G
◦
h
(1
n
) (the reason being that, in this case,
M
responds to query
q
(made by
