Paper 2023/1935

The Splitting Field of $Y^n-2$, Two-Variable NTT and Lattice-Based Cryptography

Abstract

The splitting field $F$ of the polynomial $Y^n-2$ is an extension over $\mathbb{Q}$ generated by $\zeta_n=\exp(2 \pi \sqrt{-1} /n)$ and $\sqrt[n]{2}$. In this paper, we lay the foundation for applying the Order-LWE in the integral ring $\mathcal{R}=\mathbb{Z}[\zeta_n, \sqrt[n]{2}]$ to cryptographic uses when $n$ is a power-of-two integer. We explicitly compute the Galois group $\text{Gal}\left(F/\mathbb{Q} \right)$ and the canonical embedding of $F$, based on which we study the properties of the trace pairings of the integral basis $\zeta_n^{k_0} \sqrt[n]{2}^{k_1}$. Then we discuss the security of the Order-LWE in $\mathcal{R}$, and show that it offers the same security level as the RLWE in $\mathbb{Z}[X]/\langle X^{n^2/4} + 1 \rangle$. Moreover, we design a Two-Variable Number Theoretic Transform (2NTT) algorithm for the quotient $\mathcal{R}_p=\mathcal{R}/p\mathcal{R}$, where $p$ is a prime number such that $Y^n \equiv 2 \bmod p$ has $n$ distinct solutions. Compared to the one-variable NTT in $\mathbb{Z}[X]/\langle X^{n^2/4} + 1 \rangle$, a crucial advantage of 2NTT is that it enjoys a quadratic saving of twiddle factors. Hence, we can leverage this quadratic saving to boost the performance of 2NTT in practical implementations. At last, we also look at the applications of the Order-LWE in $\mathcal{R}$. In particular, we construct a new variant of CKKS for $\mathcal{R}$ and study its new properties.

Note: Small revisions.