Classical Worst-Case Hardness Reduction for LWE

Classical Worst-Case Hardness Reduction for LWE

Definitions and mathematical statement

An LWE sample has uniform $a\in({\mathbb{Z}}/q{\mathbb{Z}})^n$ and noisy inner product $b=\langle a,s\rangle+e\pmod q$ for a fixed secret $s$, with the Gaussian error and rounding convention of Regev's reduction. For a lattice $\Lambda$, $\lambda_i$ is its $i$th successive minimum. GapSVP distinguishes a short-vector threshold from a factor-$\gamma$ larger threshold; SIVP asks for $n$ independent vectors of length at most $\gamma\lambda_n(\Lambda)$. The target is a classical worst-case-to-LWE reduction covering both problems with the same parameter range and approximation factors as the cited quantum reduction, polynomial modulus, and no dimension loss. The exact admissibility inequalities are inherited from that theorem, not replaced by arbitrary polynomial factors. A reduction treating only GapSVP does not fully meet this combined target.

Formulation and concept references: [S1].

Short English statement

Can a classical reduction match Regev's quantum LWE hardness reduction for both shortest-vector decision and independent-vector search without worsening its parameters or lattice dimension?

Research attempt

GPT-6 Astra Ultra, 27 September 2026. Status: UNRESOLVED.

The first missing step is an efficient classical replacement for the discrete-Gaussian sampling step in the quantum reduction, with its parameter promises intact. The familiar headline, an approximation factor $\widetilde O(n/\alpha)$ when the Gaussian noise parameter satisfies $\alpha q>2\sqrt n$, is not a license to alter the modulus, noise discretization, dimension, or either lattice problem. Regev's original paper [E1] supplies the reduction and the sampling mechanism being compared; its intermediate continuous-noise formulations and its search-to-decision statements must be read with their individual hypotheses. The argument below isolates a genuine classical Gaussian contraction and proves why its most direct implementation can cost exponentially many samples. It does not prove that every classical replacement must fail.

An exact contraction identity

Write \[ D_{\Lambda,s}(v)=\frac{\exp(-\pi\|v\|^2/s^2)} {\sum_{w\in\Lambda}\exp(-\pi\|w\|^2/s^2)} \qquad(v\in\Lambda). \] Assume for this calculation that independent exact samples $X,Y$ from this distribution are already available. Condition on the event $X\equiv Y\pmod{2\Lambda}$, and define \[ Z=(X+Y)/2,\qquad W=(X-Y)/2. \] Both outputs belong to $\Lambda$. Conversely, every pair $(z,w)\in\Lambda^2$ gives a unique conditioned pair $(x,y)=(z+w,z-w)$. The parallelogram identity gives \[ \|z+w\|^2+\|z-w\|^2=2\|z\|^2+2\|w\|^2. \] Thus the conditional joint distribution of $(Z,W)$ factors, and \[ Z,W\ \hbox{are independent samples from }D_{\Lambda,s/\sqrt2}. \tag{264.1} \] There is no approximation or hidden geometric assumption in this identity. Iteration would reduce the Gaussian width, suggesting a purely classical substitute for a width-reduction procedure.

The difficulty is the cost of conditioning. If $p_c$ is the probability of the coset $c\in\Lambda/2\Lambda$, then acceptance has probability \[ \Pr(X\equiv Y\bmod 2\Lambda)=\sum_c p_c^2. \tag{264.2} \] There are $2^n$ cosets in rank $n$. When their masses are close to uniform, this is close to $2^{-n}$, not inverse polynomial. Formula $264.1$ is therefore not yet an efficient sampling algorithm.

An elementary exponential-cost example

This obstruction can be demonstrated without estimating a smoothing parameter. Take $\Lambda=\mathbb Z^n$ and $s=2$. Coordinates are independent. Let $p$ be the probability that a coordinate is even under $D_{\mathbb Z,2}$, and put \[ H=1+2\sum_{j\ge1}e^{-\pi j^2/4},\qquad E=1+2\sum_{j\ge1}e^{-\pi j^2},\qquad p=E/H. \] Successive terms in the first positive sum have ratio at most $e^{-3\pi/4}$, while the corresponding ratio in the second sum is at most $e^{-3\pi}$. Consequently, \[ H\le1+\frac{2e^{-\pi/4}}{1-e^{-3\pi/4}}<3,\qquad E\le1+\frac{2e^{-\pi}}{1-e^{-3\pi}}<1.1. \] The elementary bounds $3<\pi<4$ suffice for these inequalities. Moreover, $H\ge1+2e^{-\pi/4}>1+2/e$, so $1/3<p<2/3$. Two independent coordinates have the same parity with probability $p^2+(1-p)^2\le5/9$. Independence across coordinates now yields \[ \Pr(X\equiv Y\bmod2\mathbb Z^n)\le(5/9)^n. \tag{264.3} \] Independent-pair rejection sampling therefore needs at least $(9/5)^n$ pairs on average for one accepted pair. Pooling samples and looking for collisions changes the accounting, but does not by itself establish polynomial complexity; there remain exponentially many possible parity classes.

The lattice in this countertest is intentionally easy: one can sample its coordinates directly at a smaller width. Thus $264.3$ refutes the claimed efficiency of this particular conditioning implementation, not efficient classical Gaussian sampling on $\mathbb Z^n$, and certainly not the desired reduction in general. Approximate input samplers would also require a separate bound on the effect of conditioning; dividing by an exponentially small event probability can magnify errors.

Why a basis-coordinate Gaussian is a different object

Another tempting replacement is to draw short integer coefficients independently and multiply by the supplied lattice basis. It produces lattice points efficiently, but generally the wrong distribution. Consider two bases for the same lattice $\mathbb Z^2$: \[ I,\qquad B=\begin{pmatrix}1&M\\0&1\end{pmatrix}. \] If the coefficient vector $(U,V)$ has independent centered coordinates of variance $\sigma^2$, then \[ \mathbb E\|(U,V)\|^2=2\sigma^2,\qquad \mathbb E\|B(U,V)\|^2=(M^2+2)\sigma^2. \tag{264.4} \] The second sampler depends strongly on the presentation, even though the lattice and the desired spherical discrete Gaussian have not changed. The integer $M$ is encoded in only $O(\log M)$ bits.

This example does not rule out basis reduction or more sophisticated samplers. It shows that coordinate independence in an arbitrary input basis is not a proof of spherical discrete-Gaussian sampling at the required width. A repair has to establish a quantitative distributional guarantee and include its dependence on the basis, dimension, and allowed error. Replacing spherical noise by a convenient ellipsoidal distribution would change the target oracle unless a valid transformation preserves every promise.

Both lattice tasks remain essential

The two worst-case tasks cannot be identified merely because both mention short vectors. For \[ \Lambda_T=\operatorname{diag}(1,T,\ldots,T)\mathbb Z^n,\qquad T\ge1, \] one has $\lambda_1(\Lambda_T)=1$ and $\lambda_n(\Lambda_T)=T$. Indeed, the first coordinate axis supplies a unit vector, while any collection of $n$ independent vectors must include a vector with a nonzero coordinate outside that axis, of length at least $T$. The displayed diagonal basis attains this bound.

Finding or deciding the existence of the first short vector therefore does not itself return the $n$ independent vectors required by SIVP. This observation is not a separation theorem between approximation problems: reductions might perform many carefully chosen queries. It does identify the missing work in a proposal that establishes only a shortest-vector decision reduction and declares the combined statement proved.

Similarly, noiseless modular linear algebra is an excellent sanity check but does not meet the LWE promise. Setting the error to zero, silently changing how continuous error is rounded, increasing $q$ beyond the stipulated range, or moving to a larger lattice dimension may make an intermediate algorithm simpler while leaving the stated problem unanswered. Exact admissibility inequalities matter because the reduction must apply to an oracle over the original specified parameter range.

Verification and remaining gap

The saved checks verify the change-of-variables identity algebraically in small dimensions, the parity-collision calculation by controlled Gaussian-tail bounds, and the covariance calculation for the sheared basis. These are checks of the stated partial arguments; no finite experiment can validate a worst-case reduction in unbounded dimension.

A successful continuation needs a classical oracle-assisted procedure whose output distribution, width, approximation error, sample count, and running time are all proved sufficient for the original reduction. It must then carry that procedure through both the GapSVP and SIVP consequences, checking the modulus and noise conventions at each interface. The exact contraction $264.1$ supplies one piece of algebra but currently lacks the necessary efficiency, while $264.4$ blocks a simple basis-coordinate substitute. Neither observation establishes an impossibility result.

UNRESOLVED. The useful partial result is an exact Gaussian contraction with an explicit exponential rejection-cost countertest. The required parameter-preserving classical reduction for both lattice problems has not been constructed.

Sources

• S1 C. Peikert, 'A Decade of Lattice Cryptography', in Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, ACM Books, 2021, pp. 283-357; full version at web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf. http://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf. Formulation source.
• E1 O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM 56$6$, Article 34 $2009$, author manuscript, especially Theorem 1.1 and the discrete-Gaussian sampling reduction. https://cims.nyu.edu/~regev/papers/qcrypto.pdf. Primary source for the quantum reduction and its parameter conventions; not a classical resolution.