Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-007 | 7th December 2000 00:00

#### On the Security of Modular Exponentiation

TR01-007
Authors: Vered Rosen
Publication: 10th January 2001 16:00
Keywords:

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