Is there a known non-trivial system with plausibly secure public key encryption where:
- the time function is efficiently computable;
- the [pubkey,privkey] pairs are generated with time(privkey) = 0;
- when encrypting under pubkey, the encryptor chooses a value of t in the appropriate range;
- 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;
- 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;
- 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.