LPN (Learning Parity with Noise) is a fundamental mathematical problem in modern cryptography, widely used to create secure encryption algorithms. It is based on representing secret information as a set of equations with errors, making it difficult for any bounded attacker to find it. LPN is a promising post-quantum hardness assumption with parallels to the theory of error-correcting codes.
What is Learning Problem?
Consider the problem depicted in Fig0. Given the blue, how can we find the red?
One second later, we can quickly solve it using Gaussian elimination, as shown in Fig1.
However, if we introduce some noise (yellow) to the equation, as shown in Figures 2 and 3, the problem becomes more challenging. It is difficult to find the red when only given the blue (and the yellow is unknown).
This is the Learning Problem. The red represents the secret we want to hide, and any bounded challenger cannot find the red if they only have knowledge of the blue. The LPN, which we will introduce, is one variant of this problem.
What is LPN?
Learning Parity with Noise (LPN) is a mathematical problem widely utilized in cryptography to create secure encryption algorithms. It involves representing secret information as a set of equations with errors, effectively hiding the value of a secret by introducing noise. LPN is conjectured to be a hard problem to solve and is utilized as a post-quantum hardness assumption, similar to the theory of error-correcting codes and with parallels to learning with errors (LWE). While fewer cryptographic constructions are known from LPN than LWE, LPN offers concrete efficiency that can rival dedicated constructions in certain cases.
History:
In 1996, Oded Goldreich, Shafi Goldwasser, and Dana Ron introduced the LPN assumption in their paper “Property Testing and Its Connection to Learning and Approximation.” The paper presented an algorithm for learning an unknown distribution that closely approximates a known discrete distribution with bounded errors. Additionally, the authors introduced the LPN assumption to analyze the algorithm’s computational complexity. In 1999, Johan Hastad formally introduced the LPN problem as a computational problem and demonstrated its NP-hardness in the worst case. Hastad’s work precisely defined the LPN problem and established its computational complexity.
The LPN assumption has become a significant assumption in symmetric cryptography. It has been utilized in various cryptographic primitives, including encryption schemes, digital signatures, and authentication protocols. The security of these cryptographic systems is based on the difficulty of solving linear equations with binary coefficients in the presence of noise, which is a challenging computational problem. Additionally, LPN is highly efficient, making use of multiplication and addition in a finite field.
An early example of a ZKP commitment scheme based on LPN is the scheme proposed by Damgard, Fitzi, and Nielsen in their 2005 paper “Unconditionally Secure Constant-Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation.” This scheme provides an unconditionally secure method for multi-party computation, utilizing the LPN assumption as a cryptographic primitive.
The LPN problem is defined as follows:
A · s + e mod p = u
Given a matrix A, it is computationally challenging to find a vector s that infinitely approximates a target vector u, even when a sparse noise vector e is randomly sampled within a fixed range. Here, the dot product is represented by “·”, p is a prime number greater than or equal to 2, s is an n-dimensional vector in the integer field of mod p, and the noise vector e is sparse with a small Hamming weight.
LPN vs. LWE
Boolean Circuits work better with LPN
In order to commit all the wires of the circuits gate by gate, we will utilize the VOLE protocol, which is based on the LPN assumption. The details of the VOLE protocol will be discussed in the following blog.
In the subsequent article, we will sequentially construct efficient and commercially viable commitment schemes for data exchange in the order of OT [Rabin81], OT Extension [IKNP03], GGM [GGM86], FSS [Eurocrypt 2015], and PGC [BCGIKS19]. Our ultimate goal is to implement Interactive Zero-Knowledge Proof (IZK).
