Change encryption key without displaying plaintext

Question

We are developing a database system for storing encrypted information strings, and encryption and decryption are performed on the client side using public key cryptography. If the key were ever changed, this would require re-encryption of the entire client side of the records, which is very impractical. Is there a way that this can be done on the server side without exposing the original (old) decryption key or message text?

I assume that I am behind it - an associative cipher, something like this:

T( E o (m) ) = E n ( D o (E o (m) ))

where Eo (m) is the ciphertext, Eo / Do is the old pub / private key pair, En is the new pub key, m is the message text and T is the magic re-encryption function. Edit: T is computed by clients, and then sent to the server to be used.

Answer 1

In any case, you cannot retroactively disable the old key. Anyone who has access to the old data and the old key can decrypt the data no matter what you do.

I would suggest just holding a key ring. Add a new key to the ring and mark it active. Note that the old key has expired. Encrypt the client so that if it finds any data encrypted with an expired key, it re-encrypts it with the active key. (Or not. The information you need depends on the details of your implementation requirements.)

If you wish, after a certain period of time, you can search for any data that is still encrypted with the old key and re-encrypted.

You can in no way remove the exposition of the old key - anyone who can find a backup or copy of the data encrypted with the old key can decrypt it if they have the old key. The encryption keys must be protected forever or you will receive a fiasco that issued Wikileaks diplomatic cables to the public with the names of informants.

Answer 2

Think about your security perimeters. If you are worried about server compromise, consider creating a more sophisticated subsystem that transcodes. You can do this from a server that is not connected to a network that you contacted only through a very strictly tested communication protocol (for example, via a serial line) or a dedicated hardware-protected module. However, if you are doing something like this, you should consider how your keys are protected; if an attacker can steal transient text from your server, can they also steal keys protecting it?