Self-expiring symmetric keys, or: cryptography in absence of secure deletion

I can encrypt some data D using a random symmetric key K, obtaining a ciphertext C, and then encrypt K with my public key Pub and obtain H. So far so good: I can only decrypt C if I have H and my private key Priv. My goal is to only bring around Priv, and keep both C and H on a public server. Assume C is too large to be re-uploaded, and we do not trust the server so secure deletion is not possible.

The question is: what if Priv gets compromised? In the above scenario, nothing good. C will be on the server forever, together with H, leaving to the attacker the time to read C and decrypt it.

This is bad in comparison with e.g. a mail server, where I have to log in to view my data: as soon as I notice that my password has been compromised, I can change it, and if the attacker did not download C yet, I'm safe.

So the real question is: are there any known, or standard, methods to create "self-expiring symmetric keys"? What I imagine is that I could avoid to store H on the server, but still be able to derive H from some smaller secret (kept on the server) and some external "aid" which should be as simple and less trusted as possible, e.g. a random stream of data, in such a way that it is possible to reconstruct H only for a limited amount of time.

After the key is expired, the data would be lost. Before, one should be able to refresh the key.

-
Is the random stream only available for a certain time period? Also, you would need a trusted time source, no? –  mikeazo Aug 27 '12 at 1:27
Yes I imagine the random stream is available only for some time. Thinking about it, I can think of methods to "slow down" the stream in various ways, so for the moment let's assume the random stream generates a "large enough" number just "when I need it". Then I can encrypt the current key with the current number, and store the result on the server. Then I just need to refresh the key "when I need it". –  vincenzoml Aug 27 '12 at 11:38
"My goal is to only bring around Priv, and keep both C and H on a public server." May I ask why you want to keep H on the public server? –  David Wachtfogel Sep 27 '12 at 19:53
@David Wachtfogel: I need that, since users should be able to get all of their data from the server, without storing anything else (think dropbox, or wuala, for the matter). –  vincenzoml Sep 28 '12 at 7:16
But don't they need to store Priv? If not - how can they access their data? –  David Wachtfogel Sep 29 '12 at 20:28

1 Answer

I don't believe there is any way to achieve what you want, within your constraints.

You stated as a requirement that a user must be able to get all of their data from the server, without storing anything other than their private key. If an attacker learns the private key, the attacker then knows everything that the user does, so of course the attacker can decrypt too.

A random beacon (a continuous, public stream of random numbers) doesn't seem to help, since an attacker can record a copy of that entire stream. Also, it would rely upon on some external trusted party to generate the stream; if you are willing to trust a third party, there are simpler solutions. An example of such a solution: store $H$ on the trusted third party and return it only upon request to users who prove knowledge of the private key, and only if the expiration date has not yet passed.

A different solution is to have the user change their private key every so often. To ease this, they can generate a long-lived keypair which is used only for signing, and then generate short-lived keypairs every so often. The long-lived key is used to sign each short-lived public key and publish this certificate. To send a message to this user, you look up the current short-lived public key, check its corresponding cert, then encrypt to the short-lived public key. The user can then securely delete their short-lived keypair when it expires. (I think you might also be able to build sophisticated schemes that eliminate the need for a lookup, but I'm not 100% certain about that.)

-
My stronger constraint is that we do not trust the server, so we can not count on secure deletion. However, I am interested in solutions that involve some trust in a third party (that could become a peer to peer algorithm maybe) –  vincenzoml Oct 19 '12 at 21:19
@vincenzoml, I already gave an example of such a solution in 3rd paragraph of my answer ("an example of such a solution: ..."). If this example does not meet your needs, then I encourage you to edit the question to clarify the threat model and application domain and in what ways this falls short of your needs. It would help to understand better what you're looking for and how you will evaluate candidate answers. –  D.W. Oct 20 '12 at 1:38