Kévin Carrier
Ensea

Thomas Debris-Alazard
Inria Saclay

Charles Meyer-Hilfiger
Inria de Paris

Jean-Pierre Tillich
Inria de Paris

Keywords:

Abstract

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 (\\textsf{ISD}). However, recently a new algorithm called \\textsf{RLPN}\-decoding which relies on a completely different approach was introduced and it has been shown that \\textsf{RLPN} outperforms significantly \\textsf{ISD} decoders for a rather large range of rates. This \\textsf{RLPN} decoder relies on two ingredients, first reducing decoding to some underlying \\textsf{LPN} problem, and then computing efficiently many parity-checks of small weight when restricted to some positions. We revisit \\textsf{RLPN}\-decoding by noticing that, in this algorithm, decoding is in fact reduced to a sparse-\\textsf{LPN} problem, namely with a secret whose Hamming weight is small. Our new approach consists this time in making an additional reduction from sparse-\\textsf{LPN} to plain-\\textsf{LPN} with a coding approach inspired by \\textsf{coded}\-\\textsf{BKW}. It outperforms significantly the \\textsf{ISD}’s and \\textsf{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 \\textsf{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 [[[https://link.springer.com/chapter/10.1007/978-3-031-58754-2_11#ref-CR19][19]]].