Improving verification limits for hard lattice problems in NP intersect coNP
Improving the Constant in the Aharonov--Regev Theorem
Computational Complexity
Summary
Some problems with lattices, which are grid-like mathematical structures, are hard to solve exactly but can be checked efficiently for close answers. Previous work showed that a specific verification test works up to a certain range, but with a high constant factor. The authors analyzed the test more precisely using mathematical programming and found ways to improve this constant significantly, allowing the verification method to work for smaller distances. This means that the known complexity classification for these lattice problems holds for a wider range of cases than before.
What this means in practice
- •For cryptography engineers: Use tighter verification parameters for lattice-based cryptographic constructions to improve security guarantees for certain problem reductions.
- •For complexity theory teams: Refine complexity class distinctions for lattice problems by applying improved analysis of verification protocols in cryptographic proof systems.
A theory result. No direct application yet.
Authors
Shuhong Gao
Abstract
The Aharonov-Regev proof that $\mathrm{GapCVP}_{c\sqrt n}$ lies in $\mathsf{NP}\cap \mathsf{coNP}$ uses a verifier that tests dual lattice vectors; its proof gives $c=100$. We study this verifier through a linear program in which a certificate is modeled as a sample from a probability distribution on the dual lattice. This viewpoint gives an exact analysis of the close-target tests: adding gradient and Hessian checks increases the certified close radius from $σ^{-1}/4$ to $σ^{-1}\sqrt{3/16}$, and higher derivatives cannot improve it within this framework. With Gaussian certificates for far targets, we obtain $$\mathrm{GapCVP}_{c\sqrt n},\ \mathrm{GapSVP}_{c\sqrt n}\in \mathsf{NP} \cap\mathsf{coNP}$$ for every $c>2/(π\sqrt3)\approx0.3676$. An appendix gives a finite-bit implementation of the verifier. We also show that the Gaussian certificate is not always optimal and solve the unbounded-support program exactly for targets of order two, where its value is determined by the spectral capacity of an odd dual coset.