4
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ What do you need an encryption of in order to run "the decryption function homomorphically"? ​ ​ $\endgroup$ – user991 Oct 24 '16 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$ – Hilder Vitor Lima Pereira Oct 25 '16 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 Oct 25 '16 at 1:03
  • 1
    $\begingroup$ @RickyDemer I would appreciate if you could explain why this limitation exists. Maybe you can turn your comment in an answer... (: $\endgroup$ – Hilder Vitor Lima Pereira Oct 25 '16 at 13:09
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This bootstrapping is what I called the "Gentry's blueprint". I know how it works. I think my doubt arose because I was ignoring that the secret key is also an input of the refresh procedure. C'est bien, merci bcp Florian (: $\endgroup$ – Hilder Vitor Lima Pereira Jan 17 '17 at 17:31
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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