Securely combining public-key cryptosystems

ABSTRACT

It is a maxim of sound computer-security practice that a cryptographic key should have only a single use. For example, an RSA key pair should be used only for public-key encryption or only for digital signatures, and not for both.In this paper we show that in many cases, the simultaneous use of related keys for two cryptosystems, e.g. for a public-key encryption system and for a public-key signature system, does not compromise their security. We demonstrate this for a variety of public-key encryption schemes that are secure against chosen-ciphertext attacks, and for a variety of digital signature schemes that are secure against forgery under chosen-message attacks. The precise form of the statement of security that we are able to prove depends on the particular cryptographic schemes in question and on the cryptographic assumptions needed for their proofs of security; but in every case, our proof of security does not require any additional cryptographic assumptions.Among the cryptosystems that we analyze in this manner are the public-key encryption schemes of Cramer and Shoup, Naor and Yung, and Dolev, Dwork, and Naor, which are all defined in them standard model, while in the random-oracle model we analyze plaintext-aware encryption schemes (as defined by Bellare and Rogaway) and in particular the OAEP+ cryptosystem. Among public-key signature schemes, we analyze those of Cramer and Shoup and of Gennaro, Halevi, and Rabin in the standard model, while in the random-oracle model we analyze the RSA PSS scheme as well as variants of the El Gamal and Schnorr schemes. (See references within.)

REFERENCES

• 1: Mihir Bellare , Anand Desai , David Pointcheval , Phillip Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.26-45, August 23-27, 1998
• 2: M.Bellare and P.Rogaway,Optimal Asymmetric Encryption Adv.in Cryptology -Proc.of Eurocrypt '94,Springer-Verlag LNCS 950,pp.92-111.
• 3: M.Bellare and P.Rogaway,The Exact Security of Digital Signatures:How to Sign with RSA and Rabin , Adv.in Cryptology -Proc.of Eurocrypt '96, Springer-Verlag LNCS 1070,pp.399-416.
• 4: E.Biham,New Types of Cryptanalytic Attacks Using Related Keys ,J.of Cryptology 7(4):229-246 (1994).
• 5: Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
• 6: Dan Boneh, Simplified OAEP for the RSA and Rabin Functions, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.275-291, August 19-23, 2001
• 7: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 8: Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, Proceedings of the 6th ACM conference on Computer and communications security, p.46-51, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319716]
• 9: G.Davida,Chosen Signature Cryptanalysis of the RSA (MIT)Public Key Cryptosystem ,TR-CS-82-2, Dept.of EECS,Univ.of Wisconsin,Milwaukee,1982.
• 10: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 11: C.Dwork and M.Naor,An E .cient Existentially Unforgeable Signature Scheme and Its Applications , Journal of Cryptology 11(3),pp.187-208 (1998).
• 12: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 13: Eiichiro Fujisaki , Tatsuaki Okamoto , David Pointcheval , Jacques Stern, RSA-OAEP Is Secure under the RSA Assumption, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.260-274, August 19-23, 2001
• 14: R.Gennaro,S.Halevi and Tal Rabin,Secure Hash-and-Sign Signature Without the Random Oracle ,Adv.in Cryptology -Pro .of Euro rypt '99, Springer-Verlag LNCS 1592,pp.123-139.
• 15: H.Krawczyk and T.Rabin,Chameleon hash functions , Theory of Cryptography Library:Record 98-10,1998.
• 16: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 17: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 18: D.Pointcheval and J.Stern,Security Proofs for Signature Schemes ,Adv.in Cryptology -Pro .of EUROCRYPT 1996,LNCS 1070,pp.387-398.
• 19: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 20: Charles Rackoff , Daniel R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.433-444, August 11-15, 1991
• 21: C.-P.S hnorr,E .cient Signature Generation by Smart Cards ,J.of Crypt.4(3),161-174 (1991).
• 22: V.Shoup,Using hash functions as a hedge against chosen ciphertext attacks ,Adv.in Cryptology -Pro . of Eurocrypt '2000,LNCS 1807,pp.275-288.
• 23: V.Shoup,OAEP Recon idered ,Adv.in Cryptology - Proc. of Crypto 2001.A more omplete version is available as:Cryptology ePrint Archive:Report 2000/060 (February 6,2001).

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

General Terms:
Algorithms, Design, Security