Security of all RSA and Discrete Log Bits

Johan Hastad; Mats Naslund

Paper 1999/019 Original: eprint.iacr.org/1999/019 ↗

Security of all RSA and Discrete Log Bits

Johan Hastad

Mats Naslund

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 1999-08-27: last updated; 1999-08-27: published
Short URL: https://ia.cr/1999/019
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:1999/019,
      author = {Johan Hastad and Mats Naslund},
      title = {Security of all RSA and Discrete Log Bits},
      howpublished = {Cryptology {ePrint} Archive, Paper 1999/019},
      year = {1999},
      url = {https://eprint.iacr.org/1999/019}
}