The syndrome decoding problem and how to use it to identify yourself. (invited talk PQSM workshop)

After the introduction of one of the main hard problem used in code-based cryptography (namely the syndrome decoding problem (SD)), I will describe the information set decoding algorithm (ISD) which is the most efficient algorithm to solve the SD problem (wrt the parameter choice). Then I will present two zero-knowledge schemes which rely on this NP-complete problem (namely the Stern identification scheme from CRYPTO 1993 and the Cayrel/Véron/El Yousfi scheme from SAC 2010).