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 ?

  • $\begingroup$ What do you need an encryption of in order to run "the decryption function homomorphically"? ​ ​ $\endgroup$
    – user991
    Commented Oct 24, 2016 at 23:53
  • $\begingroup$ @RickyDemer Are you suggesting that we need encryptions of the key? Because if it is that, I do not understand why it is needed, since we can set up $L$ keys in BGV and evaluate the decryption function as it was any other function... $\endgroup$ Commented Oct 25, 2016 at 0:17
  • 1
    $\begingroup$ Yes. ​ ​ ​ Without creating a cycle, setting "up $L$ keys in BGV and" evaluating "the decryption function as" if "it was any other function" limits you to ​ $L\hspace{-0.03 in}-\hspace{-0.04 in}1$ ​ sequential refreshes. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Oct 25, 2016 at 1:03

2 Answers 2


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.