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

Oded Goldreich; Vered Rosen

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

Metadata

Available format(s): PS
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: Modular exponentiation discrete logarithm hard core predicates simultaneous security pseudorandom generator factoring assumption.
Contact author(s): oded @ narkis wisdom weizmann ac il
History: 2000-12-07: received
Short URL: https://ia.cr/2000/064
License: CC BY

BibTeX

@misc{cryptoeprint:2000/064,
      author = {Oded Goldreich and Vered Rosen},
      title = {On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/064},
      year = {2000},
      url = {https://eprint.iacr.org/2000/064}
}