International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Vered Rosen

Publications

Year
Venue
Title
2003
JOFC
2000
EPRINT
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators
Oded Goldreich Vered Rosen
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.

Coauthors

Oded Goldreich (2)