__
TR02-049 | 4th August 2002 00:00
__

#### On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

**Abstract:**
Assuming the inractability of factoring, we show that

the output of the exponentiation modulo a composite function

$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,

even when its input is restricted to be half the size.

This result is equivalent to the simultaneous hardness of the upper

half of the bits of $f_{N,g}$,

proven by Hastad, Schrift and Shamir.

Yet, we supply a different proof that is significantly simpler

than the original one. In addition, we suggest a pseudorandom generator

which is more efficient than all previously known factoring

based pseudorandom generators.

This is a revised and partial version of TR01-007.