C.P. Schnorr

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

Johan Håstad, Mats Näslund

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

Vered Rosen

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

Oded Goldreich, Vered Rosen

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