Ring Learning With Errors : why is it called ring and referred it as Ring LWE

Question

I am curious about the structure of the quotient ring in Ring LWE. So $R=\mathbb Z_q[x]/(x^n+1)$, where q is prime, $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure would not be a ring anymore, it would be a field. So, why is it called ring and referred it as Ring LWE?

Answer 1

So $R = \mathbb{Z}[x]/(x^n+1)$, where $x^n+1$ is an irreducible polynomial and n is a power of 2. So, this structure would not be a ring anymore, it would be a field. So, why is it called ring and referred it as Ring LWE?

As mentioned in the comments, there are two points to highlight.

1. One doesn't work with $R$ directly, but instead $R_q := R / qR\cong \mathbb{Z}_q[x]/(x^n+1)\cong \mathbb{Z}[x]/(q, x^n+1)$. Here $q$ can be any natural number really.
2. Fields are rings

So provided Ring-LWE does not make usage of "Field-only operations" (namely division), calling it "Ring"-LWE is not being deceptive. Note that certain other lattice-based schemes do, namely NTRU requires the secret key to be invertible modulo certain quantities.

The main other thing I will highlight is that $R_q$ is often not a field. In particular, when $q = \prod_i p_i^{e_i}$ is not prime, one has that

$$ R_q \cong \prod_i R_{p_i^{e_i}} $$

by the Chinese remainder theorem. This has zero divisors for the same reason that $\mathbb{Z}/(pq)\mathbb{Z}\cong \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$ does, so is not a field.

Working with such non-prime $q$ is frequently useful. Two such cases are

1. $q = 2^k$. Then modular reductions can be replaced with bit shifts, and modular arithmetic can use hardware multipliers included in most hardware, instead of needing (slower) software. The KEM Saber made this parameter choice, though Kyber ended up being selected by NIST to be ML-KEM.

2. $q = \prod_i p_i$. This is often used in Fully Homomorphic Encryption, when one requires $q$ with $\log_2 q\geq 64$ (or realistically $60$ but that's a small detail). By using the above CRT isomorphism, one can reduce arithmetic mod $q$ into parallel computations of arithmetic mod $p_i$ for $\log p_i \leq 60$. Arithmetic mod $p_i$ for $\log p_i\leq 60$ is much faster, as one can give a software implementation of modular arithmetic where the underlying (integer) arithmetic uses hardware multipliers. Arithmetic mod $q$ directly would require "big integer" arithmetic, which is slower in comparison.