ECCC-Report TR99-037https://eccc.weizmann.ac.il/report/1999/037Comments and Revisions published for TR99-037en-usFri, 17 Sep 1999 15:00:51 +0200
Paper TR99-037
| The Security of all RSA and Discrete Log Bits |
Johan Håstad,
Mats Näslund
https://eccc.weizmann.ac.il/report/1999/037 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$.
Fri, 17 Sep 1999 15:00:51 +0200https://eccc.weizmann.ac.il/report/1999/037