You are looking at a specific version 20001207:181837 of this paper.
See the latest version.
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
-
CC BY