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 .        Search WWH ::

Custom Search