What exactly is bootstrapping in FHE?

Question

I have been reading about FHE lately, and it seems that bootstrapping is the core concept in order to develop FHE schemes. But, I don't exactly understand the idea behind it. I know that the schemes based on Gentry's design are noise-based, and that the noise increases with each homomorphic operation, and if the noise exceeds certain threshold, then decryption will fail. I guess bootstrapping was developed as a solution to this problem. But what exactly is bootstrapping?

I came across following definition, but I don't understand what it wants to say.

Definition: A $\mathcal{C}$-evaluation scheme is called bootstrappable if it is able to homomorphically evaluate its own decryption circuit plus one additional $\mathsf{NAND}$ gate.

I know what a $\mathcal{C}$-evaluation scheme is, but what exactly it means with "homomorphically evaluate its own decryption circuit", and why the "plus one $\mathsf{NAND}$ gate"?

Answer 1

First off, from your question, it is not clear whether or not you understand the "circuit" part. So I'll start there. With (most) FHE schemes, you are evaluating circuits, or a bunch of gates hooked together. Often, we think of circuits in terms of and/or/not gates. It turns out, however, that you can construct circuits from other types of gates. NAND by itself is functionally complete. So, with just a single NAND gate, you can construct any circuit. That is why we need a scheme that can compute at least one NAND gate (in addition to its own decryption circuit).

As you stated, FHE schemes add noise to the ciphertext. So, you can evaluate a circuit on the input ciphertext(s), but you may add so much noise in the process of doing this that you can no longer decrypt. That is the problem we are faced with. It is important to remember that inputs to the circuits are ciphertexts, and that the output of the circuit is a ciphertext.

What Gentry gave us what a somewhat homomorphic encryption scheme. After evaluating too many gates, the noise becomes too much and we can no longer decrypt. But, he showed that by taking the decryption algorithm for his scheme and converting it into a circuit and passing the circuit a ciphertext and an encrypted version of the private key, what you would get out was a ciphertext of the same plaintext, but with the noise gone. Furthermore, the cipher allowed you to run at least one NAND gate on two ciphertexts (a couple of gates that were equivalent to a NAND) and the decryption circuit without the noise being too much.

So, let's say we can execute one NAND gate and the decryption circuit homomorphically and still be okay noise-wise. Given a circuit like this (A NAND B) NAND (C NAND (D NAND A)) we would actually execute it as (say DEC is the decryption circuit using an encrypted version of the private key):

DEC(
  DEC(
    A NAND B
  ) 
  NAND 
  DEC(
    C NAND 
    DEC(D NAND A)
  )
)

So after every NAND you would insert a DEC to eliminate the noise. I should note that even though the last thing you evaluate is DEC, the value that comes out is encrypted.