Paper 2024/276

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

Abstract

Syndrome decoding (SD), together with its regular-noise variant (RSD), is fundamental to many cryptographic primitives; in the generator formulation used in cryptography, it is closely related to learning parity with noise (LPN). While recent proposals extend these problems to larger fields, the concrete security of SD over large fields remains comparatively less understood. This gap leaves room for more effective attacks against SD-based primitives over large fields. In this paper, we present an improved algorithm for solving SD over large fields. Our method modifies Prange's information-set decoding algorithm by iteratively applying Gaussian elimination to reduced-size matrices rather than to the full-size matrix. We call this the ``Reduce and Prange (RP)" algorithm and demonstrate its effectiveness for both SD and its variant with regular noise over large finite fields (e.g., $\mathbb{F}_{2^{128}}$). On the comparison rows of our numerical section, RP lowers the SD estimate by up to $6$ bits, and on the 128-bit recommended SD rows the drop is up to $7$ bits, relative to Liu et al. (Eurocrypt'24). For SD with regular noise, regular-RP gives the lowest listed estimate on the small and medium tested parameter sets, improving on the best previously listed estimate by up to $15$ bits; on the largest tested sets the algebraic estimate of Briaud and {\O}ygarden (Eurocrypt'23) remains lower.

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