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 exponentiationdiscrete logarithmhard core predicatessimultaneous securitypseudorandom generatorfactoring assumption.
Contact author(s)
oded @ narkis wisdom weizmann ac il
History
2000-12-07: received
Short URL
https://ia.cr/2000/064
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2000/064}},
      url = {https://eprint.iacr.org/2000/064}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.