Provably Secure Timed-Release Public Key Encryption

ABSTRACT

A timed-release cryptosystem allows a sender to encrypt a message so that only the intended recipient can read it only after a specified time. We formalize the concept of a secure timed-release public-key cryptosystem and show that, if a third party is relied upon to guarantee decryption after the specified date, this concept is equivalent to identity-based encryption; this explains the observation that all known constructions use identity-based encryption to achieve timed-release security. We then give several provably-secure constructions of timed-release encryption: a generic scheme based on any identity-based encryption scheme, and two more efficient schemes based on the existence of cryptographically admissible bilinear mappings. The first of these is essentially as efficient as the Boneh-Franklin Identity-Based encryption scheme, and is provably secure and authenticated in the random oracle model; the final scheme is not authenticated but is provably secure in the standard model (i.e., without random oracles).

REFERENCES

• 1: 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
• 2: An, J. H. 2001. Authenticated encryption in the public-key setting: security notions and analyses. http://eprint.iacr.org/2001/079/.
• 3: 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
• 4: M. Bellare , S. Goldwasser, Encapsulated Key Escrow, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 5: Bellare, M. and Palacio, A. 2002. Protecting against key exposure: Strongly key-insulated encryption with optimal threshold. http://eprint.iacr.org/2002/064/.
• 6: 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]
• 7: Blake, I. F. and Chan, A. C.-F. 2005. Scalable, server-passive, user-anonymous timed release public key encryption from bilinear pairing. In <it>International Conference on Distributed Computing System (ICDCS'05)</it>.
• 8: Boneh, D. and Boyen, X. 2004. Efficient selective-ID secure identity based encryption without random oracles. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'04)</it>.
• 9: Boneh, D., Boyen, X., and Goh, E.-J. 2005. Hierarchical identity based encryption with constant size ciphertext. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'05)</it>.
• 10: Dan Boneh , Ran Canetti , Shai Halevi , Jonathan Katz, Chosen-Ciphertext Security from Identity-Based Encryption, SIAM Journal on Computing, v.36 n.5, p.1301-1328, December 2006 [doi>10.1137/S009753970544713X]
• 11: 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
• 12: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 13: Boyen, X. 2003. Multipurpose identity based signcryption: A swiss army knife for identity based cryptography. In <it>Annual International Cryptology Conference (CRYPTO'03)</it>.
• 14: Boyen, X., Mei, Q., and Waters, B. 2005. Simple and eficient CCA2 security from IBE techniques. In <it>ACM Conference on Computer and Communications Security (ACM CCS'05)</it>.
• 15: Boyen, X. and Waters, B. 2006. Anonymous hierarchical identity-based encryption (without random oracles). In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06)</it>.
• 16: Cathalo, J., Libert, B., and Quisquater, J.-J. 2005. Efficient and non-interactive timed-release encryption. In <it>International Conference on Information, Communications and Signal Processing (ICICS'05)</it>.
• 17: Chatterjee, S. and Sarkar, P. 2005. Trading time for space: Towards an efficient IBE scheme with short(er) public parameters in the standard model. In <it>International Conference on Information Security and Cryptology (ICISC'05)</it>.
• 18: L. Chen , Keith Harrison , David Soldera , Nigel P. Smart, Applications of Multiple Trust Authorities in Pairing Based Cryptosystems, Proceedings of the International Conference on Infrastructure Security, p.260-275, October 01-03, 2002
• 19: Cheon, J. H., Hopper, N., Kim, Y., and Osipkov, I. 2004. Authenticated key-insulated public key encryption and timed-release cryptography. http://eprint.iacr.org/2004/231.
• 20: Cheon, J. H., Hopper, N., Kim, Y., and Osipkov, I. 2006. Timed-release and key-insulated public key encryption. In <it>Financial Cryptography</it>.
• 21: 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
• 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: Crescenzo, G. D., Ostrovsky, R., and Rajagopalan, S. 1999. Conditional oblivious transfer and timed-release encryption. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'99)</it>.
• 24: Dodis, Y. and Katz, J. 2005. Chosen-ciphertext security of multiple encryption. In <it>Theory of Cryptography Conference</it>.
• 25: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Key-Insulated Public Key Cryptosystems, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.65-82, May 02, 2002
• 26: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Strong Key-Insulated Signature Schemes, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.130-144, January 06-08, 2003
• 27: 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
• 28: Garay, J. and Pomerance, C. 2003. Timed fair exchange of arbitrary signatures. In <it>Financial Cryptography</it>.
• 29: Garay, J. A. and Pomerance, C. 2002. Timed fair exchange of standard signatures. In <it>Financial Cryptography</it>.
• 30: 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
• 31: 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
• 32: Kiltz, E. 2006. Chosen-ciphertext secure identity-based encryption in the standard model with short ciphertexts. http://eprint.iacr.org/2006/122/.
• 33: Kiltz, E. and Galindo, D. 2006. Direct chosen-ciphertext secure identity-based key encapsulation without random oracles. http://eprint.iacr.org/2006/034/.
• 34: Laguillaumie, F., Pallier, P., and Vergnaud, D. 2005. Universally convertible directed signatures. In <it>International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'05)</it>.
• 35: Marco Casassa Mont , Keith Harrison , Martin Sadler, The HP time vault service: exploiting IBE for timed release of confidential information, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775175]
• 36: May, T. 1993. Timed-release crypto. http://www.cyphernet.org/cyphernomicon/chapter14/14.5.html.
• 37: Alfred Menezes , Scott Vanstone , Tatsuaki Okamoto, Reducing elliptic curve logarithms to logarithms in a finite field, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.80-89, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103434]
• 38: Naccache, D. 2005. Secure and practical identity-based encryption. http://eprint.iacr.org/2005/369/.
• 39: Pederson, T. P. 1991. A threshold cryptosystem without a trusted party. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'91)</it>.
• 40: Pointcheval, D. and Stern, J. 1996. Security proofs for signature schemes. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'96)</it>.
• 41: 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
• 42: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 43: Shamus Software Ltd. MIRACL: Multiprecision integer and rational arithmetic C/C++ library. http://indigo.ie/mscott/.
• 44: Shoup, V. 2000. Using hash functions as hedge against chosen ciphertext attack. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'00)</it>.
• 45: Shoup, V. 2004. ISO 18033-2: An emerging standard for public-key encryption. http://shoup.net/iso/.
• 46: P. Syverson, Weakly Secret Bit Commitment: Applications to Lotteries and Fair Exchange, Proceedings of the 11th IEEE workshop on Computer Security Foundations, p.2, June 09-11, 1998
• 47: Waters, B. 2005. Efficient identity-based encryption without random oracles. In <it>International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'05)</it>.

INDEX TERMS

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

General Terms:
Security, Theory

Keywords:
authenticated encryption, key-insulated encryption, timed-release