{
  "abstract": "To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on $n$-dimensional Haar-random lattices. Writing $n^{cn+o(n)}$ for the tree size at the shortest vector radius, we investigate the asymptotic scaling of $c$, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish $c=1/(2e)\\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent $c$ over all bases of a random lattice satisfies: \\begin{align} 0.1464 \\approx \\frac{2-\\sqrt{2}}{4}\\leq c<0.1474. \\end{align} For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent $c \\geq 1/8$, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most $n^{n/8 + o(n)}$. Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with $c \\leq 1/(4\\sqrt{e}) \\approx 0.1516$. Recursively splitting each half lowers the upper bound below $0.1474$, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time $n^{0.0892 n + o(n)}$ for arbitrary targets.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.15265",
  "author_total": 1,
  "authors": [
    {
      "name": "Thijs Laarhoven"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/7xq8bpqjrswg7.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.15265",
  "fulltext_url": null,
  "id": "7xq8bpqjrswg7",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.15265",
  "language": null,
  "licence": "CC-BY-SA-4.0",
  "licence_label": "CC BY-SA 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by-sa/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CR"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "arxiv",
      "math.MG"
    ],
    [
      "openalex",
      "1702|Cryptography and Data Security"
    ]
  ],
  "openalex": "W7221754434",
  "pdf_url": "https://arxiv.org/pdf/2610.15265",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-11",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/7xq8bpqjrswg7.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:29:15Z",
      "native_id": "2610.15265",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.15265"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.MG",
      "subfield": "geometry-topology"
    }
  ],
  "title": "Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices",
  "title_text": "Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices",
  "type": "preprint",
  "updated_at": "2026-10-30T12:29:15Z",
  "url": "https://research.draconitic.com/paper/7xq8bpqjrswg7",
  "venue": "arXiv",
  "versions": []
}