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
.