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. Our work provides also an evidence for the difficulty of the Decisional Diffie-Hellman problem, when considered modulo a composite.

Comment #1 to TR01-007 | 11th May 2001 12:30

A pointer to an ePrint posting Comment on: TR01-007

Abstract: