Learning With Errors
Recover or distinguish a noisy linear system.
Binary error · conditional algebraic bounds
Uniform errors in {0,1}, arbitrary secret over an odd prime field; linear and quasilinear sample regimes remain separate parameter contracts
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Algebraic Algorithms for LWEePrint 2014/1018SourceBibTeX / detailsbinary error linear samples conditional semi-regularity | 26 Feb 2015 | O(n² · 2ωn(1+β)H₂(β/(1+β))+o(n)), β=C−1/2−√(C(C−1)) | O(n² · 22n(1+β)H₂(β/(1+β))+o(n)) | PreprintSource checked |
| — | Algebraic Algorithms for LWEePrint 2014/1018SourceBibTeX / detailsbinary error quasilinear samples conditional subexponential | 26 Feb 2015 | O(m² · 2ωn log₂log₂log₂(n)/(8log₂log₂(n))) | O(m² · 22n log₂log₂log₂(n)/(8log₂log₂(n))) | PreprintSource checked |
Comparison definition & assumptions
- Regime
- Uniform errors in {0,1}, arbitrary secret over an odd prime field; linear and quasilinear sample regimes remain separate parameter contracts
- Computation
- Classical
- Rigor
- Conditional: semi-regularity
- 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
- binary error, algebraic, semi-regularity, sample-sensitive