Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR02-049 | 4th August 2002 00:00

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

TR02-049
Authors: Oded Goldreich, Vered Rosen
Publication: 5th August 2002 11:49
Keywords:

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.

ISSN 1433-8092 | Imprint