Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


Variants of the Syndrome Decoding Problem and algebraic cryptanalysis

September 6, 2023


Pierre Briaud - Inria Paris & Sorbonne Université (France)


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:

Presented at

Crypto Reading Club talk on 2023-Sep-06

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created July 25, 2023, Updated September 06, 2023