Welcome to the resource topic for 2023/1935
Title:
The Splitting Field of Y^n-2, Two-Variable NTT and Lattice-Based Cryptography
Authors: Wenzhe Yang
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}. When n (\geq 8) is a power-of-two integer, the degree of F over \mathbb{Q} is n^2/4. In this paper, we lay the foundation for applying the Order-LWE in \mathcal{R}=\mathbb{Z}[\zeta_n, \sqrt[n]{2}] to cryptographic uses. More specifically, We will compute the Galois group \text{Gal}\left(F/\mathbb{Q} \right) and the canonical embedding of F into \mathbb{C}^{n^2/4}. Then we study the trace pairings of the integral basis \zeta_n^{k_0} \sqrt[n]{2}^{k_1} and obtain its dual explicitly, which will be crucial when we study the error distributions on the ideal lattices associated with \mathcal{R}.
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, a crucial advantage of 2NTT is that it enjoys a quadratic saving of twiddle factors. Hence, it is very interesting to see how to leverage this quadratic saving to boost the performance of 2NTT in practical implementations.
ePrint: https://eprint.iacr.org/2023/1935
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .