Fast Provable Algorithms for Exact SVP and Approximate CVP on Random \(q\)-ary Lattices

What it is

Kim, Kwon, Lee and Lee (ePrint 2026/2711, approved 4 November 2026, preprint) give provable randomized algorithms for exact SVP and 5/3-approximate CVP in the Euclidean norm. They target random q-ary lattices {x in Z^n : Hx ≡ 0 mod q} with H uniform in (Z/qZ)^(m×n), for every integer q ≥ 2. Density is δ = m·log2(q)/n.

How it works

The core tool is the Howgrave-Graham–Joux representation method, adapted from prime moduli to all integer moduli. It finds short ternary solutions of random linear congruences. Two problems had to be solved to apply it.

• SVP: the shortest vector depends on the random matrix. The authors fix a family of integer candidates independently of the matrix that contains a shortest vector with high probability. For each candidate they bound the probability that it lies in the lattice while the algorithm fails to find a nonzero lattice vector at least as short. Conditioning on lattice membership lets the representation-method analysis apply, and counting candidates bounds the total failure probability.
• CVP: the target is arbitrary and may depend on the matrix. The algorithm rounds the target to an integer point and searches for a short correction that moves it into the lattice. A correction is found with constant probability for any rational target, for most matrices, and the mean of successful corrections stays small. That limits the cross term between the correction and the rounding error in the squared distance. Repeated sampling then gives a lattice point within a tighter distance bound, which permits a smaller radius for the final exact search.

Results

For δ ≤ 1 both time exponents are below the heuristic sieving exponent 0.2925. The time bounds hold on every input and execution. The δ > 1 exponents are above 0.2925, so the gain applies only to δ ≤ 1.

Guarantees

For all but a 2^(-Ω(n^(2/3))) fraction of input matrices, each algorithm succeeds with probability 1 − 2^(-Ω(n)) over its internal randomness. For CVP this holds simultaneously for every target.

Caveats

• The guarantee is over random matrices. The abstract does not address structured lattices or any specific scheme or parameter set.
• The bounds are asymptotic with o(n) terms in the exponent. The page gives no implementation or concrete runtimes.
• CVP is solved only to approximation factor 5/3, not exactly.
• The page does not discuss consequences for deployed cryptography.