On the cryptographic security of single RSA bits

ABSTRACT

The ability to “hide” one bit in trapdoor functions has recently gained much interest in cryptography research, and is of great importance in many transactions protocols. In this paper we study the cryptographic security of RSA bits. In particular, we show that unless the cryptanalyst can completely break the RSA encryption, any heuristic he uses to determine the least significant bit of the cleartext must have an error probability greater than 1&edivide;4—&egr; A similar result is shown for Rabin's encryption scheme.

REFERENCES

• 1: Blum, M. and S. Micali, "How to Generate Cryptographically Strong Sequences of Pseudo Random Bits", Proceedings of the 23rd FOCS, 1982.
• 2: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• 3: Goldwasser, S., S. Micali and P. Tong, "Why and How to establish a Private Code On a Public Network" (extended abstract), Proceedings of the 23rd FOCS, 1982.
• 4: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 5: Long, D. and A. Widgerson, "How Discreet is the Discrete Log?", these proceedings.
• 6: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 7: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 8: Schmidt, W.A., Equations Over Finite Fields, An Elementary Approach, Springer-Verlag, Lecture Notes in Math. 536, 1976.
• 9: Yao, A., "Theory and Applications of Trapdoor Functions," Proceedings of the 23rd FOCS, 1982.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Standards (e.g., DES, PGP, RSA)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Security