Learning Parity with Noise (LPN) standard

Propose Edit

Updated:

Learning Parity with Noise (LPN) is a computational problem adjacent to code-based cryptography that can be viewed as a direct predecessor and a special case of Learning with Errors restricted to the binary field $\ZZ_2$. LPN is equivalent to the problem of decoding random linear codes, a well-known NP-complete problem in coding theory [1]. Because it relies on simple bitwise operations, LPN yields a solid foundation to design lightweight constructions.

Definition

The LPN problem comes in two versions: Search and Decision. Both rely on a Bernoulli distribution $\mathsf{Ber}(\tau)$, where an error bit is $1$ with probability $\tau \in (0, 1/2)$ and $0$ otherwise.

Search LPN$_{n,m,\tau}$

Let matrix $\mat{A} \in \ZZ_2^{m \times n}$ and secret vector $\vec{s} \in \ZZ_2^n$ be chosen uniformly at random. Let $\vec{e} \in \ZZ_2^m$ be sampled from $\text{Ber}(\tau)$. Given the matrix $\mat{A}$ and the vector $\vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod 2$, an adversary is asked to find the secret vector $\vec{s}$.

Without the error vector $\vec{e}$, recovering $\vec{s}$ would be a trivial matter of solving a system of linear equations over $\ZZ_2$ using Gaussian elimination. The introduction of random bit-flips, referred to as error or noise, makes the system computationally hard to solve.

Decision LPN$_{n,m,\tau}$

Let matrix $\mat{A} \in \ZZ_2^{m \times n}$ and secret vector $\vec{s} \in \ZZ_2^n$ be chosen uniformly at random. Let $\vec{e} \in \ZZ_2^m$ be sampled from $\text{Ber}(\tau)$. An adversary is asked to distinguish between the LPN distribution $(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod 2)$ and a uniformly random distribution over $\ZZ_2^{m \times n} \times \ZZ_2^m$.

For cryptographic constructions, Decision LPN is often more directly applicable (e.g., for achieving indistinguishability for pseudorandom generators). Search and Decision LPN are polynomially equivalent for typical parameter choices [2]. Thus, we only give the decision version below.

Ring-LPN$_{m,\tau,\mathcal{R}}$

Let $\mathcal{R}_2$ be the polynomial ring $\ZZ_2[X]/(f(X))$. Let $\vec{a} \in \mathcal{R}_2^m$ and $s \in \mathcal{R}_2$ be chosen uniformly at random, and let $\vec{e} \in \mathcal{R}_2^m$ be drawn such that its coefficients follow $\text{Ber}(\tau)$. The adversary is asked to distinguish the distribution $(\vec{a}, \vec{b} = \vec{a} \cdot s + \vec{e} \bmod 2)$ from a uniformly random distribution over $\mathcal{R}_2^m \times \mathcal{R}_2^m$.

Ring-LPN [3], inspired by Ring-LWE [4], adds algebraic structure by working over polynomial rings instead of binary matrices, which enables more efficient matrix multiplication via NTT. The polynomial $f(X)$ is typically an irreducible polynomial over $\FF_2$ s.t. $\FF_2[X]/f(X)$ is a field.

Hardness

The close connection of LPN to the NP-hard problem of decoding random linear codes [1] is an indicator of its hardness. Furthermore, we can assess against the best known algorithms to solve LPN. A famous algorithm for solving LPN is the BKW algorithm [5] requiring $2^{\bigO{n / \log n}}$ operations and $m=2^{\bigO{n / \log n}}$ samples. This approach was later refined in [6] and [7]. If given only polynomially many samples $m=\poly(n)$, the running time of the best algorithm goes up to $2^{\bigO{n / \log \log n}}$ [8].

Constructions built from LPN

  • One-Way Functions [2], generically implying
    • Pseudorandom Generators (PRG)
    • Pseudorandom Function (PRF)
    • Pseudorandom Permutations (PRP)
  • Secret-key Encryption [9]
  • Secret-key Identification and Authentication [10][11][12]
  • Commitments [13]
  • Zero-Knowledge Proof of Knowledge [13]

Further Reading Suggestions

References

  • [1]Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. 1978. On the inherent intractability of certain coding problems (Corresp.). IEEE Trans. Inf. Theory 24, 3 (1978), 384–386. https://doi.org/10.1109/TIT.1978.1055873
  • [2]Krzysztof Pietrzak. 2012. Cryptography from Learning Parity with Noise. In SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012. Proceedings (Lecture Notes in Computer Science), 2012. Springer, 99–114. https://doi.org/10.1007/978-3-642-27660-6_9
  • [3]Stefan Heyse, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof Pietrzak. 2012. Lapin: An Efficient Authentication Protocol Based on Ring-LPN. In Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012. Revised Selected Papers (Lecture Notes in Computer Science), 2012. Springer, 346–365. https://doi.org/10.1007/978-3-642-34047-5_20
  • [4]Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings (Lecture Notes in Computer Science), 2010. Springer, 1–23. Retrieved from https://ia.cr/2012/230
  • [5]Avrim Blum, Adam Kalai, and Hal Wasserman. 2000. Noise-tolerant learning, the parity problem, and the statistical query model. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, 2000. ACM, 435–440. https://doi.org/10.1145/335305.335355
  • [6]Éric Levieil and Pierre-Alain Fouque. 2006. An Improved LPN Algorithm. In Security and Cryptography for Networks, 5th International Conference, SCN 2006, Maiori, Italy, September 6-8, 2006, Proceedings (Lecture Notes in Computer Science), 2006. Springer, 348–359. https://doi.org/10.1007/11832072_24
  • [7]Claire Delaplace, Andre Esser, and Alexander May. 2019. Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions. In Cryptography and Coding - 17th IMA International Conference, IMACC 2019, Oxford, UK, December 16-18, 2019, Proceedings (Lecture Notes in Computer Science), 2019. Springer, 178–199. Retrieved from https://ia.cr/2019/804
  • [8]Vadim Lyubashevsky. 2005. The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings (Lecture Notes in Computer Science), 2005. Springer, 378–389. https://doi.org/10.1007/11538462_32
  • [9]Henri Gilbert, Matthew J. B. Robshaw, and Yannick Seurin. 2008. How to Encrypt with the LPN Problem. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming Track C: Security and Cryptography Foundations (Lecture Notes in Computer Science), 2008. Springer, 679–690. https://doi.org/10.1007/978-3-540-70583-3_55
  • [10]Nicholas J. Hopper and Manuel Blum. 2001. Secure Human Identification Protocols. In Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings (Lecture Notes in Computer Science), 2001. Springer, 52–66. https://doi.org/10.1007/3-540-45682-1_4
  • [11]Ari Juels and Stephen A. Weis. 2005. Authenticating Pervasive Devices with Human Protocols. In Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings (Lecture Notes in Computer Science), 2005. Springer, 293–308. https://doi.org/10.1007/11535218_18
  • [12]Jonathan Katz and Ji Sun Shin. 2006. Parallel and Concurrent Security of the HB and HB\(^\mbox+\)Protocols. In Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings (Lecture Notes in Computer Science), 2006. Springer, 73–87. Retrieved from https://ia.cr/2005/461
  • [13]Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes. 2012. Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise. Retrieved from https://ia.cr/2012/513