NP-hardness of ideal lattice problems
Abstract
We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the ℓ2 norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.
Related
- NP-Hardness of Generalized-Turán Graph Modification Problems
- NP-hardness of additive approximation for generalized Turán problems
- Stability of ideal Nash equilibrium points in generalized multi-criteria games, interval-valued games, and existence in single-leader--multi-follower problems
- A note on the ideal lattice of a weighted Leavitt path algebra
- On Lattice Tilings by Symmetric Limited Magnitude Error Balls: Q-polynomials and Ideal Characterization
BibTeX
@misc{martin2026nphardness,
title = {{NP-hardness of ideal lattice problems}},
author = {Daniel E. Martin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15813},
eprint = {2609.15813},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15813},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - NP-hardness of ideal lattice problems
AU - Daniel E. Martin
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15813
UR - https://arxiv.org/abs/2609.15813
AB - We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the ℓ_2 norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.
ER -