Noise in Homomorphic encryption

Question

What is the noise in homomorphic encryption schemes? (or where does the noise come from, I see that its inbuilt in the scheme and is not a side channel or disturbance noise)

Is it also due to the noise that HE is a probabilistic scheme ?

Answer 1

The noise is usually a small term added into the ciphertext while encrypting.

This term may be a small integer (if the scheme is based on integers) or a small polynomial (if the scheme is based on polynomials), etc.

How to decide if a term is small or not depends on the security and correctness properties of each system (for instance, a polynomial is typically considered small if all its coefficients are small).

This noise is added to guarantee the security of the cryptosystems and is sampled from a distribution of small terms (for instance, from a set of polynomials with coefficients in $\{-1, 0, 1\}$). Therefore, the noise is random. So, it implies that the HE scheme is probabilistic, but, in general there are other random values involved in the encryption process, so, I don't know if it is right to say the probabilistic property is due to the noise... (But I hope you got the point).

The decryption function does not work if the noise is greater than a certain maximum value (each scheme with each set of parameters used has its own limit) and the homomorphic operations increase the noise, that is the reason the number of operations is usually limited and there are several techniques to control the noise growth.

As an example, take the symmetric "toy-scheme" from Fully Homomorphic Encryption over the Integers:

• the integer $p$ is the private key.
• to encrypt a bit $m$ into a (big) integer $c$, we sample integers $q$ and $r$ and do $c = pq + 2r + m$.
• to decrypt $c$ we do $c \mod p$, wich gives us $2r + m$ if $2r + m$ is smaller than $p$, then we reduce $\mod 2$, ending up with $m$.

Do you see that if $2r$ is bigger than $p$, then decryption will not work? (because reducing mod $p$ would not result in $2r + m$ in this case). So, this $2r$ is the noise in this scheme.

Note that taking $c_0 = pq_0 + 2r_0 + m_0$ and $c_1 = pq_1 + 2r_1 + m_1$, we have

$c_0 + c_1 = p(q_0 + q_1) + 2(r_0 + r_1) + (m_0 + m_1)$

which means a addition increases the noise. The multiplication also does so (take a look on the paper).

Therefore, since each operation increases the noise and there is a maximum acceptable value for the noise, the number of operations is limited.