0
$\begingroup$

I'm wondering why Ring-LWE based homomorphic encryption (somewhat homomorphic encryption, not fully) requires low-degree polynomial in order to avoid decryption error. For example, a plaintext $m$ is an element over some polynomial ring, i.e. $m\in \mathbb{Z}_t[X]/(X^N+1)$ where $t$ is a prime and $N$ is a power of two integer.

More redundantly, $m= m_0 + m_1 X + m_2 X^2 + \ldots + m_{N-1}X^{N-1}$. A noise $e$ is also a polynomial sampled from discrete gaussian distribution.

I do not know why polynomial degree is considered. Noise amount on each coefficient violates on each coefficient of the plaintext polynomial. Is this correct?

$\endgroup$
  • $\begingroup$ First of all, are you sure of that $B$ in the definition of the ring? I guess it is simply $X^N+1$ instead. $\endgroup$ – Hilder Vítor Lima Pereira Mar 29 '18 at 7:46
  • $\begingroup$ Sorry, it's a typo. I fixed it. $\endgroup$ – mallea Mar 29 '18 at 7:47
  • $\begingroup$ So, your question is why do we work over $\mathbb{Z}_t[X] / \langle X^N + 1 \rangle$ instead of working over $\mathbb{Z}_t[X]$? $\endgroup$ – Hilder Vítor Lima Pereira Mar 29 '18 at 7:48
2
$\begingroup$

The ciphertexts contains a certain amount of noise for security reasons. The downside is that if this noise is too big, the decryption will fail. When using homomorphic operations, the noise contained in the output ciphertext will be bigger than the one in the input ciphertexts.

Now when adding ciphertexts, the new noise is just the sum of previous noises, but when doing multiplication, the noise grows faster, and ultimately, only knowing the number of multiplication you're doing is a good approximation to know how to set your parameters.

This is why you prefer low degree polynomials to high degree polynomials, to avoid the noise growing too large.

Second question would be why do we do polynomials? Well, basic operations here are just additions and multiplications, which gives only polynomials - but it can represent any function so it's ok!

$\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.