title: Change encryption key without exposing plaintext
body: <p>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?</p>
  
  <p>I guess what I'm after is an associative cipher, something like this:</p>
  
  <p><code> T( E<sub>o</sub>(m) ) = E<sub>n</sub>( D<sub>o</sub>(E<sub>o</sub>(m) )) </code></p>
  
  <p>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.</p>