TR99-037 Authors: Johan Håstad, Mats Näslund

Publication: 17th September 1999 15:00

Downloads: 4828

Keywords:

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 RSA\@. Moreover, we

prove that blocks of $O(\log \log N)$ bits of $x$ are

computationally indistinguishable from random bits. The results

carry over to the Rabin encryption scheme.

Considering the discrete exponentiation function $g^x$ modulo $p$, with

probability $1-o(1)$ over random choices of the prime $p$, the

analog results are demonstrated. Finally, we prove that the

bits of $ax+b$ modulo $p$ give hard core predicates for any one-way

function $f$.