DH key agreement protocols require the participation of both parties, so are only suitable for synchronous connections. Is it possible to implement PFS in a fashion usable for asynchronous protocols, like e-mail, or storage? I'm intuitively thinking not, but I haven't be able to find conclusive proof one way or the other.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Asynchronous forward secure encryption is possible if you allow users to have synchronous clocks. It seems impossible without that or a third party, though I am aware of no formal result.
A trivial(and hence awful) solution is to generate N key pairs and use one for each interval, discarding them as we go. A somewhat more efficient solution is to use Identity Based Encryption(IBE) to have one public key and N private keys.
The most efficient scheme I know of is due to Canetti, Halevi, and Katz in this paper. It provides for constant size public keys and $O(log(N))$ private keys where N is the number of time intervals. As far as I know, no paper has improved on that bound, though several have achieved that bound with more efficient techniques.
The gist of the design is you have a tree of keys where there is one root public key and messages can be encrypted to any node in the tree with the root pubic key and the index identifying the node. (So far, this is just an IBE scheme). Unlike IBE, the decryption key for a given node can be computed from it's parent key.
We now map time intervals to nodes using a pre order traversal (i.e. the root is interval one, the left child interval 2, the left left grandchild of root is interval 3 ...). So once time interval 1 is up, we derive the keys for both the left and right nodes and then delete the root key. Now messages encrypted to interval one are safe, but we can still decrypt everything targeted at the remaining N-1 intervals.