Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
Classical · memory coefficient ≤ 2/3
Constant Bernoulli noise; limiting memory coefficient ≤2/3 on the n/log₂n scale
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Dissection-BKWCrypto 2018SourceBibTeX / detailsclassical heuristic LPN time-memory tradeoff | 2018 | 2(((1−1/3) log₂ 4)+ε) n/log₂ n | 2(log₂(4)/3+ε) n/log₂ n | PublishedSource checked |
| 2 | Dissection-BKWCrypto 2018SourceBibTeX / detailsclassical heuristic LPN time-memory tradeoff | 2018 | 2(log₂(4)+ε) n/log₂ n | 2(log₂(4)/(4−1)+ε) n/log₂ n | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Constant Bernoulli noise; limiting memory coefficient ≤2/3 on the n/log₂n scale
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- Uniform random equations
- Cost scale
- limsup log₂(T) log₂(n) / n
- Parameter
- n
- Description
- Constant Bernoulli noise; memory ≤ 2^{(2/3+o(1)) n/log₂ n}
- Comparison rules
- Compare the leading time coefficient at the stated subexponential memory cap. The c-sum methods use the Independence Heuristic; tailored rows additionally require the Tailoring Heuristic. Every fixed positive exponent slack is allowed. Quantum rows assume coherent indexed access to the stored list.
- Tags
- constant noise, time-memory tradeoff, independence heuristic