Exact Euclidean shortest vector problem is NP-hard for cyclic lattices
Euclidean SVP is NP-hard for Cyclic Lattices
Computational Complexity
Summary
Finding the shortest vector in certain special mathematical grids called cyclic lattices is very hard for computers to solve exactly. The authors showed that this problem is as hard as the toughest problems known in computer science (NP-hard), meaning no fast method is likely to exist. They also proved this for a related type of lattice used in cryptography known as NTRU-form lattices. However, this result does not claim hardness for the parameter choices typically used in practical cryptographic systems.
What this means in practice
- •For cryptographic system designers: Assess the theoretical difficulty of solving Euclidean SVP exactly on cyclic lattices relevant to some cryptographic constructions.
- •For mathematical software developers: Design algorithms for lattice problems knowing exact Euclidean SVP remains hard on cyclic structures, influencing algorithm choice and expectations.
A theory result. No direct application yet.
Authors
Daqing Wan
Abstract
We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.