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. We briefly discuss a related result for bit security of the discrete logarithm. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1109/SFCS.1998.743502 | FOCS '98 Proceedings of the 39th Annual Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
individual rsa bits,related result,individual bit,polynomial time reduction,non-negligible advantage,single bit,bit security,rsa encrypted message,discrete logarithm,cryptography,information analysis,polynomial time,polynomials,information security | Discrete mathematics,Cryptography,Computer science,Encryption,Key size,Discrete logarithm,Polynomial-time reduction | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-8186-9172-7 | 38 |
PageRank | References | Authors |
6.55 | 4 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Johan Håstad | 1 | 3586 | 557.23 |
Mats Näslund | 2 | 141 | 21.58 |