Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Homomorphic encryption schemes are PKE schemes with an additional special method Evaluate.

The Evaluate method takes input any function (as boolean circuit) and encrypted inputs of the function and evaluates the circuit. The results of such function are still encrypted under the public key $PK$.

Now, if the user needs to re-encrypt the data with a new public key $PK^1$, the user should decrypt the data with older private key $SK$ first, and then encrypt again with new $PK^1$.

Or how can I efficiently proxy-re-encrypt using FHE schemes without decrypting the data?

Note that if the user runs the re-encrypt circuit as input to the Evaluate method with $PK^1$ as parameter, the result would still be encryption of (encryption of original data with new $PK_1$) with the older $PK$.

share|improve this question
up vote 5 down vote accepted

YES. It is pointed out by Gentry (in his thesis) when he consider bootstrapping and re-encryption.

Let us denote the old key pair by $(PK, SK)$ and the new key pair by $(PK^1, SK^1)$.

What the user wants is to re-encrypt an old ciphertext $C = \mathsf{Enc}(PK, M)$ into a new ciphertext $C^1$ which is decrypted into $M = \mathsf{Dec}(SK^1,C^1)$.

To do so without direct decryption, we virtually decrypt $C$ in the draft chamber guarded by $PK^1$, that is, we evaluate a decryption circuit with $PK^1$. Correctly speaking, we do the following:

  1. Generate $\widetilde{SK}_i = \mathsf{Enc}(PK^1,SK_i)$, where $SK_i$ denotes the i-th bit of $SK$.
  2. Compute $\widetilde{C}_i = \mathsf{Enc}(PK^1,C_i)$, where $C_i$ denotes the i-th bit of $C$.
  3. Evaluate the decryption circuit. That is, $C^1 = \mathsf{Eval}(PK^1, \mathsf{Dec}, (\widetilde{SK}_1,\dots,\widetilde{SK}_n,\widetilde{C}_1,\dots,\widetilde{C}_m))$.

From the correctness of evaluation, we have $$ \begin{align} \mathsf{Dec}(SK^1,C^1) &= \mathsf{Dec}(\mathsf{Dec}(SK^1,\widetilde{SK}_1),\dots,\mathsf{Dec}(SK^1,\widetilde{SK}_n),\mathsf{Dec}(SK^1,\widetilde{C}_1),\dots,\mathsf{Dec}(SK^1,\widetilde{C}_m))\\ &= \mathsf{Dec}(SK_1,\dots,SK_n,C_1,\dots,C_m) \\ &= \mathsf{Dec}(SK,C)\\ &= M \end{align} $$ as we want.

This is just re-encryption Gentry suggested in his thesis.

share|improve this answer
I did not get why he suggested doing bit by bit , any idea ? . my head is reeling with the possibilities of FHE already ! :) – sashank Aug 2 '13 at 3:40
@sashank It depends on the size of plaintext space, the ring R. In the original paper, the ring is {0,1} and he "doubly encrypt" bit by bit. – xagawa Aug 2 '13 at 3:51
@sashank Yes, Gentry did that because the usual semantic security guarantee of encryption schemes has a sneaky loophole: it's not at all clear what happens when you encrypt a secret key. As a simple example, think about what happens with a one-time-pad when it's used to encrypt a secret key under itself; it's easy for an attacker to be able to detect when this has happened, even though encryption is supposed to "hide everything" about a message. To learn more about this topic, try Googling for "circular security" or "key-dependent message." – Mayank Varia Aug 2 '13 at 23:19
Thanks Mayank . would check them out ! – sashank Aug 3 '13 at 2:26

Suppose you have some ciphertext $\psi_1 = \operatorname{Enc}_{\mathrm{pk_1}}(\pi)$, where $\pi$ is some plaintext. You want to arrive a new ciphertext $\psi_2 = \operatorname{Enc}_{\mathrm{pk_2}}(\pi)$. The trick is that, since this is an asymmetric scheme, anyone can encrypt data by virtue of the key being public.

So, your first step is to outer-encrypt $\psi$ with the $\mathrm{pk}_2$, i.e.:

$$\psi_d = \operatorname{Enc}_{\mathrm{pk_2}}\left(\operatorname{Enc}_{\mathrm{pk_1}}(\pi)\right)$$

Now, you have a doubly-encrypted plaintext $\pi$. The trick is that the owner of the secret key furnishes the bits of $\mathrm{sk}_1$ encrypted under the new public key. These are to be used in the homomorphic decryption circuit, like so:

$$\psi_2 = \operatorname{Enc}_{\mathrm{pk}_2}\left(\operatorname{HomDecrypt}_{\overline{\mathrm{sk}_1}}\left(\operatorname{Enc}_{\mathrm{pk}_1}(\pi)\right)\right)$$

Here, HomDecrypt is the homomorphically-evaluated decryption circuit, and $\overline{\mathrm{sk}_1}$ is the first secret key encrypted under the new public key. In formal notation, for the homomorphic circuit, we would use the Evaluate function with a specific circuit and inputs, but I think doing that (while being formally correct) is much less clear than the above.

Thus, the idea is to outer-encrypt the original ciphertext with the new key. Then, since the secret key holder furnishes the secret key encrypted under the new public key, it can be used to homomorphically decrypt the inner encryption, leaving you with just

$$\psi_2 = \operatorname{Enc}_{\mathrm{pk}_2}(\pi)$$

which is the intended result. The trick here is that the secret key bits are provided, encrypted, by the secret key holder. (Hence, the key owner still controls the decryption of data.)

share|improve this answer
Thanks Reid , any idea why he suggested doing bit by bit – sashank Aug 2 '13 at 3:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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