Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
Classical · memory coefficient ≤ 1/2
Constant Bernoulli noise; limiting memory coefficient ≤1/2 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 tailoring heuristic | 2018 | 2(log₂(7)−1+ε) n/log₂ n | 2(1/2+ε) n/log₂ n | PublishedSource checked |
| 2 | Dissection-BKWCrypto 2018SourceBibTeX / detailsclassical heuristic LPN time-memory tradeoff | 2018 | 2(((1−2/6) log₂ 7)+ε) n/log₂ n | 2(log₂(7)/6+ε) n/log₂ n | PublishedSource checked |
| 3 | Dissection-BKWCrypto 2018SourceBibTeX / detailsclassical heuristic LPN time-memory tradeoff | 2018 | 2(log₂(7)+ε) n/log₂ n | 2(log₂(7)/(7−1)+ε) n/log₂ n | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Constant Bernoulli noise; limiting memory coefficient ≤1/2 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^{(1/2+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