On the SVP for Anti-Circulant Lattices

The Shortest Vector Problem (SVP) is the computational foundation of lattice-based cryptography, and its hardness on structured lattices directly impacts the security of NIST-standardized schemes such as Kyber and Dilithium. This paper investigates the SVP on anti-circulant lattices, studies the algebraic structure underlying the polynomial ring Z[x]/(xn+1), and reveals a fundamental distinction from their circulant counterparts. Using the convex body restriction strategy, we prove that for n≤3, every SVP solution has coefficients in {0,±1} unconditionally, and for n=4,5,6, explicit coefficient bounds hold under mild conditions on the lattice parameters. For higher dimensions up to n=50, experiments with an exact SVP show that with probability ≥95%, there exists an SVP solution with coefficients in {0,±1}, and with probability ≥97%, and there exists one with coefficients in {0,±1,±2}. All experiments are computed with the exact SVP, without using any approximation algorithm as the primary oracle.