Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-007 | 7th December 2000 00:00

On the Security of Modular Exponentiation

RSS-Feed

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(s):

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

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





Comment #1
Authors: Vered Rosen
Accepted on: 11th May 2001 12:30
Downloads: 771
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint