Learning With Errors
Recover or distinguish a noisy linear system.
Gaussian error · algebraic bounds
Search-LWE over prime fields; arbitrary full secret and explicit Gaussian width, with algebraic sample requirements
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | New Algorithms for Learning in Presence of ErrorsICALP 2011SourceBibTeX / detailssmall Gaussian error provable oracle samples | 13 Dec 2010 | 2^{Õ(n2ε)}, for αq=n^ε and fixed ε<1/2 | Exponential-size linearization; no numerical space coefficient extracted. | PublishedSource checked |
| — | Algebraic Algorithms for LWEePrint 2014/1018SourceBibTeX / detailsconditional semi-regularity Gaussian error exponential samples | 26 Feb 2015 | O(2n[ω(1+CA)H₂(CA/(1+CA)) + πlog₂(e)/(4A²)]) | O(2n[2(1+CA)H₂(CA/(1+CA)) + πlog₂(e)/(4A²)]) | PreprintSource checked |
| — | Algebraic Algorithms for LWEePrint 2014/1018SourceBibTeX / detailsalgebraic linearization Gaussian error | 26 Feb 2015 | O(2ω D log₂(n/D) · σq log q) if D=o(n); O(2ω n log₂(D/n) · σq log q) if n=o(σ² log n); D=8σ² log₂ n+1 | Replace ω by 2 in the two time exponents. | PreprintSource checked |
Comparison definition & assumptions
- Regime
- Search-LWE over prime fields; arbitrary full secret and explicit Gaussian width, with algebraic sample requirements
- Computation
- Classical
- Rigor
- Mixed: theorem / conditional
- 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
- algebraic, Gaussian error, sample-sensitive