Learning With Errors
Recover or distinguish a noisy linear system.
BKW · Regev · unlimited samples
q ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samples
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction FactorsISIT 2019SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime unlimited samples unstructured | 19 Jan 2019 | 20.8917 n + o(n) | — | PublishedSource checked |
| 2 | On the Asymptotics of Solving the LWE Problem Using Coded-BKW with SievingIEEE Trans. Information Theory 2019SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime unlimited samples unstructured | 9 Jan 2019 | 20.8927 n + o(n) | — | PublishedSource checked |
| 3 | Coded-BKW with SievingAsiacrypt 2017SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime unlimited samples unstructured | 3 Dec 2017 | 20.8951 n + o(n) | — | PublishedSource checked |
| 4 | Coded-BKW with SievingAsiacrypt 2017SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime unlimited samples | 3 Dec 2017 | 20.9054 n+o(n) | 20.9054 n+o(n) | PublishedSource checked |
| 5 | An Improved BKW Algorithm for LWE with Applications to Cryptography and LatticesCrypto 2015SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime unlimited samples unstructured | 8 Jun 2015 | 20.9299 n + o(n) | — | PublishedSource checked |
| 6 | On the Complexity of the BKW Algorithm on LWEDesigns, Codes and Cryptography 2015SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime unlimited samples unstructured | 11 Nov 2012 | 2n+o(n) | 2n+o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- q ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samples
- Computation
- Classical
- Rigor
- Heuristic list model
- Instances
- LWE distribution
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Historical classical BKW coefficients at the Regev error scale, with abundant fresh input equations.
- Comparison rules
- Fix prime q ≍ n² and Gaussian error standard deviation σ = q/(√(2πn) (log₂ n)²). Exponentially many independent classical samples with the same secret may be read; sample acquisition is charged. The coordinate distribution and independence assumptions of each analysis remain part of the claim. These bounds are not for a fixed finite sample budget, small binary errors, or a structured ring instance. The score is the leading coefficient of n in log₂ time. Memory bounds are recorded separately when identified. Objective: Decision-LWE with constant target distinguishing advantage. Search-LWE algorithms are admissible as decision upper bounds; a search-only theorem is not silently identified with the source's optimized decision corollary.
- Tags
- classical, heuristic, LWE, BKW, Regev regime, unlimited samples, unstructured