Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-049 | 4th August 2002 00:00

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



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.

ISSN 1433-8092 | Imprint