Paper 2024/276

Reduce and Prange: Revisiting Prange's ISD for Solving LPN/RSD over Large Fields

Abstract

The Learning Parity with Noise (LPN) problem and its regular noise variant are fundamental to many cryptographic primitives. While recent proposals extend these problems to larger fields to enhance cryptographic applications, the security implications of LPN over large fields remain understudied. This gap has facilitated more effective attacks, potentially compromising the security of LPN-based primitives over large fields. In this paper, we present an improved algorithm for solving LPN over large fields. Our method enhances the classical Gaussian elimination attack, specifically Prange's information set decoding algorithm, by iteratively applying Gaussian elimination to reduced-size matrices rather than the full-size matrix. We call this the ``Reduce and Prange (RP)" algorithm and demonstrate its effectiveness for both LPN and its variant with regular noise over large finite fields (e.g., $\mathbb{F}_{2^{128}}$). Building on the RP algorithm, we develop a modified algebraic algorithm for LPN with regular noise over $\mathbb{F}_q$ with $q \geq 2$, extending the work of Briaud and Øygard (Eurocrypt'23). Furthermore, we demonstrate that Scalable Multiparty Garbling (CCS'23) fails to meet their claimed security levels. For LPN over large fields (e.g., 128-bit field size), our algorithm reduces bit-security by up to 9 bits relative to Liu et al. (Eurocrypt'24). In the case of LPN with regular noise, our RP algorithm surpasses both Liu et al. and Briaud and Øygard (Eurocrypt'23) under specific parameter settings, achieving up to 16-bit reduction in security.

Note: 25-04-24. Updated descriptions, results, algorithms, and estimation results. 24-11-29. Updated some paragraphs about the advantages of Reduce and Prange.