Source-linked AI summary
On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
Oded Regev
TL;DR
The paper asks whether a higher-modulus noisy linear-equation problem is hard and connects that question to worst-case lattice problems and random-code decoding. It gives a quantum reduction from LWE to GAPSVP and SIVP, then uses LWE to construct a classical public-key cryptosystem. The reduction remains non-classical, while the cryptosystem improves stated efficiency bounds over prior constructions.
Problem
The paper addresses the apparent difficulty of learning noisy linear equations and the related hardness of decoding random linear codes.
Method
The paper reduces LWE with a discrete-Gaussian-shaped error distribution to worst-case lattice problems using an iterative proof with one quantum step, then builds a classical public-key cryptosystem from LWE.
Results
LWE hardness implies quantum worst-case hardness for GAPSVP and SIVP, while the cryptosystem uses ˜O(n^2) public-key size and ˜O(n) message expansion.
Takeaways & Limitations
The work connects noisy learning, random-code decoding, and lattice hardness, and provides a more efficient classical cryptosystem under a quantum hardness basis.
Takeaways & Limitations
The main reduction is quantum, and making it classical remains open; removing quantum computation would impose additional construction and parameter costs.
Abstract
from arXiv · showhide
Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., non-quantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size $\tilde{O}(n^2)$ and encrypting a message increases its size by a factor of $\tilde{O}(n)$ (in previous cryptosystems these values are $\tilde{O}(n^4)$ and $\tilde{O}(n^2)$, respectively). In fact, under the assumption that all parties share a random bit string of length $\tilde{O}(n^2)$, the size of the public key can be reduced to $\tilde{O}(n)$.
1 Introduction
The paper introduces LWE as a higher-modulus extension of learning parity with error and reduces it to worst-case lattice problems through a quantum reduction. It also connects LWE to random-code decoding and builds a classical, more efficient public-key cryptosystem, while leaving classical dequantization open.
- Learning with error: LWE extends learning from parity with error to higher moduli, with independently sampled errors and uniformly random inputs.Under a reasonable condition on the error distribution, the best stated algorithms require 2^O(n) equations and time.
- Main reduction: An efficient solver for LWE with the specified distribution yields a quantum algorithm approximating GAPSVP and SIVP within ˜O(n/α) in the worst case.The reduction applies when αp > 2√n.
- Cryptosystem: The paper presents a classical public-key cryptosystem whose security follows from LWE and therefore from worst-case quantum hardness of GAPSVP and SIVP.Its construction publishes noisy equations, combines them during encryption, and relies on computational indistinguishability from uniformly random right-hand sides.
- Cryptosystem: ˜O(n^2) public-key size and ˜O(n) message expansion improve on previous values of ˜O(n^4) and ˜O(n^2), respectively.With shared trusted randomness of length ˜O(n^2), the public key can be reduced to ˜O(n).
- Open questions: The reduction’s only quantum step prevents the paper from establishing hardness from classical lattice assumptions, making dequantization a central open question.Removing quantum computation would also eliminate the iterative construction and impose stronger modulus or hardness requirements in the stated alternatives.
2 Preliminaries
The preliminaries establish notation for modular arithmetic, lattices, Gaussian distributions, learning with errors, and statistical distance. They also record sampling, approximation, and error conventions used throughout the paper.
- Zp denotes the cyclic group {0, 1, ..., p − 1} with addition modulo p, while T denotes R/Z.
- Statistical distance obeys the triangle inequality and cannot increase under randomized functions, bounding changes in algorithm acceptance probabilities.
- The paper assumes polynomial-time exact Gaussian sampling conceptually, supports sufficiently precise finite approximations, and generally allows exponentially small error.
- A discrete Gaussian DA,s assigns probability proportional to ρs(x) over a countable support A, including lattices.
- Learning with errors samples (a, ⟨a,s⟩ + e) modulo p, with uniform a and error e drawn from χ; the goal is recovering s efficiently.
- The continuous analogue samples (a, ⟨a,s⟩/p + e) modulo 1, with e drawn from a density φ on T.
3 Main Theorem
The main theorem reduces solving a discrete-Gaussian LWE problem to quantum algorithms for discrete Gaussian sampling, which then yield worst-case lattice algorithms. The construction’s only quantum component is the conversion from closest-vector access to new Gaussian samples.
- Main theorem: The main theorem reduces LWE with error distribution Ψ̄α to efficient quantum discrete Gaussian sampling on lattices.The reduction assumes an oracle solving LWEp,Ψ̄α and produces samples from a discrete Gaussian at an appropriate parameter.
- Main theorem: Bootstrapping efficiently produces an initial sample close to the target discrete Gaussian when r > 2^2nλn(L).The output distribution is within statistical distance 2^-Ω(n) of DL,r.
- Main theorem: The iterative step uses LWE to solve a modular closest-vector problem and then applies a quantum procedure to transform samples from DL,r into samples from DL,r√(αp/√n).The same input samples can support any polynomial number of output samples because the output randomness comes from the algorithm and quantum measurements.
- Main theorem: The reduction is not fully classical: converting closest-vector access into new Gaussian samples is identified as the only quantum component.The paper explicitly isolates this quantum step in the second part of the iterative step.
- From samples to CVP: The first part recovers closest-vector coefficients modulo p by recursively dividing points whose lattice distance shrinks by factors of p.After n steps, approximate closest-vector solving recovers the final coefficient, which is then used to reconstruct earlier coefficients.
- Standard lattice problems: The resulting discrete Gaussian sampler gives quantum algorithms for SIVP and GAPSVP through standard reductions.The SIVP reduction samples enough vectors to obtain short linearly independent vectors, while the GAPSVP route proceeds through GAPCVP′.
4 Variants of the LWE problem
This section shows that several decision and search variants of LWE are equivalent through elementary reductions. The reductions convert average-case distinguishers into all-secret distinguishers, decision procedures into search algorithms, and continuous errors into discrete ones.
- Average-case to worst-case: Average-case distinguishability for a non-negligible fraction of secrets can be transformed into distinguishing LWE from uniform for every secret.Random shifts preserve the uniform distribution while translating the hidden secret.
- Decision to search: A distinguisher that separates As,χ from uniform with exponentially small error can be converted into an algorithm recovering the secret s.The reduction tests candidate values for a coordinate by applying a randomized transformation that preserves LWE only for the correct candidate.
- Discrete to continuous: Solving LWE with a discretized error distribution is sufficient to solve LWE with the corresponding continuous distribution.The reduction discretizes the second component of each continuous sample and invokes the discrete-error solver.
- Combined equivalences: A distinguisher for a non-negligible fraction of secrets under a discretized continuous error distribution therefore yields an efficient solver for the original continuous-error LWE problem.This follows by combining the average-case-to-worst-case, decision-to-search, and discrete-to-continuous reductions.
5 Public Key Cryptosystem
The cryptosystem uses noisy linear equations over Z_p, with subset-sum encryption and threshold decryption. Its correctness follows from concentrated accumulated errors, while semantic security reduces to distinguishing noisy equations from uniform ones and then to worst-case lattice problems.
- Construction: The system chooses a private vector s, publishes noisy equations (a_i, b_i), and uses their subset sums to encrypt bits.Public-key entries use uniform a_i and independent errors from χ; encryption selects a random subset of [m].
- Construction: Decryption outputs 0 when b − ⟨a, s⟩ is closer modulo p to 0 than to ⌊p/2⌋, and outputs 1 otherwise.This threshold rule is applied to the decrypted pair modulo p.
- Efficiency: With the stated parameterization, the public key has size ˜O(n^2), while encryption increases message size by ˜O(n).Sharing the random vectors a_1, ..., a_m can reduce public-key size to ˜O(n).
- Correctness: For any δ > 0, if every accumulated-error distribution χ⋆k satisfies the lemma’s condition, decryption error is at most δ.The correctness lemma guarantees recovery of either encrypted bit with probability at least 1 − δ.
- Security: Semantic security means that distinguishing encryptions of 0 and 1 would yield a distinguisher between A_s,χ and the uniform distribution for a non-negligible fraction of secrets.The reduction first transforms an encryption distinguisher and then uses averaging to identify many suitable secret vectors.
- Security: That distinguishing capability would imply efficient quantum algorithms for SIVP and GAPSVP with approximation factor ˜O(n/α).The security chain proceeds through LWE and the paper’s lattice reductions.