Which encryption algorithms could be used for the following scenario?

  1. A user stores a file encrypted by someone else
  2. Then the user is asked to re-encrypt the file with a new secret
  3. The user stays unaware about the clear text every moment

To achieve that the user can be provided with a kind of "diff" secret, I suppose. It may be a password based algorithm.

  • $\begingroup$ To clarify: Is authentication and/or verification part of the scenario? $\endgroup$ – e-sushi Jul 4 '17 at 14:25
  • $\begingroup$ Could you explain what you're trying to accomplish? If a user can re-encrypt the file with any new secret, he can simply generate a secret himself and get the clear text. $\endgroup$ – Daan Bakker Jul 4 '17 at 15:16
  • $\begingroup$ @DaanBakker If such a system exists, I'm guessing the "re-encrypt key" (given to the person storing the file) would need to be some cryptographic combination of the original (de)cryption key and the new (en)cryption key (both known only to the creator of the file). $\endgroup$ – TripeHound Jul 4 '17 at 15:31
  • 1
    $\begingroup$ What I'm missing from the description are the requirements of the receiver. You ask to "encrypt with a new secret" but if you include asymmetric crypto then a public key could be used for encryption, while you would need the private key for decryption. $\endgroup$ – Maarten Bodewes Jul 4 '17 at 15:36

This is possible with the Integrated Encryption System

In this system, there are global values $p$ (a large prime) and $g$ (a generator of a prime subgroup in $\mathbb{Z}_p^*$). A private key is a value $x$ and the corresponding public key is the value $y = g^x \bmod p$.

To encrypt a message $M$ using the public key $y$, you select a random value $r$, and publish the pair $(C, D)$ with $C = g^r \bmod p$ and $D = E_{y^r \bmod p}( M )$ (where $E_k(M)$ is the message $M$ encrypted using the key $k$ with some symmetric cipher).

To decrypt a message $(C, D)$ using the public key $x$, you just compute $C^x \bmod p$; this is the value $y^r \bmod p$, which you can then use as the key for the symmetric cipher in $D$.

Now, here comes the interesting part; to update the key from $x$ to $x'$, what the holder of the private key would do is compute $s = x x'^{-1} \bmod p-1$; he then sends it to the user. The user then replaces $(C, D)$ with $(C^s \bmod p, D)$

We can see that the updated ciphertext $(C^s \bmod p, D)$ is a valid ciphertext to the new public key $y' = g^{x'} \bmod p$; the decryption computes $(C^s)^{x'} = C^{x}$, which is the same key that was originally used to encrypt D, hence decryption works as expected.


This is possible with Homomorphic Encryption, though for decryption in this case both keys would be required, and it would be VERY computationally expensive as most fully homomorphic encryption schemes are. This is also possible via secret sharing, though the use case would dictate whether the constraints imposed by this paradigm would be acceptable. In secret sharing schemes the secret, or in this case file, is split into various parts which must be recombined in order for them to be reconstructed to regain the "cleartext". This is different from the ciphertext/key combination for normal encryption.

Homomorphic Encryption: https://en.wikipedia.org/wiki/Homomorphic_encryption

Secret Sharing: https://en.wikipedia.org/wiki/Secret_sharing


Here is an idea: Use a stream cipher, for example AES in counter mode.

If you want to change the key or even use an other stream cipher, you send the XOR of the keystream of the old cipher and the keystream of the new cipher. The receiver who has the file stored then XORs the ciphertext with this data.

The downside is that the data you have to send is as large as the file. But this is still better then downloading the file, re-encrypting it, and then uploading it again.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jul 5 '17 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.