Learning With Errors
Recover or distinguish a noisy linear system.
Decision · binary secret and error · n samples
Decisional LWE; both secret and errors uniform in {0,1}; n samples; prime modulus q=Θ(n²)
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | An Improved BKW Algorithm for LWE with Applications to Cryptography and LatticesCrypto 2015SourceBibTeX / detailsclassical provable LWE binary secret binary errors linear samples | 29 Jun 2015 | 2(ln(2)/2+o(1)) n/log₂ log₂ n | Not separately normalized | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Decisional LWE; both secret and errors uniform in {0,1}; n samples; prime modulus q=Θ(n²)
- Computation
- Classical
- Rigor
- Provable
- Instances
- Uniform random equations
- Cost scale
- 2^{c n / log₂ log₂ n + o(n/log₂ log₂ n)}
- Parameter
- n
- Description
- Decisional LWE; both secret and errors uniform in {0,1}; n samples; prime modulus q=Θ(n²)
- Comparison rules
- Compare bounds only under the displayed noise, sample and memory conditions.
- Tags
- binary secret, binary errors, linear samples