Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference Tree

Minki Hhan

ePrint 2026/1859

Time bound

2^{n/2 + o(n)}

Space bound

2^{0.5 n + o(n)}

Source / version date

2 Sept 2026

Comparison variant

Classical · worst case

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂

Success guarantee

High probability

Computation model

Classical randomized; polynomial factors suppressed

reference

Hhan26b

Assumptions and source notes

Preprint claim: exact worst-case SVP in time and space 2^{n/2+o(n)}. Its separate distance-guarantee CVP result is not treated as unrestricted exact CVP here. Source checked; proof not independently audited.

Primary source ↗

@misc{paper-0f3a0f011219,
  author = {Minki Hhan},
  title = {{Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference Tree}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.02764},
  cr_date = {2026-09-02},
  cr_status = {preprint},
  cr_author_ids = {minki-hhan},
  howpublished = {arXiv:2609.02764; also Cryptology ePrint Archive, Paper 2026/1859}
}