Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
Classical · noise probability 1/√n
Bernoulli error probability p = n^{-1/2}; unlimited fresh samples
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 LPN low noise | 29 Jun 2015 | O(n⁴ exp(√n)) | poly(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Bernoulli error probability p = n^{-1/2}; unlimited fresh samples
- Computation
- Classical
- Rigor
- Provable
- Instances
- Uniform random equations
- Cost scale
- 2^{c √n + o(√n)}
- Parameter
- √n
- Description
- Bernoulli error probability p = n^{-1/2}; unlimited fresh samples
- Comparison rules
- Compare bounds only under the displayed noise, sample and memory conditions.
- Tags
- low noise, unlimited samples