Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISCRETE LOGARITHM:
Reports tagged with Discrete logarithm:
TR98-033 | 12th June 1998
C.P. Schnorr

Security of Allmost ALL Discrete Log Bits

Let G be a finite cyclic group with generator \alpha and with
an encoding so that multiplication is computable in polynomial time. We
study the security of bits of the discrete log x when given \exp_{\alpha}(x),
assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way.
... more >>>


TR99-037 | 27th August 1999
Johan Hastad, Mats Näslund

The Security of all RSA and Discrete Log Bits

We study the security of individual bits in an
RSA encrypted message $E_N(x)$. We show that given $E_N(x)$,
predicting any single bit in $x$ with only a non-negligible
advantage over the trivial guessing strategy, is (through a
polynomial time reduction) as hard as breaking ... more >>>


TR01-007 | 7th December 2000
Vered Rosen

On the Security of Modular Exponentiation

Comments: 1

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 ... more >>>


TR02-049 | 4th August 2002
Oded Goldreich, Vered Rosen

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

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 ... more >>>




ISSN 1433-8092 | Imprint