I check some key size which FHE libraries generated, for example, HElib's key size will be more than 300M, while tfhe's is also nearly 100M. Since these keys are so long, does it guarantee FHE encryption is more safer than traditional encryption, such as RSA?

  • 1
    $\begingroup$ Is 512-bit RSA more secure than 256-bit ECC? $\endgroup$
    – yyyyyyy
    Sep 25 '17 at 17:55

No, the large sizes basically come from the fact that one needs to be able to handle a very large error term in order to perform a procedure known as "bootstrapping." The basic idea of bootstrapping is that we use a "base" homomorphic system which is somewhat error-prone; that is, the decryption of $c_1 \oplus c_2$ is intrinsically some $m_1 + m_2 + \epsilon$ for some error $\epsilon$. As we evaluate more and more $\oplus$ gates we accumulate more and more error, but we can solve this problem by including more and more bits per "signal" bit to handle the "noise" bits, and there are even clever ways to shift moduli as-you-go to keep the absolute magnitude of the error down for multiplications and so forth -- what's important is that you can either limit the depth of the circuits you use, or increase the size of the state space. Finally as part of decrypting, we end up truncating this error.

In bootstrapping, we take the fixed ciphertext that we have built up so far (which we of course know) and we form the circuit which would take a variable private key (which we of course don't know) and decrypt this ciphertext with that key. So, we "homomorphicize" this decryption circuit by treating the key as the input and the ciphertext as fixed, known boolean constants. We can then apply the homomorphic circuit to an encrypted private key $\kappa = E_k(k)$ that is stored as part of the public key, to get an "encrypted decrypted ciphertext" -- in other words, to get a new representation of our fixed ciphertext, $c \mapsto c'.$

This sounds completely useless and it is completely useless if you do not include the homomorphic version of the logic which truncates the error. But when the homomorphic error-truncation logic enters the picture, something magical happens: whatever $\epsilon_c$ has been built up so far in $c\leftrightarrow m + \epsilon_c$ gets replaced with a fixed error, $c'\leftrightarrow m + \epsilon_0.$ This error only depends on the depth of the decryption circuit (when viewed in this backwards key-first way).

I like the analogy for bootstrapping that one of the TFHE researchers gave: Spider-man can only swing for a certain time on one piece of webbing before it "runs out" (and he starts going backwards or something). But Spider-man is able to swing an arbitrary time/distance. How does he do this? While he is swinging he devotes some of his time to firing out another piece of webbing, and switches to that before the current piece "runs out". Similarly we have an error threshold of operations; we can only continue for a certain number of operations before we "run out", and so we devote a certain number of these operations to resetting our error bars on our ciphertext state and then we can continue doing this again.

Anyway, for a long story short, the combination of the tolerable error margins and the width of the key/plaintext/ciphertext together set the security level; and you may need to increase the width of the key text without making the key any more secure, in order to handle larger homomorphic circuits. The docs for the TFHE software for example specify that they target only a 110-bit security level; that places its security roughly at the 2048-bit RSA level according to a 2003 estimate from RSA security. The fact that it has megabyte-size keys is purely to handle the errors needed to bootstrap successfully.


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.