Learning With Errors
Recover or distinguish a noisy linear system.
BKW · Regev · polynomial samples
q ≍ n²; σ = q/(√(2πn) (log₂ n)²); polynomially many 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 polynomial samples | 19 Jan 2019 | 21.6399 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 polynomial samples | 9 Jan 2019 | 21.6417 n + o(n) | — | PublishedSource checked |
| 3 | The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction FactorsISIT 2019SourceBibTeX / detailsclassical heuristic LWE BKW Regev regime polynomial samples | 19 Jan 2019 | 21.6507 n+o(n) | 21.6507 n+o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- q ≍ n²; σ = q/(√(2πn) (log₂ n)²); polynomially many fresh samples
- Computation
- Classical
- Rigor
- Heuristic list model
- Instances
- LWE distribution
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Coded-BKW exponents with a polynomial fresh-sample budget.
- Comparison rules
- Fix the Regev regime and restrict fresh input to poly(n) samples. Amplification creates additional equations at increased noise. Score total asymptotic time under the cited list model. Quantum rows retain the coherent table-access model. 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, polynomial samples