2
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ "So, this structure would not be a ring anymore, it will be field."; actually, all fields are also rings (as they meet all the requirements required of a ring - it's just that they meet the additional requirements of a field) $\endgroup$
    – poncho
    Feb 22 at 15:27
  • $\begingroup$ If R is a field, then what is the inverse of 2 in R? $\endgroup$ Feb 22 at 15:50
  • 1
    $\begingroup$ @HilderVitorLimaPereira: actually the ring he quoted Z[x]/(x^n+1) is not a field; however with RLWE we actually use $\mathbb{Z}_p[x]/(x^n+1)$, which may be $\endgroup$
    – poncho
    Feb 22 at 16:06
  • 1
    $\begingroup$ @HilderVitorLimaPereira I suppose that $R$ shall modulo a prime $q$, like $R = Z_q[X] / (X^n + 1)$, and that is standard in Ring LWE. That way, 2 has inverse in $R$. $\endgroup$
    – xacid
    Feb 22 at 16:06
  • $\begingroup$ @poncho I just wanted he/she to realize that R is not a field, so the answer his/her question is just, well, "it is called ring LWE because we use rings" $\endgroup$ Feb 22 at 23:40

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.