Superlattice methods for the shortest vector problem and discrete Gaussian sampling

Minki Hhan · Jiseung Kim · Sunyeop Kim · Thijs Laarhoven

ePrint 2026/2761

Time bound

2^{0.409 n + o(n)}

Space bound

2^{0.259 n + o(n)}

Source / version date

4 Nov 2026

Comparison variant

Constant approximation · large-factor limit

Cost scale

2^{(c + ε) n}, any fixed ε > 0

Norm

Euclidean ℓ₂

Success guarantee

High probability

Computation model

Classical randomized; polynomial factors suppressed

reference

HKKL26

Approximation guarantee

Exact output (μ = 1), hence meets every relaxed constant-factor guarantee

Assumptions and source notes

The exact-SVP theorem immediately supplies this approximation guarantee without changing time or space. This is a transferred guarantee, not another algorithm or a separate new result. Claim in the 4 November 2026 preprint abstract: optimized worst-case SVP time 0.409 and space 0.259. Dense superlattices, random shifts, and midpoint-shell tests. Source checked; proof not independently audited.

Primary source ↗

@misc{paper-c70730f20075,
  author = {Minki Hhan and Jiseung Kim and Sunyeop Kim and Thijs Laarhoven},
  title = {{Superlattice methods for the shortest vector problem and discrete Gaussian sampling}},
  year = {2026},
  url = {https://eprint.iacr.org/2026/2761},
  cr_date = {2026-11-04},
  cr_status = {preprint},
  cr_author_ids = {minki-hhan; jiseung-kim; sunyeop-kim; thijs-laarhoven},
  howpublished = {Cryptology ePrint Archive, Paper 2026/2761}
}