Paper 2023/176

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

Abstract

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. Update 18/02/2024: analysis extended to the constant code rate/constant error rate regime and link to github script added.