Speaker
Description
The security of code-based cryptography relies fundamentally on the computational hardness of decoding random linear codes. Until recently, the most efficient known algorithms for the decoding problem were Information Set Decoding (ISD) algorithms, which we refer to as primal attacks in this presentation.
In 2001, a new class of decoding algorithms, known as dual attacks, was introduced and has been significantly improved over the past four years. These attacks rely on a reduction of the decoding problem to the Sparse Secret Learning Parity with Noise (sparse-LPN) problem, where samples are constructed using low-weight codewords of the dual (orthogonal) code. As a consequence, dual attacks require, as a core subroutine, the ability to find low-weight codewords in the dual code.
This observation can be seen as a first step toward addressing a long-standing open question: can the decoding problem be dualized, that is, polynomially reduced to a decoding problem in the dual code? This question is of particular importance in code-based cryptography, since a positive answer would imply that decoding at rate R can be reduced to decoding at rate 1 - R. Such a result would be highly significant, as the complexity of existing primal attacks is not symmetric with respect to the code rate.
In this presentation, after a brief overview of primal and dual attacks, we examine the parameter regimes in which dual attacks currently outperform the best known primal attacks. In particular, we focus on the relevance of these attacks for cryptosystems such as BIKE, McEliece, and HQC, where the target decoding distance grows sub-linearly with the code length.