Forward-secure public-key encryption

A forward-secure public-key encryption scheme is a public-key encryption scheme whose public key is fixed for time periods, whose ciphertexts are formed for a period, and whose secret key is updated at the end of each period, such that the secret key of period reveals nothing about plaintexts encrypted for any period — CHK03.

Syntax

A key-evolving public-key encryption scheme with periods is a tuple of efficient algorithms with message space and ciphertext space — CHK03:

  • , a randomized algorithm outputting a public key and the secret key of period ,
  • , a (possibly randomized) algorithm which, for , takes the secret key of period and outputs the secret key of period , after which the receiver erases ,
  • , a randomized algorithm which takes the public key, a period and a message , outputting a ciphertext ,
  • , a deterministic algorithm which takes the secret key of period and a ciphertext, outputting or .

Throughout, is polynomially bounded, and denotes the key obtained from by applications of .

Properties

Correctness

A key-evolving public-key encryption scheme is -correct if for all , and ,

over and the randomness of and . When , is perfectly correct.

Forward security

The adversary receives and makes one break-in query, receiving the secret key of a period of its choice, and one challenge query, receiving an encryption of or for a period of its choice, in either order — CHK03. An admissible makes exactly one query to each oracle, with , and submits with . The challenge period must precede the break-in period because yields, through , the secret key of every period .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{fs\text{-}cpa}}_{\mathsf{FSPKE},T,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk_1) \gets \KeyGen(1^\secpar, T)$; $b \getsr \bits$
\State $b' \gets \calA^{\calO_{\mathrm{brk}}, \calO_{\mathrm{ch}}}(1^\secpar, \pk)$
\Comment{one query to each oracle, in either order, with $j < i$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{brk}}(i)$}
\begin{algorithmic}
\State $\sk_{t+1} \gets \mathsf{Update}(\sk_t)$ for $t = 1, \ldots, i - 1$
\Return $\sk_i$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{ch}}(j, m_0, m_1)$}
\begin{algorithmic}
\Return $\Enc(\pk, j, m_b)$
\end{algorithmic}
\end{algorithm}

A key-evolving public-key encryption scheme is forward-secure if for all polynomially bounded and all admissible efficient ,

is negligible.

Variations

Chosen-ciphertext forward security

In the chosen-ciphertext game the adversary also has a decryption oracle for every period , and may not query it on for the challenge period and challenge ciphertext , since by correctness — CHK03. The CHK03 scheme extends to chosen-ciphertext security — CHK03. Securing binary tree encryption against chosen-ciphertext attacks gives more efficient such schemes in the standard model — CHK04.

Key-insulated encryption

In a -key-insulated scheme with periods, the receiver’s key update also takes a message from a helper device that stores a master key, and exposure of the receiver’s secret keys for any periods leaves every other period secure, earlier or later — DKXY02. A forward-secure scheme needs no helper, and exposure of breaks every period from on.

Forward-secure signatures

The analogous notion for signatures is forward-secure signature, in which the signing key of period does not allow forging signatures for earlier periods — BM99.

Other results

Participates in

Produces Forward-secure public-key encryption