Paper 2023/1852

Reduction from sparse LPN to LPN, Dual Attack 3.0

Kévin Carrier, Laboratoire ETIS, UMR 8051, CY Cergy-Paris Université, ENSEA, CNRS
Thomas Debris-Alazard, Project GRACE, Inria Saclay, Laboratoire LIX, Ecole Polytechnique, Institut Polytechnique de Paris, 1 rue Honoré d'Estienne d'Orves, 91120 Palaiseau Cedex
Charles Meyer-Hilfiger, Project COSMIQ, Inria de Paris
Jean-Pierre Tillich, Project COSMIQ, Inria de Paris

The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders ($\mathsf{ISD}$). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly $\mathsf{ISD}$ decoders for a rather large range of rates. This RLPN decoder relies on two ingredients, first reducing decoding to some underlying LPN problem, and then computing efficiently many parity-checks of small weight when restricted to some positions. We revisit RLPN-decoding by noticing that, in this algorithm, decoding is in fact reduced to a sparse-LPN problem, namely with a secret whose Hamming weight is small. Our new approach consists this time in making an additional reduction from sparse-LPN to plain-LPN with a coding approach inspired by $\mathsf{coded}$-$\mathsf{BKW}$. It outperforms significantly the $\mathsf{ISD}$'s and RLPN for code rates smaller than $0.42$. This algorithm can be viewed as the code-based cryptography cousin of recent dual attacks in lattice-based cryptography. We depart completely from the traditional analysis of this kind of algorithm which uses a certain number of independence assumptions that have been strongly questioned recently in the latter domain. We give instead a formula for the LPN noise relying on duality which allows to analyze the behavior of the algorithm by relying only on the analysis of a certain weight distribution. By using only a minimal assumption whose validity has been verified experimentally we are able to justify the correctness of our algorithm. This key tool, namely the duality formula, can be readily adapted to the lattice setting and is shown to give a simple explanation for some phenomena observed on dual attacks in lattices in [DP23].

Available format(s)
Public-key cryptography
Publication info
Code-based CryptographyCryptanalysisStatistical DecodingDual Attacks
Contact author(s)
kevin carrier @ ensea fr
thomas debris @ inria fr
charles meyer-hilfiger @ inria fr
jean-pierre tillich @ inria fr
2023-12-04: approved
2023-12-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kévin Carrier and Thomas Debris-Alazard and Charles Meyer-Hilfiger and Jean-Pierre Tillich},
      title = {Reduction from sparse {LPN} to {LPN}, Dual Attack 3.0},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1852},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.