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
- CPA-secure public-key encryption exists if and only if forward-secure public-key encryption does, for every polynomially bounded ; the construction from PKE uses independent key pairs, so its public key grows linearly in , and conversely the period- algorithms of a forward-secure scheme form a CPA-secure PKE scheme (CPA-secure PKE ⇔ Forward-secure PKE) — folklore.
- A selective-node-secure binary tree encryption scheme of depth gives a forward-secure scheme with periods whose period keys hold at most tree keys (Selective-node-secure BTE ⇒ Forward-secure PKE (Canetti–Halevi–Katz)) — CHK03.
- If DBDH is hard, a forward-secure scheme exists in the standard model (DBDH ⇒ Forward-secure PKE (Canetti–Halevi–Katz)) — CHK03.
Participates in
Produces Forward-secure public-key encryption