Date de l'exposé : 16 juin 2023
Dual attacks in Coding Theory
The first part of this talk will be dedicated to present a new algorithm, which we introduced in the paper "Statistical decoding 2.0: Reducing Decoding to LPN", to decode generic linear codes. The algorithm is based on the computation of many parity-checks of low weight which are then used to generate LPN samples where the secret is a part of the error vector. It is the first dual attack in code based cryptography which outperforms for certain ranges information set decoding techniques (primal attacks) which have been for $60$ years the dominant tool for solving the decoding problem and choosing the parameters of code-based cryptosystems. The analysis of our algorithm rely on some assumptions coming from the LPN model and which are closely related to similar assumptions made to analyse dual attacks in lattices. Originally, in our paper we noticed some discrepancy between our assumptions and the experimental results, however we conjectured that asymptotically this discrepancy was not a problem. More recently, a paper strongly questioned dual attacks in lattices by showing that the assumptions made there were in contradiction with some theorems in certain regimes or with well-tested heuristics in some other regimes. The second part of this talk will be dedicated to show formally that the assumptions we made in coding theory cannot hold and that, as a result, we need to make a small correction to our original algorithm. We now provide a full analysis of this corrected algorithm which does not rely on these previous assumptions and show that it achieves the originally claimed complexities. This is a joint work with K. Carrier, T. Debris-Alazard and J-P. Tillich.
