Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-037 | 27th August 1999 00:00

The Security of all RSA and Discrete Log Bits

RSS-Feed




TR99-037
Authors: Johan Håstad, Mats Näslund
Publication: 17th September 1999 15:00
Downloads: 4739
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint