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...

Descripció completa

Dades bibliogràfiques
Publicat a:Journal of the ACM 51, 2 (2004).
Autor principal: Håstad, Johan
Format: Article
Idioma:English
Matèries:
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.