Abstract
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by exposure of secret data (e.g., keys) stored on such devices, the paradigm of forward security was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; furthermore, exposure of a secret key corresponding to a given time period does not enable an adversary to “break” the scheme (in the appropriate sense) for any prior time period. A number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known.
We present the first constructions of a (non-interactive) forward-secure public-key encryption scheme. Our main construction achieves security against chosen plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. It is practical, and all complexity parameters grow at most logarithmically with the total number of time periods. The scheme can also be extended to achieve security against chosen ciphertext attacks.
Chapter PDF
Similar content being viewed by others
References
M. Abdalla and L. Reyzin. A new forward-secure digital signature scheme. Asiacrypt’00, LNCS vol. 1976, pp. 116–129, Springer-Verlag, 2000.
A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975.
R. Anderson. Two remarks on public key cryptology. Invited Lecture, ACM-CCS’97. http://www.cl.cam.ac.uk/ftp/users/rja14/forwardsecure.pdf.
D. Beaver and S. Haber. Cryptographic protocols provably secure against dynamic adversaries. In Eurocrypt’ 92, LNCS vol. 658, pp. 307–323, Springer-Verlag, 1992.
D. Beaver, Plug and play encryption, Advances in Cryptology — Crypto’ 97, LNCS vol. 1294, pp. 75–89, Springer-Verlag, 1997.
M. Bellare and S. K. Miner. A forward-secure digital signature scheme. Advances in Cryptology — Crypto’ 99, LNCS vol. 1666, pp. 431–448, Springer-Verlag, 1999.
M. Bellare and B. Yee. Forward security in private-key cryptography. Topics in Cryptology — CT-RSA 2003, to appear. Preliminary version at http://eprint.iacr.org/2001/035/.
M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Advances in Cryptology — Crypto’98, Lecture Notes in Computer Science Vol. 1462, pp. 26–45, Springer-Verlag, 1998.
D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. Advances in Cryptology — Crypto 2001, LNCS vol. 2139, pp. 213–229, Springer-Verlag, 2001. Full version to appear in SIAM J. Computing and available at http://eprint.iacr.org/2001/090.
D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. Asiacrypt’ 01, LNCS vol. 2248, pp. 514–532, Springer-Verlag, 2001.
R. Canetti, U. Feige, O. Goldreich and M. Naor, Adaptively Secure Computation, STOC’ 96, pp. 639–648, ACM, 1996. Also MIT-LCS-TR #682, 1996.
I. Damgaard and J. B. Nielsen, Improved non-committing encryption schemes based on general complexity assumption, Advances in Cryptology — Crypto’ 00, LNCS vol. 1880, pp. 432–450, Springer-Verlag, 2000.
Y. Desmedt and Y. Frankel. Threshold cryptosystems. Advances in Cryptology — Crypto’ 89, LNCS vol. 435, pp. 307–315, Springer-Verlag, 1989.
W. Diffie, P. C. Van-Oorschot, and M. J. Weiner. Authentication and authenticated key exchanges. Designs, Codes, and Cryptography 2:107–125, 1992.
D. Dolev, C. Dwork and M. Naor, Non-malleable cryptography, SIAM. J. Computing, Vol. 30, No. 2, 2000, pp. 391–437. Preliminary version in 23rd Symposium on Theory of Computing (STOC), ACM, 1991.
E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric encryption schemes. Crypto’ 99, LNCS 1666, pp. 537–554, Springer-Verlag, 1999.
C. Gentry and A. Silverberg. Hierarchical identity-based cryptography. Asiacrypt 2002, LNCS vol. 2501, pp. 548–566, Springer-Verlag, 2002.
C. G. Günther. An identity-based key-exchange protocol. Advances in Cryptology — Eurocrypt’ 89, LNCS vol. 434, pp. 29–37, Springer-Verlag, 1989.
S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281–308, April 1988.
A. Herzberg, M. Jakobson, S. Jarecki, H. Krawczyk, and M. Yung. Proactive public key and signature systems. Proceedings of 4th Conference on Computer and Communications Security, pp. 100–110, ACM, 1997.
J. Horwitz and B. Lynn. Toward hierarchical identity-based encryption. Eurocrypt’02, LNCS vol. 2332, pp. 466–481, Springer-Verlag, 2002.
G. Itkis and L. Reyzin. Forward-secure signatures with optimal signing and verifying. Crypto’ 01, LNCS vol. 2139, pp. 499–514, Springer-Verlag, 2001.
A. Joux. A one round protocol for tripartite Diffie-Hellman. 4th International Symposium on Algorithmic Number Theory, LNCS vol. 1838, pp. 385–394, Springer-Verlag, 2000.
A. Joux and K. Nguyen. Separating decision diffie-hellman from diffie-hellman in cryptographic groups. Manuscript, January 2001. Available at http://eprint.iacr.org/2001/003/.
A. Kozlov and L. Reyzin. Forward-secure signatures with fast key update. Proc. 3rd Conference on Security in Communication Networks, LNCS vol. 2576, pp. 247–262, Springer-Verlag, 2002.
H. Krawczyk. Simple forward-secure signatures from any signature scheme. Proc. 7th ACM-CCS, pp. 108–115, ACM, 2000.
T. Malkin, D. Micciancio, and S. K. Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. Advances in Cryptology — Eurocrypt 2002, LNCS vol. 2332, pp. 400–417, Springer-Verlag, 2002.
M. Naor and M. Yung, Public key cryptosystems provably secure against chosen ciphertext attacks, 22nd STOC, 427–437, 1990.
J. B. Nielsen. Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. Crypto’ 02, LNCS vol. 2442, pp. 111–126, Springer-Verlag, 2002.
R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. 10th Annual Symposium on Principles of Distributed Computing, pages 51–59, ACM, 1991.
C. Rackoff and D. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, Crypto’ 91, LNCS vol. 576, pp. 433–444, Springer-Verlag, 1991.
A. Sahai. Non-malleable non-interactive zero-knowledge and adaptive chosenciphertext security. Proc. of the 40th Annual Symposium on Foundations of Computer Science, pages 543–553, IEEE, 1999.
A. Shamir. How to share a secret. Comm. of the ACM 22(11):612–613, 1979.
E. R. Verheul. Self-blindable credential certificates from the Weil pairing. Asiacrypt 2001, LNCS vol. 2248, pp. 533–551, Springer-Verlag, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Canetti, R., Halevi, S., Katz, J. (2003). A Forward-Secure Public-Key Encryption Scheme. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_16
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive