TY - GEN
T1 - Statistical Decoding 2.0
T2 - 28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022
AU - Carrier, Kévin
AU - Debris-Alazard, Thomas
AU - Meyer-Hilfiger, Charles
AU - Tillich, Jean Pierre
N1 - Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022/1/1
Y1 - 2022/1/1
N2 - 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 decoders 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.
AB - 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 decoders 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.
U2 - 10.1007/978-3-031-22972-5_17
DO - 10.1007/978-3-031-22972-5_17
M3 - Conference contribution
AN - SCOPUS:85149645674
SN - 9783031229718
T3 - Lecture Notes in Computer Science
SP - 477
EP - 507
BT - Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings
A2 - Agrawal, Shweta
A2 - Lin, Dongdai
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 5 December 2022 through 9 December 2022
ER -