Cryptography Reference
In-Depth Information
and
H
n
−
l
(
n
)
p
(
n
)
U
l
(
n
)
+
1
n
∈N
H
n
−
l
(
n
)
p
(
n
)
(
f
(
U
n
))
,
,
are polynomial-time-indistinguishable.
Proof Idea:
Use a reducibility argument. If the claim does not hold, then con-
tradiction of the hypothesis that
g
is a hard-core of
f
is derived. Specifically,
given an algorithm
D
that violates the claim, we construct an algorithm
D
that,
on input (
y
,
z
), uniformly selects
h
∈
S
n
−
l
(
n
)
p
(
n
)
and outputs
D
(
h
(
y
)
,
h
,
z
). Then
D
distinguishes between
{
(
f
(
U
n
)
,
g
(
U
n
))
}
n
∈N
and
{
(
f
(
U
n
)
,
U
l
(
n
)
+
1
)
}
n
∈N
.
Claim 3.5.3.2:
The statistical difference between the random variables
H
n
−
l
(
n
)
,
U
l
(
n
)
+
1
(
f
(
U
n
))
,
H
n
−
l
(
n
)
p
(
n
)
p
(
n
)
and
U
n
−
l
(
n
)
,
H
n
−
l
(
n
)
,
U
l
(
n
)
+
1
p
(
n
)
is bounded by 2
·
2
−
l
(
n
)
/
3
.
Proof Idea:
Use the hypothesis that
S
n
−
l
(
n
)
p
(
n
)
is a hashing family, and apply
Lemma 3.5.1. Specifically, use
δ
=
2
−
l
(
n
)
/
3
, note that
[
f
(
U
n
)
=
y
]
≤
2
−
n
for
every
y
, and count separately the contributions of bad and non-bad
h
's to the
statistical difference between (
H
n
−
l
(
n
)
Pr
,
H
n
−
l
(
n
)
) and (
U
n
−
l
(
n
)
,
H
n
−
l
(
n
)
(
f
(
U
n
))
).
p
(
n
)
p
(
n
)
p
(
n
)
Because the statistical difference is a bound on the ability of algorithms to dis-
tinguish, the proposition follows.
Extension.
Proposition 3.5.3 can be extended to the case in which the function
f
is
polynomial-to-1 (instead of 1-to-1). Specifically, let
f
satisfy
|
f
−
1
(
f
(
x
))
|
<
q
(
|
x
|
) for
some polynomial
q
(
·
) and all sufficiently long
x
's. The modified proposition asserts
that
for every probabilistic polynomial-time algorithm A, every polynomial p
(
·
)
, and
all sufficiently large n's,
1
p
(
n
)
l
(
n
)
−
log
2
q
(
n
)
3
2
−
|
Pr
[
A
(
G
(
U
n
,
U
k
))
=
1]
−
Pr
[
A
(
U
n
+
k
+
1
)
=
1]
|
<
2
·
+
where k is as in Proposition 3.5.3
.
3.5.1.3. Obtaining Pseudorandom Generators
With Proposition 3.5.3 proved, we consider the possibility of applying it in order to con-
struct pseudorandom generators. We stress that applying Proposition 3.5.3 with length
function
l
(
1.
By Theorem 2.5.6 (in Section 2.5.3), such hard-core functions exist essentially for all
one-way functions, provided that
l
(
·
) requires having a hard-core function
g
for
f
, with
|
g
(
x
)
|=
l
(
|
x
|
)
+
) is logarithmic. (Actually, Theorem 2.5.6 asserts
that such hard-cores exist for a modification of any one-way function, where the mod-
ified function preserves the 1-1 property of the original function.) Hence, combining
139
·
