International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: A Forward-Secure Public-Key Encryption Scheme

Ran Canetti
Shai Halevi
Jonathan Katz
Search ePrint
Search Google
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 keys stored on such devices, the paradigm of \emph{forward security} was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the secret key corresponding to a given time period does not enable an adversary to ``break'' the scheme (in the appropriate sense) for any \emph{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 non-trivial constructions of (non-interactive) forward-secure public-key encryption schemes. Our main construction achieves security against chosen-plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. This scheme is practical, and all parameters grow at most logarithmically with the total number of time periods. We also give a slightly more efficient scheme in the random oracle model. Both our schemes can be extended to achieve security against chosen-ciphertext attacks and to support an unbounded number of time periods. Toward our goal, we introduce the notion of \emph{binary tree encryption} and show how to construct a binary tree encryption scheme in the standard model. This new primitive may be of independent interest. In particular, we use it to construct the first known example of a (hierarchical) identity-based encryption scheme that is secure in the standard model. (Here, however, the notion of security we achieve is slightly weaker than what is achieved in some previous constructions in the random oracle model.)
  title={A Forward-Secure Public-Key Encryption Scheme},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / forward security, BDH assumption},
  note={Eurocrypt 2003 12409 received 1 May 2003, last revised 23 Dec 2003},
  author={Ran Canetti and Shai Halevi and Jonathan Katz},