ECCC-Report TR01-007https://eccc.weizmann.ac.il/report/2001/007Comments and Revisions published for TR01-007en-usFri, 11 May 2001 12:30:06 +0300
Comment 1
| A pointer to an ePrint posting Comment on: TR01-007 |
Vered Rosen
https://eccc.weizmann.ac.il/report/2001/007#comment1Fri, 11 May 2001 12:30:06 +0300https://eccc.weizmann.ac.il/report/2001/007#comment1
Paper TR01-007
| On the Security of Modular Exponentiation |
Vered Rosen
https://eccc.weizmann.ac.il/report/2001/007Assuming 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.
Wed, 10 Jan 2001 16:00:04 +0200https://eccc.weizmann.ac.il/report/2001/007