8
$\begingroup$

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$.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I did not get why he suggested doing bit by bit , any idea ? . my head is reeling with the possibilities of FHE already ! :) $\endgroup$
    – sashank
    Commented Aug 2, 2013 at 3:40
  • $\begingroup$ @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. $\endgroup$
    – xagawa
    Commented Aug 2, 2013 at 3:51
  • 2
    $\begingroup$ @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." $\endgroup$
    – Mayank Varia
    Commented Aug 2, 2013 at 23:19
3
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Reid , any idea why he suggested doing bit by bit $\endgroup$
    – sashank
    Commented Aug 2, 2013 at 3:42
0
$\begingroup$

As others have pointed out, there are schemes. However, I understand this question was asked a few years ago, but now you can find implementations of re-encryption without decryption in FHE schemes:

https://gitlab.com/palisade

Look at ReEncrypt function under here (Bgv scheme). The library supports other FHE schemes as well, I'll leave you to explore it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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