Change encryption key without exposing plaintext

Question

We're designing a database system to store encrypted strings of information, with encryption and decryption performed client side using public-key cryptography. If the key was ever changed though, this would necessitate reencrypting all the records client side, which is very impractical. Is there any way this could be performed server side without exposing either the original (old) decryption key, or the message text?

I guess what I'm after is an associative cipher, something like this:

T( Eo(m) ) = En( Do(Eo(m) ))

where Eo(m) is the cipher text, Eo/Do the old pub/priv key pair, En the new pub key, m the message text and T the magical reencryption function. Edit: T is calculated clientside and then sent to the server to be used.

Answer 1

You can't retroactively disable the old key anyway. Anyone who has access to the old data and the old key can decrypt the data no matter what you do.

I would suggest simply keeping a ring of keys. Add the new key to the ring and mark it active. Mark the old key expired. Code the client so that if it finds any data that's encrypted with an expired key, it re-encrypts it with the active key. (Or don't. What's needed depends on details of your implementation requirements.)

If desired, after a period of time, you can sweep for any data still encrypted with the old key and re-encrypt it.

You can't eliminate the exposure of the old key anyway, ever -- anyone who can find a backup or copy of data encrypted with the old key can decrypt it if they have the old key. Encryption keys must be protected forever or you get the fiasco that released the Wikileaks diplomatic cables to the public with the names of informants intact.