Learning With Errors
Recover or distinguish a noisy linear system.
Small secret · guessing and lattice reduction
Secret guessing followed by a reduced-dimension Gaussian-error lattice attack; distribution and guessed coordinates explicit
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Lattice Decoding Attacks on Binary LWEACISP 2014SourceBibTeX / detailshybrid small secret Gaussian error | 21 Feb 2017 | min0≤k≤n 2k · Clattice(n−k,m,q,σ) | Space of the chosen residual lattice solver, plus polynomial storage. | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Secret guessing followed by a reduced-dimension Gaussian-error lattice attack; distribution and guessed coordinates 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
- small secret, hybrid, Gaussian error