Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 22 min ago
Peer-reviewedCC BY 4.0Axioms

On the SVP for Anti-Circulant Lattices

  • Gengran Hu1,2
  1. 1School of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, China
  2. 2Zhejiang Provincial Key Laboratory of Sensitive Data Security and Confidentiality Governance, Hangzhou Dianzi University, Hangzhou 310018, China
Open at sourceDOICite

Abstract

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.

Related

  1. Integral homology lattices of matching and circulant complexes
    Qihang Wang, Weiye Li
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  2. A study on Type-2 isomorphic circulant graphs. Part 3: 384 pairs of Type-2 isomorphic circulant graphs C32(R)
    Vilfred Kamalappan
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A study on Type-2 isomorphic circulant graphs. Part 4: 960 triples of Type-2 isomorphic circulant graphs C54(R)
    Vilfred Kamalappan
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. A Study on Type-2 Isomorphic Circulant Graphs: Part 7: C432(R), C6750(S) - each has 2 types of Type-2 isomorphic circulant graphs
    Vilfred Kamalappan
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. v-numbers of powers of edge ideals of cubic circulant graphs
    Guangjun Zhu, Jiaxin Li, Yulin Hu
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@article{hu2026anticirculant,
  title = {{On the SVP for Anti-Circulant Lattices}},
  author = {Gengran Hu},
  journal = {Axioms},
  year = {2026},
  month = oct,
  doi = {10.3390/axioms15110802},
  url = {https://www.mdpi.com/2075-1680/15/11/802},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - On the SVP for Anti-Circulant Lattices
AU  - Gengran Hu
PY  - 2026
DA  - 2026/10/28
JO  - Axioms
DO  - 10.3390/axioms15110802
UR  - https://www.mdpi.com/2075-1680/15/11/802
AB  - 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.
SN  - 2075-1680
ER  -