Cryptography Reference
In-Depth Information
additional information that goes beyond the group structure we are dealing with,
namely, we also use the multiplication defined on
Z
p
and this is why this method
cannot be extended to generic cyclic groups. On the other hand, we also remark that
the fact that
Z
p
has prime order is not essential here and the computation of discrete
logarithms is also easy in any
Z
t
even if
t
is not prime.
Exercise 3.12
Suppose that
f
is a length-preserving one-way function and
g
a
length-preserving permutation such that
g
is efficiently computable for each
x
.
Determine whether each of the compositions
f
(
x
)
f
, is a one-way function.
What happens if the permutation
g
is not efficiently computable? Determine also
whether the composition of two length-preserving one-way functions is one-way.
◦
g
,
g
◦
3.3.3 From One-Way Functions to Pseudo-Random
Generators: The Blum-Blum-Shub PRG
We have already mentioned that PRGs can be obtained from one-way functions and
this is the basic idea used in cryptography to obtain them. The fact that the existence
of one-way functions implies that of PRGs—they are in fact equivalent—was proved
by Håstad, Impagliazzo, Levin and Luby in the 1990s but for the PRGwe want to use
we only need the following weaker result which assumes the existence of a length-
preserving one-way permutation (instead of a one-way function, see [6, Lemma
9.10], [90, Theorem 3.4], [86, Theorem 3.5.1], [109, Corollary 6.11]):
}
∗
be a length-preserving one-way permuta-
tion. Then, for every polynomial-time computable function
}
∗
→{
Theorem 3.4
Let f
:{
0
,
1
0
,
1
: N → N
such that
}
∗
→{
}
∗
with stretch
(
t
)>
t for all t
∈ N
, there exists a PRG G
:{
0
,
1
0
,
1
.
A more explicit version of this result that enables us to actually construct a PRG
can be obtained if we analyze the way in which the preceding theorem is proved. For
this we need some additional notions related to one-way functions.
Definition 3.11
A
predicate
is a function:
}
∗
→{
B
:{
0
,
1
0
,
1
}
,
i.e., a function that acts on bit strings and whose output is a single bit.
Now let
f
be a one-way function. A
hard-core predicate
of
f
is a predicate that
is difficult to compute given only
f
(
x
)
but easy to compute given
x
. More formally:
}
∗
Definition 3.12
A predicate
B
:{
0
,
1
→{
0
,
1
}
is a
hard-core predicate
of a
}
∗
→{
}
∗
if the following conditions hold:
function
f
:{
0
,
1
0
,
1
}
∗
.
1. There exists a PPT algorithm
A
such that
A(
x
)
=
B
(
x
)
for every
x
∈{
0
,
1
G
2. For every PPT algorithm
, there exists a negligible function
negl
such that
