# Security of Homomorphic encryption schemes

Usually for cryptosystems the security is denoted as a $2^n$-bit security such as 256-bit, 1024-bit, 2048-bit etc whereas I came across homomorphic schemes mentioning 80-bit and 96-bit security.

Is this secure enough? Why does it not follow the $2^n$-bit security?

• I think it is a misunderstanding that security must be expressed at $2^n$-bit for some $n$. This is no requirement. AES for example comes in a 192-bit variant, the same does twofish. DES and 3DES also have non-two-power key sizes. – Guut Boy Oct 19 '16 at 11:31

Why does it not follow the $2^n$-bit security?

They follow the usual way of describing schemes, i.e., $n$ bits of security means $2^n$ operations to the best attack. So, taking $n = 80$, you impose "an effort" of $2^{80}$ to the attacker.

Is this secure enough?

This is a tricky question. That depends on what you want to do with the scheme and how powerful the attacker is supposed to be.

Anyway, I think the main reason to have $n = 80$ in this kind of paper, is that homomorphic encryption schemes are very expensive and authors just want to show a proof of concept. Anyone that wants to use these cryptosystems is free to instantiate them with larger values of $n$.

It seems it actually does follow the $2^n$ bit security. Normally we define the effective security relative to the security of perfect block ciphers. So that's, for instance, AES-128, 192 and 256 bit security.

The key sizes of asymmetric primitives are however much higher than their effective security. 1024 bit RSA (factorization) or 1024/160 bit security (discrete logarithm, e.g. DH or DSA) is comparable to a symmetric key size of about 72 bits. 2048 bits RSA keys are comparable to 88 bits etc. You can calculate these yourself by using the equations on the top of the keylength.com website.

Now 80 and 96 bits is not a huge amount of effective security, but it is still out of the range of brute force attacks. You might however want to enforce a higher amount of effective security for data that you want to protect for longer. Definitely use 96 bits rather than 80 bits of security if that is efficient enough within your solution.

• I wouldn't say that it's not a huge difference in 80 and 96 bit security. It is still a factor of $65536$, comparable to the difference between $1$ second and $\approx 18$ hours. One more reason why most often keysizes and block sizes are chosen as $2^n$ is the technical side: Computers operate on bits and pretty much all the common units in a computer (bytes, words, integers,...) are also of that format. – tylo Oct 19 '16 at 12:00