Security of all RSA and Discrete Log Bits

Johan Hastad; Mats Naslund

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 1999/019

Security of all RSA and Discrete Log Bits

Johan Hastad and 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): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: public key encryption RSA discrete log bit security hard core.
Contact author(s): mats naslund @ era-t ericsson se
History: 1999-08-27: received
Short URL: https://ia.cr/1999/019
License: CC BY

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},
      note = {\url{https://eprint.iacr.org/1999/019}},
      url = {https://eprint.iacr.org/1999/019}
}