Learning With Errors
Recover or distinguish a noisy linear system.
Lattice decoding · parameterized models
Search-LWE through BDD; basis reduction, enumeration parameters and target success probability stay explicit
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Better Key Sizes (and Attacks) for LWE-Based EncryptionCT-RSA 2011SourceBibTeX / detailsdecoding nearest planes sample-sensitive | 30 Nov 2010 | Treduce(B) + poly(m) ∏i=1m di | Polynomial working space for depth-first search; the ∏di output set need not all be retained. | PublishedSource checked |
| — | On the concrete hardness of Learning with ErrorsJournal of Mathematical Cryptology 2015SourceBibTeX / detailsdecoding historical cost model tradeoff | 2 Oct 2015 | minδ₀,d: P(d,δ₀)≥ε [TBKZ(m,δ₀) + tnode ∏i di] | Depends on the selected lattice reduction and enumeration implementation. | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Search-LWE through BDD; basis reduction, enumeration parameters and target success probability stay explicit
- Computation
- Classical
- Rigor
- Heuristic / model-dependent
- 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
- primal, BDD, Gaussian error, parameterized