Cryptography Reference
In-Depth Information
(G(
(
))
=
(
))
≤
/
+
negl
(
),
Pr
f
x
B
x
1
2
t
where the probability is taken over a random uniform choice of
x
of length
t
and
over the random bits of
G
.
The idea behind the definition of hard-core predicate—which can be extended in
a straightforward way to a family of one-way functions, see [90, Definition 2.50]—is
the following. A (candidate) one-way function
f
does not necessarily hide everything
about
x
,given
f
(
x
)
. For example:
g
x
mod
p
, where
p
is a prime and
g
a primitive root modulo
p
. Use the Legendre
symbol to show how the least significant bit of
x
can be efficiently computed from
dexp
(
: Z
p
−
1
→ Z
p
given by
dexp
(
Exercise 3.13
Let
dexp
be the function
f
x
)
=
x
)
.
But, if
f
is one-way and hence a randomly chosen
x
is hard to compute from
f
(
x
)
, it seems that there should at least be one bit of
x
which is hard to guess from
. So the idea of Definition 3.12 is to select specific bits in
x
that are hard to
compute given
f
f
(
x
)
.
By a theorem of Goldreich and Levin ([86, Theorem 2.5.2], [6, Theorem 9.12),
a one-way function can be modified to have a hard-core predicate. In particular,
this applies to one-way permutations and so Theorem 3.4 is a consequence of the
following more explicit version ([86, Proposition 3.4.3]):
(
x
)
}
∗
→{
}
∗
Theorem 3.5
Let f
:{
0
,
1
0
,
1
be a length-preserving one-way permuta-
}
∗
→{
tion with hard-core predicate B
:{
0
,
1
0
,
1
}
. Then for every polynomial-time
computable function
: N → N
such that
(
t
)>
t for every t
∈ N
, the function
}
∗
→{
}
∗
defined, for x
t
,by
G
:{
0
,
1
0
,
1
∈{
0
,
1
}
f
2
f
(
t
)
−
1
G
(
x
)
=
B
(
x
)
B
(
f
(
x
))
B
(
(
x
)) . . .
B
(
(
x
)),
where we denote the concatenation of bits by juxtaposing them, is a PRG.
The proof proceeds by showing that we can first construct a PRG of stretch
(
1 (also called an
extender
), see for example, [90, Theorem 3.4], [109,
Theorem 6.22], and then iterating this construction.
Now, in order to apply this theorem to actually build a PRG, we need a length-
preserving one-way permutation with hard-core predicate. The best candidate is the
modular square function defined on
t
)
=
t
+
Z
n
, the group of units of
Z
n
, for a composite
∈ Z
n
can be computed efficiently as
it only requires an integer multiplication followed by the corresponding reduction
mod
n
. However, as Rabin showed already in 1979, computing modular square roots
is presumed hard when
n
is composite or, in other words, the function
x
∈ Z
n
, its square
x
2
mod
n
integer
n
.Given
x
x
2
mod
n
is one-way assuming factoring is hard (we will give a more precise formulation of
this hypothesis below). Assuming that this is indeed the case, we still have some-
thing missing in order to be able to apply Theorem 3.5 because it is necessary that
→
