Classical hardness of learning parity with noise
Fix a noise rate $0 < \eta < 1/2$. For each $n$, draw a secret $s$ uniformly from $\mathbb{F}_2^n$, and give an algorithm $q(n)$ independent examples $$(a_i, b_i), \qquad a_i \sim \operatorname{Unif}(\mathbb{F}_2^n), \qquad b_i = \langle a_i, s \rangle + e_i \pmod 2,$$ where the $e_i$ are independent Bernoulli$(\eta)$ bits, independent of $s$ and of the $a_i$. The algorithm is a classical uniform randomized algorithm; its running time includes reading the examples and any preprocessing, and it receives no advice depending on the examples. Its success probability is $$p_{A,q,\eta}(n) = \Pr\bigl[A\bigl(n, (a_i, b_i)_{i=1}^{q(n)}\bigr) = s\bigr],$$ over the secret, the examples and the algorithm's randomness. A function of $n$ is negligible if for every $c > 0$ it is at most $n^{-c}$ for all large $n$. Blum, Kalai and Wasserman gave an algorithm that recovers $s$, for every constant $\eta$, with time and number of examples $2^{O(n/\log n)}$. As Pietrzak notes, a proof of the hardness below would imply $\mathrm{P} \ne \mathrm{NP}$.
Problem. Is it true that, for every fixed $\eta \in (0, 1/2)$, every polynomially bounded sample count $q\colon \mathbb{N} \to \mathbb{N}$ computable in polynomial time, and every such algorithm $A$ running in time polynomial in $n$, the success probability $p_{A,q,\eta}(n)$ is negligible? The algorithm and the sample count are fixed before $n \to \infty$ and may depend on $\eta$.
Source: The learning parity with noise assumption of cryptography: an early form is the Parity Assumption of Blum, Furst, Kearns and Lipton (1994), and the search version is Definition 1 of Pietrzak (2012). Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- ST
- Keywords
- AIM Open Applied Problems, average-case complexity, learning parity with noise, random linear codes
References
@inproceedings{blum1994,
author = {Blum, Avrim and Furst, Merrick and Kearns, Michael and Lipton, Richard J.},
title = {Cryptographic primitives based on hard learning problems},
booktitle = {Advances in Cryptology -- {CRYPTO} '93},
series = {Lecture Notes in Comput. Sci.},
volume = {773},
publisher = {Springer},
address = {Berlin},
year = {1994},
pages = {278--291},
doi = {10.1007/3-540-48329-2_24},
}
@inproceedings{pietrzak2012,
author = {Pietrzak, Krzysztof},
title = {Cryptography from learning parity with noise},
booktitle = {SOFSEM 2012: Theory and Practice of Computer Science},
series = {Lecture Notes in Comput. Sci.},
volume = {7147},
publisher = {Springer},
address = {Berlin},
year = {2012},
pages = {99--114},
doi = {10.1007/978-3-642-27660-6_9},
}
@article{blum2003,
author = {Blum, Avrim and Kalai, Adam and Wasserman, Hal},
title = {Noise-tolerant learning, the parity problem, and the statistical query model},
journal = {J. ACM},
volume = {50},
number = {4},
year = {2003},
pages = {506--519},
doi = {10.1145/792538.792543},
eprint = {cs/0010022},
archivePrefix = {arXiv},
}
@misc{aim-learning-parity-noise,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Classical hardness of learning parity with noise}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/306-learning-parity-noise.md},
note = {Entry 306 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00291, "Classical hardness of learning parity with noise", clopen.solutions.