How to understand “homomorphically decrypting” in bootstrapping?

I come across the following explanation of bootstrapping in this tutorial:

Once the “noise” in a ciphertext grows too large it is no longer able to be decrypted properly. Bootstrapping solves this problem. It does so by homomorphically decrypting the ciphertext, performing a single computation on it, and then recrypting under a different public key.

What is the meaning of homomorphically decrypting? Does it mean decrypt to the plaintext first then recrypt again?

Does it mean decrypt to the plaintext first then recrypt again?

No. It doesn't. It just mean to run a "homomorphic version" of the decryption function. Since homomorphic evaluation just use homomorphic operations and these operations always return ciphertexts, the result of homomorphic decryption is also a ciphertext. And since the decryption removes the noise, this new ciphertext is fresh.

Think of evaluating homomorphically as a function, which we will call $$Eval$$.

So, homomorphically evaluating any function $$f$$ on arguments $$m_0$$, $$m_1$$, ..., $$m_\ell$$ means to execute $$Eval(pk, f, [m_0]_{pk}, [m_1]_{pk}, ..., [m_\ell]_{pk})$$, which returns $$[f(m_0, m_1, ..., m_\ell)]_{pk}$$.

(Here I'm using $$[m]_{pk}$$ to denote the encryption of $$m$$ under the public key $$pk$$).

That is, $$Eval$$ returns an encryption of the function evaluated in the arguments, given the function, encryptions of those arguments, and the public key used to encrypt them.

Now, let's say you have a pair of keys $$sk$$ and $$pk$$ and you want to refresh a ciphertext $$c = [m]_{pk}$$. Then, you have to homomorphically decrypt $$c$$. To do so, replace $$f$$ by $$Dec$$. Also, the arguments of $$Dec$$ are $$sk$$ and $$c$$, so, you should use $$[sk]_{pk_1}$$ and $$[c]_{pk_1}$$, for some public key $$pk_1$$. Then, we get:

\begin{align} Eval(pk_1, Dec, [sk]_{pk_1}, [c]_{pk_1}) &= [Dec(sk, c)]_{pk_1}\\ &= [m]_{pk_1}\\ \end{align}

that is, a fresh encryption of $$m$$ under the public key $$pk_1$$.

Note that this $$pk_1$$ may be a new public key, and in this case we will need a new secret key $$sk_1$$ to decrypt $$[m]_{pk_1}$$, or it can be equal to the original public key $$pk$$, and in this case we are supposing circular security...

• Also, this question may be helpful: crypto.stackexchange.com/questions/40952/… – Hilder Vitor Lima Pereira Apr 11 '17 at 13:24
• So in Eval function, the pk or pk1 is also called "evaluation key", is it right? Thanks! – Nan Xiao Apr 12 '17 at 8:36
• @NanXiao well, it might be. It depends on the definitions the paper uses. It could be defined so that it receives also an integer number that tells in which level the ciphertexts are (in leveled FHE)... – Hilder Vitor Lima Pereira Apr 20 '17 at 10:12

The key feature of fully homomorphic encryption systems (FHE) is that one can execute arbitrary algorithms (more precisely circuits) on encrypted data (without first decrypting and then encrypting it again). A somewhat fully homomorphic encryption system (SFHE) can do almost the same, but only for algorithms of restricted complexity (meaning the circuits have a bounded depths, i.e., number of AND-gates data flows from input to output).

If the decryption algorithm for an SFHE has a complexity lower than the complexity of algorithms the SFHE is able to execute on encrypted data, then one can execute it by first encrypting the noisy ciphertext with the SFHE using a new key (yielding a double-encrypted result). Then one applies the decryption algorithm (using the old key encrypted under the new one) homomorphically on the freshly encrypted noisy ciphertext, which removes the "inner encryption" giving an encryption (under the new key) of the decrypted noisy ciphertext, i.e., an encryption (under the new key) of the plaintext belonging to the noisy ciphertext.

So "homomorphically decrypting" means to apply the decryption algorithm directly on the encrypted data yielding an encryption of the decrypted data (like "homomorphically multiplying" encrypted data yields the encryption of the product of the data, not the product of the encrypted data).

• The homomorphically decrypted ciphertext is as "new ciphertext" not quite as fresh as one might hope for: it's a fresh ciphertext on which the decryption algorithm was already executed homomorphically. – itsme Apr 11 '17 at 16:12