Cryptography Reference
In-Depth Information
when the legitimate parties use pseudorandom sequences. The benefit
in such a substitution (of random sequences by pseudorandom ones) is
that the latter sequences can be eciently generated using much less
true randomness. Furthermore,
in an interactive setting
, it is possible
to eliminate all random steps from the on-line execution of a program,
by replacing them with the generation of pseudorandom bits based on
a random seed selected and fixed off-line (or at set-up time).
Various cryptographic applications of pseudorandom generators will
be presented in the sequel, but first let us show a construction of
pseudorandom generators based on the simpler notion of a one-way
function. Using Theorem 2.5, we may actually assume that such a func-
tion is accompanied by a hard-core predicate. We start with a simple
construction that suces for the case of 1-1 (and length-preserving)
functions.
Theorem 3.3.
((31; 123), see (65, Sec. 3.4)):
Let
f
be a 1-1 function
that is length-preserving and e
ciently computable, and
b
be a hard-
core predicate of
f
.Then
G
(
s
)=
b
(
s
)
b
(
f
(
|s|
)
−
1
(
s
)) is a
pseudorandom generator (with stretch function
), where
f
i
+1
(
x
)
·
b
(
f
(
s
))
···
de
=
f
(
f
i
(
x
)) and
f
0
(
x
)
de
=
x
.
As a concrete example, consider the permutation
1
x
2
mod
N
,
where
N
is the product of two primes each congruent to 3 (mod 4),
and
x
is a quadratic residue modulo
N
. Then, we have
G
N
(
s
)=
lsb(
s
)
x
→
lsb(
s
2
(
|s|
)
−
1
mod
N
), where lsb(
x
)istheleast
significant bit of
x
(which is a hard-core of the modular squaring func-
tion (3)).
lsb(
s
2
mod
N
)
·
···
Proof sketch of Theorem 3.3:
We use the fundamental fact that
asserts that the following two conditions are equivalent:
1
It is a well-known fact (cf., (65, Apdx. A.2.4)) that, for such
N
's, the mapping
x
→
x
2
mod
N
is a permutation over the set of quadratic residues modulo
N
.
