RSA/Rabin Bits are 1/2 + 1 / Poly (Log N) Secure
- 1 January 1984
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 449-457
- https://doi.org/10.1109/sfcs.1984.715947
Abstract
We prove that RSA least significant bit is 1/2 + (1/[logc N]) secure, for any constant c (where N is the RSA modulus). This means that an adversary, given the ciphertext, cannot guess the least sigiiilicatnt bit of the plaintext with probability better than 1/2 + (1/[logc N]), unless he can break RSA.Keywords
This publication has 13 references indexed in Scilit:
- Efficient And Secure Pseudo-Random Number GenerationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- How to construct random functionsJournal of the ACM, 1986
- Probabilistic encryptionJournal of Computer and System Sciences, 1984
- RSA bits are .732 + ε securePublished by Springer Science and Business Media LLC ,1984
- On the cryptographic security of single RSA bitsPublished by Association for Computing Machinery (ACM) ,1983
- How discreet is the discrete log?Published by Association for Computing Machinery (ACM) ,1983
- Comparison of Two Pseudo-Random Number GeneratorsPublished by Springer Science and Business Media LLC ,1983
- Coin flipping by telephone a protocol for solving impossible problemsACM SIGACT News, 1983
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- New directions in cryptographyIEEE Transactions on Information Theory, 1976