Algorithms for Nearest Neighbor Problem and application to cryptanalysis of McEliece cryptosystem

Le vendredi 24 juin, Mickaël Hamdad (Lip6, Sorbonne Univ. ) fera une présentation au laboratoire MIS à 10h en salle 301

Abstract :

The best algorithm to this day for McEliece cryptosystem's cryptanalysis is due to Alexander May and Ilya Ozerov. It uses in a crucial way a subroutine that solves the Nearest Neighbor Problem (in boolean context). I will present  algorithms that exploit the projections method and Galton-Watson's trees to solve this problem. The objective is to find an algorithm which will be implementable and have a better complexity in terms of number of operations and memory access than existent ones.