Variants of the Syndrome Decoding Problem and algebraic cryptanalysis

Abstract. The intractability of decoding generic linear codes is at the core of an important branch of post-quantum cryptography. In this context, the code is random by design or it is assumed to be so in the security reduction. This talk will focus on versions of the Decoding Problem where the error vector is structured, often to achieve better performance. We will mostly consider the Regular Syndrome Decoding Problem and a paper presented at Eurocrypt 2023. If time permits, we will also mention other assumptions which appear in the analysis of recent signature proposals. While combinatorial techniques such as Information Set Decoding are often the method of choice to attack these problems, we will study the potential of algebraic algorithms. Even though they are not the most efficient in general, these approaches may allow to identify new weak parameter zones.

Based on joint works with Morten Oygarden.

Suggested reading: ia.cr/2023/176