Welcome to the LPN Estimator

This is an implementation of the estimator to evaluate the concrete security of learning parity with noise (LPN) problems (as well as its dual syndrome decoding problem) for pseudorandom correlation generator (PCG) and secure multi-party computation (MPC) applications. This estimator supports both exact noise distribution (each component of a noise vector is a uniform non-zero element in t random positions and zero elsewhere) and regular noise distribution (the noise vector is further divided into t consecutive sub-vectors, where each sub-vector has a single noisy coordinate), and covers any finite fields and power-of-two rings. For LPN over ℤ_2^λ, According to the analysis [LWYY24], each non-zero entry of a noise vector is sampled to guarantee that it is invertible, following the countermeasure [BBMS22]. Our estimator convers the following cryptanalysis algorithms for solving LPN problems :

• Pooled Gauss [EKM17]
• Information Set Decoding (ISD) [BJMM12, LWYY24, ES24]
• Statistical Decoding (SD) 2.0 [CDMT22]
• Algebraic attacks [BØ23, LWYYY25]
• Hybrid attack [WWYLYZW25]

This estimator integrates the following recent solvers of LPN problems, and will be updated if more advanced LPN solver is found.

• [LWYY24]
• [WWYLYZW25]
• [ES24]
• [LWYYY25]

Our estimator enables one to evaluate the concrete bit-security of an LPN instance, given the LPN parameters.

LPN Estimator

This is an estimator to evaluate the concrete security of LPN and (R)SD problems for PCG and MPC applications.

LPN Estimator Help Information

The following explains the LPN parameters used in the estimator :

• k : dimension (i.e., the length of a secret vector)
• N : the number of samples
• t : the Hamming weight of a noise vector

There is an extra parameter needed for syndrome decoding (a.k.a., dual LPN) problems:

• n : the number of correlations output by a protocol, where n = N / c and c is called the compression parameter

From the view of syndrome decoding problem, e.g., He = y, n is the length of the syndrome vector y, N is the length of noise vector e, and |e| = t.

For this estimator, while an LPN problem is defined by default over a binary field 𝔽₂, it can be also defined over any larger fields or power-of-two rings. The size of fields or rings has an impact on the concrete security of LPN problems. By the following parameters, one can specify the size:

• log q : the bit representation for the size of a finite field 𝔽_q
• λ : the bit representation for the size of a ring ℤ_2^λ

One can also download the estimator and run it in your computer ( LPN estimator ).

Citation

If you would like to cite the LPN estimator, we kindly suggest using the following citation format:

Contact

For any questions, please send email to team@lpnestimator.com