Welcome to the resource topic for 1999/019
Title:
Security of all RSA and Discrete Log Bits
Authors: 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.
ePrint: https://eprint.iacr.org/1999/019
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .