Stateful public-key cryptosystems: how to encrypt with one 160-bit exponentiation

ABSTRACT

We show how to significantly speed-up the encryption portion of some public-key cryptosystems by the simple expedient of allowing a sender to maintain state that is re-used across different encryptions.In particular we present stateful versions of the DHIES and Kurosawa-Desmedt schemes that each use only 1 exponentiation to encrypt, as opposed to 2 and 3 respectively in the original schemes, yielding the fastest discrete-log based public-key encryption schemes known in the random-oracle and standard models respectively. The schemes are proven to meet an appropriate extension of the standard definition of IND-CCA security that takes into account novel types of attacks possible in the stateful setting.

REFERENCES

• 1: M. Abe, R. Gennaro, K. Kurosawa and V. Shoup. Tag-KEM/DEM: A New Framework for Hybrid Encryption and a New Analysis of Kurosawa Desmedt KEM. EUROCRYPT '05, LNCS 3494, Springer-Verlag.
• 2: Michel Abdalla , Mihir Bellare , Phillip Rogaway, The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.143-158, April 08-12, 2001
• 3: J. An. Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses. Cryptology ePrint Archive: Report 2001/079.
• 4: Jee Hea An , Yevgeniy Dodis , Tal Rabin, On the Security of Joint Signature and Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.83-107, May 02, 2002
• 5: M. Bellare, A. Boldyreva and A. Palacio. An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. EUROCRYPT '04, LNCS 3027, Springer-Verlag.
• 6: Mihir Bellare , Alexandra Boldyreva , Jessica Staddon, Randomness Re-use in Multi-recipient Encryption Schemeas, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.85-99, January 06-08, 2003
• 7: Mihir Bellare , Ran Canetti , Hugo Krawczyk, Keying Hash Functions for Message Authentication, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.1-15, August 18-22, 1996
• 8: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 9: 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
• 10: M. Bellare, T. Kohno and V. Shoup. Stateful Public-Key Cryptosystems: How to Encrypt with One 160-bit Exponentiation. Full version of this paper. Cryptology ePrint Archive: Report 2006/267.
• 11: M. Bellare and C. Namprempre. Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm. ASIACRYPT '00, LNCS 1976, Springer-Verlag.
• 12: M. Bellare and P. Rogaway. Code-Based Game-Playing Proofs and the Security of Triple Encryption. EUROCRYPT '06, LNCS 4004, Springer-Verlag.
• 13: Mihir Bellare , Phillip Rogaway, Collision-Resistant Hashing: Towards Making UOWHFs Practical, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.470-484, August 17-21, 1997
• 14: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 15: D. Boneh and J. Katz. Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity Based Encryption. CT-RSA '05, LNCS 3376, Springer-Verlag.
• 16: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 17: Stefan Brands, Untraceable off-line cash in wallet with observers, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.302-318, January 1994, Santa Barbara, California, United States
• 18: M. Burmester and Y. Desmedt. Remarks on soundness of proofs. Electronics Letters, 25(22), 1509--1511, 1989.
• 19: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 20: R. Canetti, S. Halevi and J. Katz. Chosen-Ciphertext Security from Identity-Based Encryption. EUROCRYPT '04, LNCS 3027, Springer-Verlag.
• 21: D. Chaum, J. Evertse and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. EUROCRYPT '87, LNCS 304, Springer-Verlag.
• 22: Ronald Cramer , Victor Shoup, Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack, SIAM Journal on Computing, v.33 n.1, p.167-226, 2004 [doi>10.1137/S0097539702403773]
• 23: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 24: Anand Desai, New Paradigms for Constructing Symmetric Encryption Schemes Secure against Chosen-Ciphertext Attack, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.394-412, August 20-24, 2000
• 25: T. ElGamal. A public key cryptosystem and signature scheme based on discrete logarithms. IEEE Trans. Info. Theory, 31(4), 469--472, 1985.
• 26: R. Gennaro and V. Shoup. A note on an encryption scheme of Kurosawa and Desmedt. Cryptology ePrint Archive: Report 2004/194.
• 27: S. Goldwasser and S. Micali. Probabilistic Encryption. J. Comput. & Sys. Sci.,28, 270--299, 1984.
• 28: Jonathan Katz , Moti Yung, Unforgeable Encryption and Chosen Ciphertext Secure Modes of Operation, Proceedings of the 7th International Workshop on Fast Software Encryption, p.284-299, April 10-12, 2000
• 29: E. Kiltz. Chosen-Ciphertext Security from Tag-Based Encryption. Theory of Cryptography -- TCC '06, LNCS 3876, Springer-Verlag.
• 30: Kaoru Kurosawa, Multi-recipient Public-Key Encryption with Shortened Ciphertext, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.48-63, February 12-14, 2002
• 31: K. Kurosawa and Y. Desmedt. A New Paradigm of Hybrid Encryption Scheme. CRYPTO '04, LNCS 3152, Springer-Verlag.
• 32: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 33: NIST. Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication. Document SP 800-38B, May 2005.
• 34: Tatsuaki Okamoto , David Pointcheval, The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.104-118, February 13-15, 2001
• 35: 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
• 36: Phillip Rogaway , Mihir Bellare , John Black, OCB: A block-cipher mode of operation for efficient authenticated encryption, ACM Transactions on Information and System Security (TISSEC), v.6 n.3, p.365-403, August 2003 [doi>10.1145/937527.937529]
• 37: V. Shoup. Sequences of Games: A Tool for Taming Complexity in Security Proofs. Cryptology ePrint Archive: Report 2004/332.
• 38: V. Shoup. Why chosen ciphertext security matters. IBM Research Report RZ 3076, November 1998.
• 39: Yuliang Zheng, Digital Signcryption or How to Achieve Cost(Signature & Encryption) << Cost(Signature) + Cost(Encryption), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.165-179, August 17-21, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Security

Keywords:
cryptography, public-key encryption