Learning With Errors
Recover or distinguish a noisy linear system.
Dual lattice · parameterized models
Decision-LWE with Gaussian errors, with q(n), Gaussian width and sample availability specified per entry
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Lattice-based CryptographyPost-Quantum Cryptography 2009SourceBibTeX / detailsdual historical model | 7 Nov 2008 | Treduce(m, δ); m ≈ sqrt(n log₂(q) / log₂(δ)) | Depends on the selected lattice-reduction algorithm. | PublishedSource checked |
| — | On the concrete hardness of Learning with ErrorsJournal of Mathematical Cryptology 2015SourceBibTeX / detailsdual historical cost model oracle samples | 2 Oct 2015 | O(ε⁻² · TBKZ(m,δ₀)); log₂δ₀=[log₂(f(ε)/α)]²/(4nlog₂q), f(ε)=√(ln(1/ε)/π) | Depends on the chosen SVP oracle inside BKZ. | PublishedSource checked |
| — | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEALEurocrypt 2017SourceBibTeX / detailsdual amortization heuristic fixed samples | 18 May 2017 | TBKZ(m,β) + M·[Trerandomize(m) + TBKZ(m,β′)], with β′≤β | Reduced basis plus M short dual vectors, if stored. | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Decision-LWE with Gaussian errors, with q(n), Gaussian width and sample availability specified per entry
- Computation
- Classical
- Rigor
- Heuristic / model-dependent
- Instances
- Uniform random LWE samples; explicit parameter contract
- Cost scale
- Parameter-dependent time and space expressions
- Parameter
- n, q, error width, secret distribution, sample budget and attack parameters
- Description
- Historical LWE bounds and cost models with parameters retained. Entries without a common fixed asymptotic scale are listed without a numerical rank.
- Comparison rules
- Specify q(n), error distribution and width convention, secret distribution, available samples, search versus decision objective, success criterion and lattice/algebraic assumptions. Formula-only entries have null coefficients. A concrete instance estimate is not an exponent c in 2^{cn}.
- Tags
- dual, Gaussian error, parameterized