Source-linked AI summary
Classical Hardness of Learning with Errors
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé
TL;DR
The paper addresses whether LWE remains classically hard with polynomial modulus, where earlier evidence relied on quantum or non-standard lattice reductions. It develops modulus-reduction techniques inspired by recent cryptography and proves classical hardness from standard worst-case lattice problems, while identifying a dimension–modulus tradeoff and a quadratic dimension loss.
Problem
Before this work, polynomial-modulus LWE was known to yield only quantum lattice algorithms or classical algorithms for a non-standard lattice problem.
Method
The paper uses modulus reduction, a hybrid argument, and an extended-LWE hardness reduction inspired by fully homomorphic encryption constructions.
Results
The first classical reduction establishes standard worst-case lattice hardness for polynomial-modulus LWE and shows that hardness is essentially governed by n log2 q.
Takeaways & Limitations
The result supplies classical worst-case support for known polynomial-modulus LWE applications and clarifies how dimension and modulus trade off.
Takeaways & Limitations
Theorem 1.1 inherits a quadratic dimension loss and bases hardness only on GapSVP-type problems rather than SIVP.
Abstract
from arXiv · showhide
We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.
1 Introduction
The paper gives the first classical hardness reduction for polynomial-modulus LWE to standard worst-case lattice problems, resolving a central gap left by prior quantum or non-standard reductions. Its modulus-reduction techniques also reveal a dimension–modulus tradeoff, while incurring a quadratic dimension loss and relying on GapSVP-type hardness.
- Motivation: Prior to this work, polynomial-modulus LWE was known to imply only quantum lattice algorithms or classical algorithms for a non-standard lattice problem.This left persistent concern about the hardness underlying LWE-based cryptographic applications.
- Main result: The paper provides the first classical hardness reduction from polynomial-modulus LWE to worst-case instances of standard lattice problems.Theorem 1.1 states that solving n-dimensional LWE with polynomial modulus yields an equally efficient solution to a worst-case lattice problem in dimension √.
- Techniques: The core technique is modulus reduction from LWE with large modulus q and dimension n to modulus p = poly(n) and dimension n log2 q.The proof combines a hybrid argument with a new hardness reduction for extended-LWE, which exposes selected inner products of the error vector.
- Broader perspective: The generalized reduction exposes a tradeoff in which LWE hardness is governed essentially by n log2 q rather than dimension or modulus separately.It reduces dimension n and modulus p to dimension n/k and modulus pk, preserving the relevant quantity.
- Broader perspective: n-dimensional LWE with modulus 2n is essentially as hard as n2-dimensional LWE with polynomial modulus, revealing a quadratic loss in the classical reduction.The paper contrasts this with the quantum reduction, which does not incur that loss.
- Broader perspective: The reductions also establish hardness for arbitrary huge moduli, including primes, whereas previous results required smooth moduli.The classical theorem inherits a limitation: its hardness is based on GapSVP, BDD, and uSVP rather than problems such as SIVP.
2 Preliminaries
The preliminaries define the probability, lattice, Gaussian, and LWE objects used throughout, then state reductions to normal-form and decision LWE. They also establish sampling and statistical-distance tools supporting these transformations.
- Statistical tools: The leftover hash lemma gives near-uniformity of (H, Hz) versus (H, u) when n ≥ k log2 q + 2 log2(1/ε).The resulting statistical distance is at most ε.
- Reductions: A polynomial-time reduction solves one problem using an oracle for another, usually by transforming the input before oracle access.The paper calls these transformation reductions and notes one exception among its reductions.
- Lattices and Gaussians: The section defines lattices, dual lattices, shortest-vector gaps, Gaussian distributions, and the smoothing parameter.These notions support later Gaussian sampling and lattice-based transformations.
- Lattices and Gaussians: Exact discrete-Gaussian sampling is available efficiently for sufficiently broad parameters, and the paper modifies the sampler to support slightly narrower Gaussians.The exact sampler is mainly included for cleaner proofs and a minor parameter improvement.
- Learning with Errors: LWE distinguishes noisy linear samples from uniform samples over a torus.Samples use a uniformly random a and an error term, with the decision problem formalized over distributions indexed by the secret.
- Learning with Errors: Normal-form reduction changes the secret distribution to a discretized Gaussian, while search-to-decision reduction yields decision LWE hardness for arbitrary moduli.The normal-form transformation incurs a sample loss and advantage degradation; the decision reduction extends beyond smooth moduli with a small noise deterioration.
3 Modulus-Dimension Switching
This section constructs efficient reductions that lower the modulus or trade dimension for modulus while controlling statistical distance, noise growth, and advantage loss. These transformations extend LWE hardness across moduli and expose a modulus-dimension tradeoff.
- Modulus reduction: A bounded-secret reduction maps LWEn,m,q,≤α(D) to LWEn,m,q′,≤β(D), losing at most δ + 14εm in advantage.The secret distribution is (B, δ)-bounded, and the reduction preserves dimension while changing the modulus and noise parameter.
- Modulus reduction: Corollary 3.3 extends hardness from a modulus q to a power-of-2 modulus q′, with sample loss 16n + 4 ln ln q and advantage at least (ζ − δ)/4.The source modulus lies in [q′, 2q′), and the resulting error is bounded by a parameter β.
- Dimension-modulus switching: For normal-form secrets, the reduction increases the error rate by about a factor involving √k while trading dimension against modulus.The normal-form distribution is used to control the transformed secret's norm.
- Dimension-modulus switching: Dimension-modulus switching maps dimension n to n/k while replacing q by q^k, using G = I_n/k ⊗ (1, q, q^2, . . . , q^{k−1})^T.The reduction preserves n log q = n′ log q′ and loses at most δ + 14εm in advantage.
- Reduction analysis: The reduction maps uniform inputs within statistical distance 4ε and LWE inputs within 10ε of a lower-modulus LWE distribution.For a secret s with norm at most B, the new error satisfies (α′)^2 = α^2 + r^2(∥s∥^2 + B^2) ≤ α^2 + 2(rB)^2.
- Construction: The switching construction samples a′ so that G^T a′ approximates a modulo Z^n, with discrete-Gaussian approximation error.This encoding makes inner products with the original short secret nearly equivalent to inner products with the transformed secret Gs.
4 Hardness of LWE with Binary Secret
The section establishes reductions from general LWE to binary-secret LWE through first-is-errorless and extended-LWE variants, yielding hardness consequences while tracking advantage and dimension losses.
- Theorem 4.1: Theorem 4.1 gives three efficient transformation reductions from LWE to binary-secret LWE under explicit dimension, modulus, error, and advantage conditions.The reductions preserve hardness up to the stated parameter constraints and advantage losses.
- Consequences: Combining the theorem with modulus switching and prior classical hardness results yields the paper’s formal binary-secret LWE consequence, while the construction tracks additional advantage losses and prime-factor terms.The modulus q′ can be reduced substantially, and the theorem’s proof combines several reductions whose losses are explicitly bounded.
- Proof strategy: The proof proceeds through first-is-errorless LWE, extended LWE with leaked error information, and finally LWE with a binary secret.The first step is relatively standard; the latter two are identified as the section’s main contributions.
- First-is-errorless LWE: First-is-errorless LWE remains hard via an efficient reduction from lower-dimensional LWE, with advantage loss bounded by a sum over prime factors of q.For prime q, the loss is at most q^-n.
- Extended LWE: For a set Z of quality ξ, Lemma 4.7 reduces first-is-errorless LWE to extended LWE with error parameter (α^2ξ^2+r^2)^1/2 and bounded advantage loss.The construction uses unimodular matrices whose columns are orthogonal to chosen z values; {0,1}^m has quality 2.
- Reduction to binary secret: Extended LWE can be reduced to a binary-secret instance through an efficient transformation that loses a factor of t in advantage, followed by three reductions to binLWE.The binary-secret hardness statement is formalized through Lemma 4.9 and the associated advantage accounting.
5 Exact Gaussian Sampler
The section constructs an exact discrete Gaussian sampler by combining a one-dimensional rejection sampler with recursive sampling on arbitrary lattices. It establishes the sampler’s correctness, termination bounds, and efficient probability computation.
- 5.1 The one-dimensional case: The one-dimensional sampler uses rejection sampling from a continuous normal distribution to obtain an exact sample on any coset Z+c.Scaling reduces the task to sampling from DZ+c,r with c ∈ [0, 1).
- 5.1 The one-dimensional case: The procedure partitions the continuous normal source into two tails, rounds each sample to a neighboring lattice point, and accepts with probability ρr(y)/ρr(x).The two branches handle x ≥ c and x ≤ c−1, respectively.
- 5.1 The one-dimensional case: Conditioned on acceptance, the output has support Z+c and probability mass proportional to ρr, so it is distributed as the desired discrete Gaussian.The same argument identifies the output probabilities for c, c−1, and the remaining lattice points.
- 5.1 The one-dimensional case: At least 1/2 termination probability per iteration gives a tail bound of 2^−t and expected iteration count at most 2.This bound applies to the one-dimensional procedure.
- 5.2 The general case: The recursive general-lattice sampler applies SampleD and an additional rejection step to produce an exact sample from DΛ+c,r.The output remains in Λ+c, and the relevant probabilities can be computed efficiently using fast-decaying sums or Poisson summation.
- 5.2 The general case: Conditioned on output, the recursive sampler has the desired distribution, terminates with probability at least e^−2 per iteration, and has expected iteration count at most e^2.The iteration-count tail is at most (1−e^−2)^t.
- 5.2 The general case: The rejection probabilities are efficiently computable to any desired t bits of accuracy in polynomial time.For r < 1, direct summation decays quickly; for r ≥ 1, the Poisson summation formula yields a rapidly decaying representation.