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. the [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, one can efficiently compute privkey1 such that time(privkey1) = t;
5. given privkey' generated from the original privkey by zero or more more applications of (4), and a message encrypted under pubkey with t = time(privkey'), one can efficiently decrypt the message;
6. given privkey' generated from the original privkey by one or more applications of 4, and a message encrypted under pubkey with 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.