Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pseudorandomgenerator:
TR02-049 | 4th August 2002
Oded Goldreich, Vered Rosen

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 ... more >>>

ISSN 1433-8092 | Imprint