How and why does Recrypt function work?

Question

The general aproach presented by Craig Gentry in 2009 to create a fully-homomorphic encryption system is roughly the follow:

• Create a scheme that can evaluate some functions (increasing the noise in the ciphertext)

• Change you decryption function to be one of these functions that can be evaluated

• Use a function Recrypt to somehow decript and encrypt again the ciphertext to eliminate the noise introduced by the homomorphic operations.

The idea seems wonderfull, but, I don't understand well how and why this Recrypt function work...

For example, in the section 4.3 of the paper Computing Arbitrary Functions of Encrypted Data, he explains it like that:

Imagine that we have a list of public keys $p_1, p_2, .. $ and a private key $s_1$, then, we encrypt $m$ using $p_1$ generating $c_1$.

Then, we encrypt each bit of $s_1$ using $p_2$ generating a vector of ciphertexts $\overline{s_1}$.

Then, Recrypt encrypts each bit of $c_1$ using $p_2$ generating the array $\overline{c_1}$ and evaluate the decryption citcuit $D$ in $\overline{c_1}$, $\overline{s_1}$ and $p_2$.

It seems like recrypt tries to decrypt the $\overline{c_1}$ with a wrong key (since it was encrypted with $p_2$, I was expecting something like $s_2$...).

Could someone here just try to explain how this Recrypt works? I don't know what I'm missing...

If my question is unclear, please, let me know.

Thanks.

Answer 1

At a high-level (ignoring the messier details), recryption that boosts bounded-depth homomorphism to unbounded-depth homomorphism works as follows:

Suppose you have a public-key "somewhat-homomorphic" encryption scheme with procedures:

1. $(PK, SK) \leftarrow Gen(1^{secparam}; coins)$: generates encryption/decryption keys
2. $c \leftarrow Enc(PK, m; coins)$: encrypts message $m$ as ciphertext $c$ under key $PK$
3. $m \leftarrow Dec(SK, c)$: decrypts ciphertext $c$ using key $SK$ to message $m$
4. $c^* \leftarrow Eval(C, c_1, ..., c_k)$: given ciphertexts $c_1, ..., c_k$ and a circuit description $C$, computes $c^* = Enc(C(m_1, ..., m_k))$

where "somewhat-homomorphic" means $Eval$ can only correctly (and succinctly) compute ciphertexts $c^*$ when the circuit $C$ has bounded depth (in some well-defined sense).

Correctness just means that w.h.p. over honest $(PK, SK) \leftarrow Gen$, for all $C, \{m_i\}_i$, we have $C(m_1, ..., m_k) = Dec(SK, Eval(C, Enc(PK, m_1; coins_1), ..., Enc(PK, m_k; coins_k)))$. I.e. that if you use the scheme 'honestly,' you get correct decryption of (possibly $Eval$'d) ciphertexts.

---

That said, the observation is that the $Dec$ procedure, when written as a circuit, is a bounded-depth computation. Therefore, we can run $Eval$ on $C = \langle Dec\rangle$ when given (say) $SK_1$ and $Enc(PK_1, m)$ with BOTH encrypted under $PK_2$

To use this, we augment the $Gen$ procedure to first honestly generate two key-pairs $(PK_1, SK_1), (PK_2, SK_2)$. Then, $Gen$ creates a "recryption" key $RK_{1\rightarrow 2} = Enc(PK_2, SK_1)$ -- that is, the encryption of the key $SK_1$ under $PK_2$.

The scheme begins with the keys above, messages $\{m_i\}$ and a circuit $C$, and first creates ciphertexts $c^{(1)}_i = Enc(PK_1, m_i)$.

In order to recrypt, (conceptually) we can then doubly-encrypt the $\{c^{(1)}_i\}$ under $PK_2$. That is, create $c^{(2)}_i = Enc(PK_2, c^{(1)}_i) = Enc(PK_2, Enc(PK_1, m_i))$.

Then, under key $PK_2$, we perform (for each $i$) $Eval(\langle Dec\rangle, RK_{1\rightarrow 2}, c^{(2)}_i)$ obtaining a ciphertext $c^*_i$. By the correctness of $Eval$ and $Dec$, we have $c^*_i = Enc(PK_2, C(first\_plaintext, second\_plaintext)) = Enc(PK_2, Dec(SK_1, c^{(1)}_i)) = Enc(PK_2, m_i)$.

---

The 'messier details' in fact show that these $\{c^*_i = Enc(PK_2, m_i)\}$ are "fresh" ciphertexts under $PK_2$, meaning we have the full "bounded-depth" of $Eval$ available to us. Therefore, if $Eval$ can support at least the depth of the $Dec$ circuit, plus one, then you are able to perform unbounded-depth homomorphic computation (by further assuming circular security, and posting both $RK_{1\rightarrow 2}$ and $RK_{2\rightarrow 1}$, then toggling between the two keys with each recryption). In other words, you compute one step of the computation of some given circuit $C$, then you recrypt, and repeat.

P.S. If you go through significantly more effort (involving program obfuscation techniques), you can also obtain FHE without the circular security assumption. See: http://eprint.iacr.org/2014/882