Cryptography Reference
In-Depth Information
Proof Outline:
The proof is analogous to the proof of Proposition 3.4.3. Specifi-
cally, we let
G
i
(
x
)
f
t
−
1
i
x
) (the reverse of
G
i
(
x
)) and prove
=
B
(
i
,
(
x
))
···
B
(
i
,
f
p
(
n
)
I
n
that even when given
I
n
and
(
X
n
) as auxiliary inputs, the sequence
G
p
(
n
)
I
n
(
X
n
) is unpredictable in polynomial time. This is done by a reducibility
argument: An algorithm predicting the next bit of
G
p
(
n
)
(
X
n
), given also
I
n
and
I
n
f
p
(
n
)
I
n
(
X
n
), is used to construct an algorithm for predicting
B
(
I
n
,
X
n
) from
I
n
and
f
I
n
(
X
n
), which contradicts the hypothesis by which
B
is a hard-core predicate
for the collection (
I
,
D
,
F
). The extra hypothesis by which
D
(
i
) is uniformly
distributed over
D
i
is used in order to establish that the distributions
D
(
i
) and
f
j
i
(
D
(
i
)) are identical
2
for every
j
<
t
. The reader should be able to complete
the argument.
Generalization.
Proposition 3.4.6 and Theorem 3.4.5 remain valid even if one relaxes
the condition concerning the distribution of
D
(
i
) and requires only that
D
(
i
) be sta-
tistically close (as a function in
) to the uniform distribution over
D
i
. Similarly, one
can relax the condition regarding
I
so that the foregoing holds for all but a negligible
measure of the
i
's generated by
I
(1
n
) (rather than for all such
i
's).
|
i
|
3.4.2.2. Concrete Instantiations
As an immediate application of Construction 3.4.4, we derive pseudorandom generators
based on either of the following assumptions:
•
The intractability of the discrete-logarithm problem
: Specifically, we assume that the
DLP collection, as presented in Section 2.4.3, is one-way. The generator is based on the
fact that, under the foregoing assumption, the following problem is intractable: Given a
prime
P
, a primitive element
G
in the multiplicative group mod
P
, and an element
Y
in this group, guess whether or not there exists 0
G
x
mod
P
.
In other words, the latter predicate, denoted
B
P
, constitutes a hard-core for the DLP
collection.
The generator uses the seed in order to select a prime
P
, a primitive element
G
in the multiplicative group mod
P
, and an element
Y
of the group. It outputs the
sequence
≤
x
≤
P
/
2 such that
Y
≡
B
P
G
G
Y
mod
P
mod
P
,...
B
P
(
G
Y
,
,
B
P
(
Y
)
mod
P
)
G
Z
mod
P
.
•
The difficulty of inverting RSA
: Specifically, we assume that the RSA collection, as pre-
sented in Section 2.4.3, is one-way. The generator is based on the fact that under this
assumption, the least significant bit (denoted lsb) constitutes a hard-core for the RSA
collection.
The generator uses the seed in order to select a pair of primes (
P
That is, the function being iterated is
Z
→
,
Q
), an integer
e
relatively prime to
φ
(
N
)
=
(
P
−
1)
·
(
Q
−
1), and an element
X
in the multiplicative
2
We comment that weaker hypotheses can in fact suffice for that purpose. Alternatively, one can postulate that
the function
f
i
is hard to invert on the distribution
f
j
(
D
(
i
)) for every
j
<
t
.
i
