Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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...
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).
