2
$\begingroup$

In (lattice-based) cryptography, the quotient ring $\mathbb{Z}[X]/(X^n+1)$ where $n = 2^e$ is a power of 2 is used in various cryptographic schemes (e.g., CRYSTALS-Kyber). It is my understanding that this is a common choice because we can efficiently compute products in this ring using the Number Theoretic Transform (NTT).

Another ring that admits fast multiplications via FFT-techniques is $\mathbb{Z}[X]/(X^n-1)$. However, I have read comments in articles / papers that claim that this ring is not secure since it has "lots of structure" that could be leveraged by an attacker.

My questons are as follows:

  • What exactly is this additonal structure in $\mathbb{Z}[X]/(X^n-1)$? Are there (simple) examples that demonstrate how this can be exploited to attack a cryptosystem?
  • Why does $\mathbb{Z}[X]/(X^n+1)$ not have this structure?
$\endgroup$

1 Answer 1

5
$\begingroup$

common choice because we can efficiently compute products in this ring using the Number Theoretic Transform (NTT)

note that this is only true for special moduli $q\equiv 1\bmod 2n$. Lattice crypto is often defined over this ring without this special moduli though (the cryptosystem "SABER" uses $q = 2^k$ for some $k$ for fast modular reduction, and initially wasn't able to use NTT-type multiplication at all. You can get NTT multiplication for Saber now though, using things like this). Dually, one can get fast NTT-type multiplication in other rings as well, see this.

To see the issue with $\mathbb{Z}[x] / (x^n-1)$, it is worth mentioning that when $n\equiv 0\bmod 2$ is even, that

$$\mathbb{Z}[x] / (x^n-1)\cong \mathbb{Z}[x] / (x^{n/2}-1)\times \mathbb{Z}[x] / (x^{n/2}+1).$$

This is a polynomial version of the chinese remainder theorem. One can break an $n$ dimensional ring into two "independent" $(n/2)$ dimensional rings. Breaking the version of LWE on one of these $n/2$ dimensional rings would break LWE on the full ring. Of course, if $n\equiv 0\bmod 4$, one can iterate this process, and write $\mathbb{Z}[x] / (x^{n/2}-1) = \mathbb{Z}[x] / (x^{n/4}-1)\times\mathbb{Z}[x] / (x^{n/4}+1)$, i.e. reduce breaking degree $n$ RLWE to breaking degree $n/4$ RLWE (and potentially further iterate it).

This is really how you should view $\mathbb{Z}[x] / (x^{n}+1)$. It is the largest-degree factor of $x^{2n}-1$, so implicitly we want to be working in $x^n-1$, but the low-degree factors of this cause issues, so we remove them. To explicitly demonstrate these issues, let $(a(x), a(x)s(x) + e(x))$ be an RLWE sample, where arithmetic is implicitly in $\mathbb{Z}[x] / (x^n-1)$. As $f(x) := x^n-1$ has $f(1) = 1$, we have that $\frac{x^n-1}{x-1}$ is an integer polynomial. We can then factor

$$\mathbb{Z}[x]/(x^n-1) := \mathbb{Z}[x] / (x-1) \times \mathbb{Z}[x] / \left(\frac{x^n-1}{x-1}\right)$$

Evaluation at $1$ projects $a(x) \in \mathbb{Z}[x]/(x^n-1)$ onto its first component in $\mathbb{Z}[x] / (x-1)$. When working modulo $q$, this is simply $\mathbb{F}_q$. Explicitly, taking an RLWE sample $(a(x), a(x)s(x) + e(x))$ and evaluating it at 1 yields $(a(1), a(1)s(1) + e(1))\in\mathbb{F}_q^2$, i.e. a 1-dimensional LWE sample. This is a large reduction in the security of the underlying problem (one would typically expect degree $n$ RLWE to reduce to dimension $n$ LWE). This phenonoma leads to direct attacks on cryptosystems, roughly because they are secure assuming degree $n$ RLWE is hard, but the above shows that degree $n$ RLWE reduces to dimension $1$ LWE, which is (typically) easy.

The underlying issue was that $x^n-1$ factors into the product of lower-degree polynomials. This is morally similar to how things like Pollard rho (for factoring) mean we want to choose numbers $N$ without small prime factors. So you want to choose an irreducible polynomial, like $x^{n/2}+1$ instead. There are many other caveats for how one particularly chooses the polynomial --- most authors just ignore these, and use $x^{n/2}+1$ as a "safe" choice. If you're interested in these caveats, the word to search on is "Polynomial LWE". Starting in ~2014 there were some works that noticed polynomial LWE can be unexpectedly weak depending on the choice of polynomial, so I would only look into papers that are after this time period. Explicitly though, it is not enough to choose $f(x)$ that is irreducible and of large degree. Again, read the literature on PLWE for more details.

In practice, one should almost always do one of the following

  1. use (algebraically unstructured) LWE or LWR, of appropriate parameters
  2. use power-of-two-cyclotomic (i.e. $\mathbb{Z}[x] / (x^n+1)$ for $n= 2^k$) MLWE / MLWR of module rank $\geq 2$
  3. use middle-product LWE (it's hard to write down precisely what ring one works over --- you define a "funny product" that multiplies $a(x)b(x)$ over $\mathbb{Z}[x]$, then extracts the "middle coefficients" of this polynomial as a new polynomial).

There are some niche cases to use other rings, but you should really know what you're doing if you want to deviate from any of the above choices.

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