  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 (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 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 coded-BKW. It outperforms significantly the 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 LPNs 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].
