{"id":"arxiv/2609.15813","url":"https://arxiv.org/abs/2609.15813","tags":["cs.CC","math.NT"],"score":0,"title":"NP-hardness of ideal lattice problems","domain":"cs.CC","source":"arxiv","authors":["Daniel E. Martin"],"reviews":0,"subject":"cs.CC","summary":"We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\\ell_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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}