Public Key Encryption with forward secrecy

Question

Is there a known non-trivial system with plausibly secure public key encryption where:


1. $\;\;$ the $\:$ time $\:$ function is efficiently computable
2. $\;\;$ [pubkey,privkey] $\:$ pairs are generated with $\:$ time(privkey) = 0
3. $\;\;$ when encrypting under $\:$ pubkey $\:$, $\:$ the encryptor chooses a value of t in the appropriate range

${}$4. $\;\;$ given privkey0 and t such that $\:$ time(privkey0) < t $\:$ and t is in the appropriate range,
$\qquad$one can efficiently compute privkey1 such that $\:$ time(privkey1) = t

${}$5. $\;\;$ given $\:$ privkey' $\:$ generated from the original $\:$ privkey $\:$ by zero or more
$\qquad$ more applications of 4, and a message encrypted under pubkey
$\qquad$ with $\:$ t = time(privkey') $\:$, $\:$ one can efficiently decrypt the message

${}$6. $\;\;$ given $\:$ privkey' $\:$ generated from the original $\:$ privkey $\:$ by one or more
$\qquad$ applications of 4, and a messgae encrypted under pubkey with
$\qquad$ t < time(privkey') $\:$, $\:$ it is infeasible to learn anything about the message


?



The trivial system is generating keys with $\:$ privkey $\:$ as 0 paired with a (randomly chosen) state for a forward-secure pseudo-random number generator, and $\:$ pubkey $\:$ as a list of public keys for an ordinary PKE system generated using the pseudo-random output from the state. $\;\;$ The $\:$ time $\:$ function is taking the first entry in the pair. $\;\;$ The range for t values is non-negative integers less than the number of (ordinary) public keys in the list. $\;\;$ Encryption under $\:$ pubkey $\:$ is the pair of t together with (ordinary) encryption under the t'th (ordinary) public key in the list. $\;\;$ The step 4 updating is changing the first part of $\:$ privkey $\:$ to t and changing the state to what it was after generating the first t (ordinary) public keys. $\;\;$ The step 5 decryption is by using the known state to regenerate the
(ordinary) private key for the t'th (ordinary) public key in the list, and using
that private key to decrypt the second part of the encrypted message.

The problem with the trivial system is that the size of $\:$ pubkey
grows linearly with the desired size of the range for t values.

Answer 1

One approach can be found in this paper by Canetti, Halevi and Katz. To summarize the approach:

• This generate a tree of private keys; from a node, you can generate private keys downwards (to child nodes), but you cannot compute upwards (to the parent nodes). This achieves forward secrecy by generating child nodes and erasing parent nodes.

• The public key can be used to encrypt to any private key node; if we have the private key for that node (or we can generate it because we have one of its parents), we can decrypt the message; if the private key for that node has already been erased, we cannot.

• The size of the public key is constant (that is, independent of the number of time steps supported).

• The size of an encrypted message is $O(\log t)$ (where $t$ is the number of time steps supported).

• The size of the private key for the entire system is $O(\log t)$; this includes the number of private keys nodes stored in memory at any one time.

• Encryption and decryption both take $O(\log t)$ time.

• The algorithm uses a bilinear mapping that meets the BDH (Bilinear Diffie-Hellman) assumption.