Paper 2000/064 Original: eprint.iacr.org/2000/064 ↗
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators
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)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2000-12-07: last updated
- 2000-12-07: published
- Short URL
- https://ia.cr/2000/064
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}