About converting Leveled FHE to Pure FHE and the Circular Security Assumption

Question

As it was pointed out in one answer of this question, the BGV paper has a footnote that says

One can obtain a "pure" FHE scheme (with a constant-size public key) from these leveled FHE schemes by assuming "circular security", namely that it is "safe" to encrypt the leveled FHE secret key under its own public key.

However, I do not understand how the circular security assumption is related to this transformation from a leveled FHE to a pure FHE.

In my understanding, any leveled FHE can be turned in a pure FHE by setting the acceptable multiplicative depth, that is, the parameter $L$, to a value large enough to evaluate homomorphically the decryption circuit plus one operation and then apply the Gentry's blueprint, namely, refresh the ciphertexts after any operation by running the decryption function homomorphically.

So, can anyone explain what authors of BGV mean with that footnote or show what is wrong with my understanding ?

Answer 1

Let me try to explain you how the bootstrapping works, then you will have a better idea of why you need circular security to reach pure FHE and not just leveled FHE:

Suppose you have a ciphertext $C$ that you want to refresh.
The idea of bootstrapping is to homomorphically evaluate the decryption circuit: $Dec(C,k) \rightarrow m$.
Now, remark that the Decryption circuit uses two inputs: $C$ and $k$. So in order to evaluate it, you need to have two ciphertexts:
One that encrypts $C$ - which you can create on your own since you know $C$
And one that encrypts $k$: this is where you have to use circular security.

Once you understand this principle, there is an easy optimization you can do: instead of evaluating $Dec$, you can evaluate $Dec_C: k \rightarrow m$ in which the ciphertext has been hardwired. Thus you only need a ciphertext encrypting $k$, and don't need to have 2 layers of encryption.

I hope this high level overview of bootstrapping helps you better understand FHE.

Answer 2

You need the "circular security" assumption to obtain an FHE scheme with a single public-private key pair, as you want to homomorphically decrypt using the private key $k_0$ (whose corresponding public key was used for encrypting the data) that is encrypted using a public key $k_1$.

If the public key $k_1$ used for encrypting the private key $k_0$ is the "partner" of the private key $k_0$ in the public-private key pair, then you can repeatedly use the encryption of $k_0$ under $k_1$ to get your pure FHE-scheme via Gentry's bootstrapping, but to prove security you need the "circular security" assumption (cycle length 1).

Otherwise there is some other private key $k_2$ belonging to the public key $k_1$, so that in your second application of Gentry's bootstrapping you now need an encryption of the private key $k_2$ under some public key $k_3$. You can define in this way a sequence of keys $(k_i)_{i\in\mathbb N_0}$ (where for odd $i$ the keys $k_i$ are public keys and for even $i$ private keys, and for $i$ odd the key $k_{i+i}$ is the matching private key for the public key $k_i$).

If all the keys $k_i$ are different, then you don't need the "circular security" assumption, but your system needs infinitely many different public keys as well as infinitely many different encryptions of private keys, which is not really satisfying. If you have some repetition, then you can choose $k_i = k_{i+2\cdot n}$ for some $n\in\mathbb N$, but for proving security you need the "circular security" assumption (cycle length n).