Principal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912824666619904 |
|---|---|
| author | Cui, Gaohao Li, Jianing Zhuang, Jincheng |
| author_facet | Cui, Gaohao Li, Jianing Zhuang, Jincheng |
| contents | The shortest vector problem (SVP) over ideal lattices is closely related to the Ring-LWE problem, which is widely used to build post-quantum cryptosystems. Power-of-two cyclotomic fields are frequently adopted to instantiate Ring-LWE. Pan et al. (EUROCRYPT~2021) explored the SVP over ideal lattices via the decomposition fields and, in particular determined the length of the shortest vector in prime ideals lying over rational primes $p\equiv3,5\pmod{8}$ in power-of-two cyclotomic fields via explicit construction of reduced lattice bases.
In this work, we first provide a new method (different from analyzing lattice bases) to analyze the length of the shortest vector in prime ideals in $\mathbb{Z}[ζ_{2^{n+1}}]$ when $p\equiv3,5\pmod{8}$. Then we precisely characterize the length of the shortest vector in the cases of $p\equiv7,9\pmod{16}$. Furthermore, we derive a new upper bound $\sqrt[4]{2^{2n+1}p}$ for this length, which is tighter than the bound $2^n\sqrt[4]{p}$ obtained from Minkowski's theorem. Our key technique is to investigate whether a generator of a principal ideal can achieve the shortest length after embedding as a vector. If this holds for the ideal, finding the shortest vector in this ideal can be reduced to finding its shortest generator. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07511 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Principal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields Cui, Gaohao Li, Jianing Zhuang, Jincheng Cryptography and Security The shortest vector problem (SVP) over ideal lattices is closely related to the Ring-LWE problem, which is widely used to build post-quantum cryptosystems. Power-of-two cyclotomic fields are frequently adopted to instantiate Ring-LWE. Pan et al. (EUROCRYPT~2021) explored the SVP over ideal lattices via the decomposition fields and, in particular determined the length of the shortest vector in prime ideals lying over rational primes $p\equiv3,5\pmod{8}$ in power-of-two cyclotomic fields via explicit construction of reduced lattice bases. In this work, we first provide a new method (different from analyzing lattice bases) to analyze the length of the shortest vector in prime ideals in $\mathbb{Z}[ζ_{2^{n+1}}]$ when $p\equiv3,5\pmod{8}$. Then we precisely characterize the length of the shortest vector in the cases of $p\equiv7,9\pmod{16}$. Furthermore, we derive a new upper bound $\sqrt[4]{2^{2n+1}p}$ for this length, which is tighter than the bound $2^n\sqrt[4]{p}$ obtained from Minkowski's theorem. Our key technique is to investigate whether a generator of a principal ideal can achieve the shortest length after embedding as a vector. If this holds for the ideal, finding the shortest vector in this ideal can be reduced to finding its shortest generator. |
| title | Principal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2601.07511 |