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.292 n + o(n)}

Space bound

2^{0.208 n + o(n)}

Source / version date

4 Nov 2026

Comparison variant

Arbitrary width · worst case

Cost scale

2^{c n + o(n)}

Width restriction

Any positive Gaussian parameter

Output samples

One fresh sample; output batch not normalized

Distribution error

2^{-κ}; poly(κ) factors suppressed

Computation model

Randomized classical worst-case analysis

reference

HKKL26

Assumptions and source notes

Public preprint abstract claims arbitrary-width DGS with polynomial dependence on κ for error 2^{-κ}. Source-attributed bound; 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}
}