# How and why does Recrypt function work?

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.

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

• Thank you, @DanielApon. I'm still reading your answer and trying to understand it... But I already have an issue: The keys generated by Gen are $(PK_1, SK_2)$ and $(PK_2, SK_2)$ as you said, or the first pair should be $(PK_1, SK_1)$ ? Dec 21, 2014 at 16:40
• You're correct-- I had a typo there; it's fixed now. Dec 22, 2014 at 22:15
• In case it helps your understanding, here's a shortened, "color-coded" description: i.imgur.com/0hXewk7.png Here, [m] denotes a ciphertext encrypting a message m. Same-color keys encrypt to/decrypt from same-color bracketed ciphertexts (e.g. a "red SK" can be used to decrypt [m] whose brackets are red, etc.) Hopefully, this will help 'separate out' the various layers of encryption, and when they come into play. It might also help to imagine TOR, except in each iteration you decrypt the inner layer to bootstrap (instead of the outer layer, as in TOR). Dec 22, 2014 at 22:19
• the image is clear! I got it: since it's homomorphic, f(cipher1, cipher2) = f(text1, text2), and in this case, f is Dec, text1 is the secret key and text2 is the first ciphertext... Sometimes we saw that something is not too hard, but we just have to talk to someone to understand it. Thank you! Dec 23, 2014 at 0:15
• Don't forget awarding the bounty to Apon :) Dec 23, 2014 at 0:26