Cryptology ePrint Archive: Report 2000/064

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

Oded Goldreich and Vered Rosen

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.

Category / Keywords: foundations / Modular exponentiation, discrete logarithm, hard core predicates, simultaneous security, pseudorandom generator, factoring assumption.

Date: received 7 Dec 2000

Contact author: oded at narkis wisdom weizmann ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20001207:181838 (All versions of this report)

Short URL: ia.cr/2000/064

Discussion forum: Show discussion | Start new discussion