# Does FHE's longer key bring more security than traditional encryption algorithm?

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?

• Is 512-bit RSA more secure than 256-bit ECC? – 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).