Direct chosen ciphertext security from identity-based techniques

ABSTRACT

We describe a new encryption technique that is secure in the standard model against chosen ciphertext attacks. We base our method on two very efficient Identity-Based Encryption (IBE) schemes without random oracles due to Boneh and Boyen, and Waters.Unlike previous CCA2-secure cryptosystems that use IBE as a black box, our approach is very simple and compact. It makes direct use of the underlying IBE structure, and requires no cryptographic primitive other than the IBE scheme itself. This conveys several advantages. We achieve shorter ciphertext size than the best known instantiations of the other methods, and our technique is as efficient as the Boneh and Katz method (and more so than that of Canetti, Halevi, and Katz). Further, our method operates nicely on hierarchical IBE, and since it allows the validity of ciphertexts to be checked publicly, it can be used to construct systems with non-interactive threshold decryption.In this paper we describe two main constructions: a full encryption system based on the Waters adaptive-ID secure IBE, and a KEM based on the Boneh-Boyen selective-ID secure IBE. Both systems are shown CCA2-secure in the standard model, the latter with a tight reduction. We discuss several uses and extensions of our approach, and draw comparisons with other schemes that are provably secure in the standard model.

REFERENCES

• 1: Masayuki Abe, Rosario Gennaro, Kaoru Kurosawa, and Victor Shoup. Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM. In EUROCRYPT 2005, volume 3494 of LNCS, pages 128--146. Springer-Verlag, 2005.
• 2: 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]
• 3: Dan Boneh and Xavier Boyen. Efficient selective-ID secure identity based encryption without random oracles. In EUROCRYPT 2004, LNCS. Springer Verlag, 2004.
• 4: Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. In EUROCRYPT 2005, volume 3494 of LNCS, pages 440--456. Springer-Verlag, 2005.
• 5: Dan Boneh, Xavier Boyen, and Shai Halevi. Chosen ciphertext secure public key threshold encryption without random oracles. Manuscript, 2005. http://crypto.stanford.edu/~dabo/abstracts/threshold.html.
• 6: Dan Boneh, Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based encryption, 2005. Journal Submission, available at http://crypto.stanford.edu/~dabo/papers/ccaibejour.pdf.
• 7: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 8: Dan Boneh and Jonathan Katz. Improved efficiency for CCA-secure cryptosystems built using identity based encryption. In RSA-CT 2005. Springer-Verlag, 2005.
• 9: Xavier Boyen, Qixiang Mei, and Brent Waters. Direct chosen ciphertext security from identity-based techniques. Cryptology ePrint Archive, Report 2005/288, 2005. http://eprint.iacr.org/.
• 10: Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. In EUROCRYPT 2003. Springer-Verlag, 2003.
• 11: Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based encryption. In EUROCRYPT 2004. Springer-Verlag, 2004.
• 12: Ron Canetti and Shafi Goldwasser. An efficient threshold public key cryptosystem secure against adaptive chosen message attack. In EUROCRYPT 1999, volume 1592 of LNCS, pages 90--106. Springer-Verlag, 1999.
• 13: 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
• 14: Ronald Cramer , Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.45-64, May 02, 2002
• 15: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 16: Edith Elkind and Amit Sahai. A unified methodology for constructing public-key encryption schemes secure against adaptive chosen-ciphertext attack. Cryptology ePrint Archive, Report 2002/042, 2002. http://eprint.iacr.org/.
• 17: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 18: Jeremy Horwitz , Ben Lynn, Toward Hierarchical Identity-Based Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.466-481, May 02, 2002
• 19: Antoine Joux, A One Round Protocol for Tripartite Diffie–Hellman, Journal of Cryptology, v.17 n.4, p.263-276, September 2004 [doi>10.1007/s00145-004-0312-y]
• 20: Kaoru Kurosawa and Yvo Desmedt. A new paradigm of hybrid encryption scheme. In CRYPTO 2004, LNCS, pages 426--442. Springer-Verlag, 2004.
• 21: Leslie Lamport. Constructing digital signatures from a one-way function. Technical Report CSL-98, SRI International, Palo Alto, 1979.
• 22: Victor S. Miller, The Weil Pairing, and Its Efficient Calculation, Journal of Cryptology, v.17 n.4, p.235-261, September 2004 [doi>10.1007/s00145-004-0315-8]
• 23: 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]
• 24: 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
• 25: Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999
• 26: Victor Shoup. Using hash functions as a hedge against chosen ciphertext attack. In EUROCRYPT 2000, LNCS, pages 275--288. Springer-Verlag, 2000.
• 27: Brent Waters. Efficient identity based encryption without random oracles. In EUROCRYPT 2005, LNCS. Springer Verlag, 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
chosen ciphertext security, identity-based encryption