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.