Paper 2022/1000

Statistical Decoding 2.0: Reducing Decoding to LPN

Kevin Carrier, CY Cergy-Paris University
Thomas Debris-Alazard, Inria Saclay - Île-de-France Research Centre
Charles Meyer-Hilfiger, Inria de Paris Research Centre
Jean-Pierre Tillich, Inria de Paris Research Centre
Abstract

The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD). A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error. This algorithm was long forgotten because even the best variants of it performed poorly when compared to the simplest ISD algorithm. We revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decodings at code rates smaller than $0.3$. It gives for the first time after $60$ years, a better decoding algorithm for a significant range which does not belong to the ISD family.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. arXiv
Keywords
code-based cryptography decoding of linear codes statistical decoding
Contact author(s)
kevin carrier @ ensea fr
thomas debris @ inria fr
charles meyer-hilfiger @ inria fr
jean-pierre tillich @ inria fr
History
2022-10-17: last of 4 revisions
2022-08-03: received
See all versions
Short URL
https://ia.cr/2022/1000
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1000,
      author = {Kevin Carrier and Thomas Debris-Alazard and Charles Meyer-Hilfiger and Jean-Pierre Tillich},
      title = {Statistical Decoding 2.0: Reducing Decoding to LPN},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1000},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1000}},
      url = {https://eprint.iacr.org/2022/1000}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.