ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption

ABSTRACT

A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in hierarchical identity-based encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously.

We present a scalable forward-secure HIBE (fs-HIBE) scheme satisfying the above properties. We also show how our fs-HIBE scheme can be used to construct a forward-secure public-key broadcast encryption scheme, which protects the secrecy of prior transmissions in the broadcast encryption setting. We further generalize fs-HIBE into a collusion-resistant multiple hierarchical ID-based encryption scheme, which can be used for secure communications with entities having multiple roles in role-based access control. The security of our schemes is based on the bilinear Diffie-Hellman assumption in the random oracle model.

REFERENCES

• 1: Michel Abdalla , Sara K. Miner , Chanathip Namprempre, Forward-Secure Threshold Signature Schemes, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.441-456, April 08-12, 2001
• 2: R. Anderson. Two remarks on public-key cryptology. Invited lecture, 4th ACM Conference on Computer and Communications Security, 1997.
• 3: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 4: 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]
• 5: M. Bellare and B. Yee. Forward security in private-key cryptography. In CT-RSA, volume 2612 of LNCS, pages 1--18.
• 6: D. Boneh and X. Boyen. Efficient selective-ID secure identity-based encryption without random oracles. In Advances in Cryptology -- Eurocrypt '04, volume 3027 of LNCS, pages 223--238.
• 7: D. Boneh and X. Boyen. Secure identity based encryption without random oracles. Crypto '04.
• 8: 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
• 9: D. Boneh and A. Silverberg. Applications of multilinear forms to cryptography. Contemporary Mathematics, 324:71--90, 2003.
• 10: R. Canetti, S. Halevi, and J. Katz. A forward-secure public-key encryption scheme. In Advances in Cryptology -- Eurocrypt '03, volume 2656 of LNCS, pages 255--271.
• 11: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 12: Y. Dodis and N. Fazio. Public-key broadcast encryption for stateless receivers. In Digital Rights Management -- DRM '02, volume 2696 of LNCS, pages 61--80.
• 13: Yevgeniy Dodis , Nelly Fazio, Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.100-115, January 06-08, 2003
• 14: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 15: Eiichiro Fujisaki , Tatsuaki Okamoto, Secure Integration of Asymmetric and Symmetric Encryption Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.537-554, August 15-19, 1999
• 16: Juan A. Garay , Jessica Staddon , Avishai Wool, Long-Lived Broadcast Encryption, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.333-352, August 20-24, 2000
• 17: Christoph G. Günther, An identity-based key-exchange protocol, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.29-37, November 1990, Houthalen, Belgium
• 18: 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
• 19: M. T. Goodrich, J. Z. Sun, and R. Tamassia. Efficient tree-based revocation in groups of low-state devices. In Advances in Cryptology - Crypto '04, LNCS.
• 20: Dani Halevy , Adi Shamir, The LSD Broadcast Encryption Scheme, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.47-60, August 18-22, 2002
• 21: Jason E. Holt , Robert W. Bradshaw , Kent E. Seamons , Hilarie Orman, Hidden Credentials, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC [doi>10.1145/1005140.1005142]
• 22: 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
• 23: J. Katz. A forward-secure public-key encryption scheme. Cryptology ePrint Archive, Report 2002/060.
• 24: C. Kim, Y. Hwang, and P. Lee. An efficient public key trace and revoke scheme secure against adaptive chosen ciphertext attack. In Advances in Cryptology -- Asiacrypt 2003, volume 2894 of LNCS, pages 359--373.
• 25: M. Luby and J. Staddon. Combinatorial bounds for broadcast encryption. In Advances in Cryptology -- Eurocrypt '98, volume 1403 of LNCS, pages 512--526.
• 26: Tal Malkin , Daniele Micciancio , Sara K. Miner, Efficient Generic Forward-Secure Signatures with an Unbounded Number Of Time Periods, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.400-417, May 02, 2002
• 27: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 28: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 29: Roberto Tamassia , Danfeng Yao , William H. Winsborough, Role-based cascaded delegation, Proceedings of the ninth ACM symposium on Access control models and technologies, June 02-04, 2004, Yorktown Heights, New York, USA [doi>10.1145/990036.990061]
• 30: B. R. Waters. Efficient identity-based encryption without random oracles. Cryptology ePrint Archive, Report 2004/180, 2004.
• 31: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.68-79, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 32: D. Yao, N. Fazio, Y. Dodis, and A. Lysyanskaya. ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption. Cryptology ePrint Archive, Report 2004/212, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Security, Theory

Keywords:
ID-Based encryption, broadcast encryption, forward security