ACCESS
Algebraic Coding and Cryptography
Seminar Series
Online Event
ACCESS is a joint effort designed to highlight world-class research in coding theory, cryptography, and related areas and to encourage collaboration among its participants.
Next seminar
September 03
September 03
Andre Esser
Technology Innovation Institute
Technology Innovation Institute
Sieving for Codes
Abstract. The decoding of linear codes is one of the most fundamental problems in coding theory and the foundation of most code-based cryptography. The decoding of linear codes is closely related to the problem of finding codewords of small norm, a problem that has been intensively studied in the case of lattices in form of the shortest vector problem (SVP). Recently, Guo, Johansson and Nguyen showed how to translate some of the techniques from the lattice world to the code setting, by embedding a sieving technique into the well-known decoding concept of Information Set Decoding (ISD).
In this talk we cover all building blocks of this Sieving for Codes framework, as well as several improvements introduced after its appearance. We first recall the basic idea of ISD from the code setting and the general concept of lattice sieving. We then discuss the embedding of Sieving into ISD algorithms and highlight the essential differences between code- and lattice-sieving that make the translation work. Despite the differences, at the heart of Sieving for Codes lies, similar to the lattice-setting, a nearest-neighbor routine (on the Hamming-Sphere). We discuss different algorithms to instantiate this routine, ranging from basic techniques to a procedure tailored to the code-based setting achieving close to optimal complexities. We conclude with future perspectives and open questions.
This talk is based on joint work with Léo Ducas, Simona Etinski and Elena Kirshanova.
Biography. Andre is currently the Lead Researcher of the asymmetric cryptanalysis team at the Technology Innovation Institute (TII) in Abu Dhabi. He received his PhD in 2020 under the supervision of Alexander May from Ruhr University Bochum. His main research focus lies in the field of post quantum cryptography, with a special focus on code-based cryptanalysis. Andre works on the edge of theoretical and practical cryptanalysis. As such, he is co-designer of three submissions to the NIST PQC renewed call for additional digital signatures and co-holder of multiple record computations in the field of decoding.