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

<p>Suppose you have a public-key "somewhat-homomorphic" encryption scheme with procedures:</p>

<ol>
<li>$(PK, SK) \leftarrow Gen(1^{secparam}; coins)$: generates encryption/decryption keys</li>
<li>$c \leftarrow Enc(PK, m; coins)$: encrypts message $m$ as ciphertext $c$ under key $PK$</li>
<li>$m \leftarrow Dec(SK, c)$: decrypts ciphertext $c$ using key $SK$ to message $m$</li>
<li>$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))$</li>
</ol>

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

<p>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.</p>

<hr>

<p>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$</p>

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

<p>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)$.</p>

<p>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))$.</p>

<p>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)$.</p>

<hr>

<p>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>

<p>P.S. If you go through significantly more effort (involving program obfuscation techniques), you can also obtain FHE without the circular security assumption. See: <a href="http://eprint.iacr.org/2014/882" rel="nofollow">http://eprint.iacr.org/2014/882</a></p>

CC BY-SA 3.0
2014-12-21T16:40:09.403Z
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)$  ?
Hilder Vitor Lima Pereira
CC BY-SA 3.0
2014-12-22T22:15:06.093Z
You're correct-- I had a typo there; it's fixed now.
Daniel Apon
CC BY-SA 3.0
2014-12-22T22:19:31.437Z
In case it helps your understanding, here's a shortened, "color-coded" description: http://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).
Daniel Apon
CC BY-SA 3.0
2014-12-23T00:15:02.810Z
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!
Hilder Vitor Lima Pereira
CC BY-SA 3.0
2014-12-23T00:26:54.063Z
Don't forget awarding the bounty to Apon :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-23T10:47:19.673Z
Oh, it is not automatic when I mark the anwser as correct...  I'll award the bounty now.
Hilder Vitor Lima Pereira
CC BY-SA 3.0
2014-12-21T15:52:34.683Z
2014-12-22T22:14:47.223Z
2014-12-22T22:14:47.223Z
Daniel Apon
<p>The general aproach presented by Craig Gentry in 2009 to create a fully-homomorphic encryption system is roughly the follow:</p>

<ul>
<li><p>Create a scheme that can evaluate some functions (increasing the noise in the ciphertext)</p></li>
<li><p>Change you decryption function to be one of these functions that can be evaluated</p></li>
<li><p>Use a function <strong>Recrypt</strong> to somehow decript and encrypt again the ciphertext to eliminate the noise introduced by the homomorphic operations.</p></li>
</ul>

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

<p>For example, in the section 4.3 of the paper <a href="http://crypto.stanford.edu/craig/easy-fhe.pdf" rel="nofollow">Computing Arbitrary Functions of Encrypted Data</a>, he explains it like that:</p>

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

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

<p>Then, <strong>Recrypt</strong>  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$.</p>

<p>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$...).</p>

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

<p>If my question is unclear, please, let me know.</p>

<p>Thanks.</p>

<homomorphic-encryption>
How and why does Recrypt function work?
Hilder Vitor Lima Pereira
# How and why does Recrypt function work?

(Asked by: username_0 on 2014-12-17)

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](http://crypto.stanford.edu/craig/easy-fhe.pdf), 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.

**Tags:** homomorphic-encryption

---

## 1 answers

### Answer by username_1 on 2014-12-21. Score: 6 | Accepted answer

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>

> **Comments:**
> **username_0**: 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)$  ?  
> **username_1**: You're correct-- I had a typo there; it's fixed now.  
> **username_1**: In case it helps your understanding, here's a shortened, "color-coded" description: http://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).  
> **username_0**: 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!  
> **username_2**: Don't forget awarding the bounty to Apon :)  
> **username_0**: Oh, it is not automatic when I mark the anwser as correct...  I'll award the bounty now.  

---

