The security of all RSA and discrete log bits.

The security of all RSA and discrete log bits.

We study the security of individual bits in an RSA encrypted message EN(x). We show that given EN(x), predicting any single bit in x with only a nonnegligible advantage over the trivial guessing strategy, is (through a polynomial-time reduction) as hard as breaking RSA. Moreover, we prove that block...

Descrición completa

Detalles Bibliográficos
Publicado en:Journal of the ACM 51, 2 (2004).
Autor Principal: Håstad, Johan
Formato: Artigo
Idioma:English
Subjects:
Data.
Data encryption.
Public key cryptosystems.
Theory of computation.
Analysis of algorithms and problem complexity.
Numerical algorithms and problems.
Number-theoretic computations (e.g., factoring, primality testing).
Security.
Theory.