Title :
The security of individual RSA bits
Author :
Håstad, Johan ; Näslund, Mats
Author_Institution :
NADA, R. Inst. of Technol., Stockholm, Sweden
Abstract :
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 non-negligible advantage over the trivial guessing strategy is (through a polynomial time reduction) as hard as breaking RSA. We briefly discuss a related result for bit security of the discrete logarithm
Keywords :
cryptography; RSA encrypted message; bit security; discrete logarithm; individual RSA bits security; polynomial time reduction; trivial guessing strategy; Cryptography; Electronic mail; Information analysis; Information security; Jacobian matrices; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-9172-7
DOI :
10.1109/SFCS.1998.743502
