ECCC-Report TR02-049https://eccc.weizmann.ac.il/report/2002/049Comments and Revisions published for TR02-049en-usMon, 05 Aug 2002 11:49:28 +0300
Paper TR02-049
| On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators |
Oded Goldreich,
Vered Rosen
https://eccc.weizmann.ac.il/report/2002/049Assuming 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.
Mon, 05 Aug 2002 11:49:28 +0300https://eccc.weizmann.ac.il/report/2002/049