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

본문 미리보기

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 presen