## Cryptology ePrint Archive: Report 2003/083

**A Forward-Secure Public-Key Encryption Scheme**

*Ran Canetti and Shai Halevi and Jonathan Katz*

**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.)

**Category / Keywords: **public-key cryptography / forward security, BDH assumption

**Publication Info: **Eurocrypt 2003

**Date: **received 1 May 2003, last revised 23 Dec 2003

**Contact author: **jkatz at cs umd edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **This paper supersedes a previous version which appears as
ePrint archive report 2002/060.

**Version: **20031223:175209 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]