Paper 2023/176

A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions

Pierre Briaud, Inria de Paris Research Centre, Sorbonne University (France)
Morten Øygarden, Simula UiB (Norway)

The Regular Syndrome Decoding (RSD) problem, a variant of the Syndrome Decoding problem with a particular error distribution, was introduced almost 20 years ago by Augot et al. . In this problem, the error vector is divided into equally sized blocks, each containing a single noisy coordinate. More recently, the last five years have seen increased interest in this assumption due to its use in MPC and ZK applications. Generally referred to as "LPN with regular noise" in this context, the assumption allows to achieve better efficiency when compared to plain LPN. We present the first attack on RSD relying on Gröbner bases techniques. After a careful theoretical analysis of the underlying polynomial system, we propose concrete attacks that are able to take advantage of the regular noise distribution. In particular, we can identify several examples of concrete parameters where our techniques outperform other algorithms.

Note: Update 22/11/2023: corrected a mismatch between Table 1 and Tables 4 and 5.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. EUROCRYPT 2023
Learning Parity with NoiseRegular distributionPseudorandom Correlation GeneratorAlgebraic cryptanalysis
Contact author(s)
pierre briaud @ inria fr
morten oygarden @ simula no
2023-11-22: last of 2 revisions
2023-02-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pierre Briaud and Morten Øygarden},
      title = {A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/176},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.