dorsal/arxiv
View SchemaPrincipal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields
| Authors | Gaohao Cui, Jianing Li, Jincheng Zhuang |
|---|---|
| Categories | |
| ArXiv ID | 2601.07511vv2 |
| URL | https://arxiv.org/abs/2601.07511 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
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}[\zeta_{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.
{
"annotation_id": "8f98a4c5-83a9-41dc-93f0-6d24596d002d",
"date_created": "2026-02-17T05:53:12.059000Z",
"date_modified": "2026-02-17T05:53:12.059000Z",
"file_hash": "2834eca0571c699db1b718e0d9ef31e706c15ecd4550bfa143fd3f17b03a4edb",
"private": false,
"record": {
"abstract": "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.\n 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}[\\zeta_{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\u0027s 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.",
"arxiv_id": "2601.07511",
"authors": [
"Gaohao Cui",
"Jianing Li",
"Jincheng Zhuang"
],
"categories": [
"cs.CR"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Principal ideal problem and ideal shortest vector over rational primes in power-of-two cyclotomic fields",
"url": "https://arxiv.org/abs/2601.07511",
"version": "v2"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "826cc845-c17d-4779-b992-63c885eb0e1d",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}