International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Oded Goldreich
Vered Rosen
Download:
URL: http://eprint.iacr.org/2000/064
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2000-11408,
  title={On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators},
  booktitle={IACR Eprint archive},
  keywords={foundations / Modular exponentiation, discrete logarithm, hard core predicates, simultaneous security, pseudorandom generator, factoring assumption.},
  url={http://eprint.iacr.org/2000/064},
  note={ oded@narkis.wisdom.weizmann.ac.il 11298 received 7 Dec 2000},
  author={Oded Goldreich and Vered Rosen},
  year=2000
}