Learning With Errors
Recover or distinguish a noisy linear system.
BKW · Regev · quantum / Grover
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 / detailsquantum heuristic LWE BKW Regev regime unlimited samples coherent reads | 19 Jan 2019 | 20.8782 n + o(n) | — | PublishedSource checked |
| 2 | On the Asymptotics of Solving the LWE Problem Using Coded-BKW with SievingIEEE Trans. Information Theory 2019SourceBibTeX / detailsquantum heuristic LWE BKW Regev regime unlimited samples coherent reads | 9 Jan 2019 | 20.8795 n + o(n) | — | PublishedSource checked |
| 3 | Coded-BKW with SievingAsiacrypt 2017SourceBibTeX / detailsquantum heuristic LWE BKW Regev regime unlimited samples coherent reads | 3 Dec 2017 | 20.8856 n + o(n) | — | PublishedSource checked |
Comparison definition & assumptions
- Regime
- q ≍ n²; σ = q/(√(2πn) (log₂ n)²); independent fresh samples
- Computation
- Quantum
- Rigor
- Heuristic list model
- Instances
- LWE distribution
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Quantum-search variants of coded BKW with abundant classical input samples.
- Comparison rules
- Use the same Regev modulus, error and fresh classical sample convention as the classical category. Grover-based geometric searches assume coherent indexed reads of their working tables. Record the coherent-access assumption explicitly. A reusable-walk method that requires coherent writes or a stronger distribution model belongs in a separately tagged comparison category; no such unpublished claim is seeded here. 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
- quantum, heuristic, LWE, BKW, Regev regime, unlimited samples, coherent reads