Learning with Quantization and Worst Case Lattice Problems

What it is

Paper 2026/2613 (ePrint, preprint, received 23 October 2026) by Ziwei Hong and Zhongqiu Fang studies worst case hardness of learning with quantization (LWQ) with public dither. It is motivated by the MAMBA proposals. The result is a quantum reduction from worst case lattice problems on arbitrary n-dimensional lattices to LWQ, with explicit approximation factors.

How it works

The authors use the randomized polar lattice quantizer of Lyu et al. to build explicit LWQ families with polynomial power-of-two moduli. The dither function can be any efficiently computable function, and the seed distribution any efficiently samplable one. The matrix is uniform and independent of both the secret and the seed. Conditional on the public seed, the comparison output is uniform in the prescribed dither coset and independent of the matrix.

Two families give two reductions:

The decision family needs stronger parameter conditions than the search family. The paper's abstract does not state what those conditions are.

Preconditions

The guarantees apply only to the paper's constructed families, with polynomial power-of-two moduli and a uniform secret. They are quantum reductions, so a classical attacker breaking LWQ does not by itself give a classical lattice algorithm.

Caveats

The paper also examines LWE with interval uniform errors, as used in MAMBA Frost. It finds obstacles from deterministic quantization boundaries and gives a local perturbation bound that depends explicitly on the number of observations. It states that this does not give a complete worst case reduction for these errors. It also does not show hardness at the concrete MAMBA parameters. The abstract gives no concrete parameter sets or security estimates, so it cannot be used to size a deployment.