Étude et conception d'algorithmes quantiques pour le décodage de codes linéaires

International audienceLes cryptosystèmes basés sur les codes correcteurs sont de bons candidatspour la cryptographie post-quantique. Afin de bien choisir leurs paramètres desécurité, il faut tenir compte des attaques quantiques les plus puissantes.Bernstein avait montré en 2009 qu'il est possible d'utiliser l'algorithme derecherche non-structurée de Grover avec l'algorithme de Prange pour obtenir unalgorithme ISD quantique dont la complexité est la racine carrée de l'algorithme dePrange classique. Nous avons réussi à faire mieux que ce résultat en considérant lesalgorithmes classiques plus sophistiqués et en se servant de techniques basées sur lamarche aléatoire quantique (Quantum Walk) et inspirées par les meilleurs algorithmesquantiques de résolution du problème de la somme des sous-ensembles (subset sum)