Paper 2023/1460

Rigorous Foundations for Dual Attacks in Coding Theory

Charles Meyer-Hilfiger, French Institute for Research in Computer Science and Automation
Jean-Pierre Tillich, French Institute for Research in Computer Science and Automation

Dual attacks aiming at decoding generic linear codes have been found recently to outperform for certain parameters information set decoding techniques which have been for $60$ years the dominant tool for solving this problem and choosing the parameters of code-based cryptosystems. However, the analysis of the complexity of these dual attacks relies on some unproven assumptions that are not even fully backed up with experimental evidence. These dual attacks can actually be viewed as the code-based analogue of dual attacks in lattice based cryptography. Here too, dual attacks have been found out those past years to be strong competitors to primal attacks and a controversy has emerged whether similar heuristics made for instance on the independence of certain random variables really hold. We will show that the dual attacks in coding theory can be studied by providing in a first step a simple alternative expression of the fundamental quantity used in these dual attacks. We then show that this expression can be studied without relying on independence assumptions whatsoever. This study leads us to discover that there is indeed a problem with the latest and most powerful dual attack introduced in the recent Asiacrypt 2022 paper "Statistical decoding 2.0: Reducing Decoding to LPN" (RLPN) and that for the parameters chosen in this algorithm there are indeed false candidates which are produced and which are not predicted by the analysis provided there which relies on independence assumptions. We then suggest a slight modification of this algorithm consisting in a further verification step, analyze it thoroughly, provide experimental evidence that our analysis is accurate and show that the complexity claims made in RLPN are indeed valid for this modified algorithm. This approach provides a simple methodology for studying rigorously dual attacks which could turn out to be useful for further developing the subject.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in TCC 2023
code-based cryptographycryptanalysisdecoding of linear codesstatistical decoding
Contact author(s)
charles meyer-hilfiger @ inria fr
jean-pierre tillich @ inria fr
2023-09-24: approved
2023-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charles Meyer-Hilfiger and Jean-Pierre Tillich},
      title = {Rigorous Foundations for Dual Attacks in Coding Theory},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1460},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.