logo EDITE Sujets de doctorat

Analyse du décodage générique en métrique de Hamming et étude des cryptosystèmes basés sur la métrique rang

Résumé rédigé par
Directeur de thèse:
Doctorant: Rodolfo CANTO TORRES
Unité de recherche ? 0 Laboratoire inconnu!

Projet

Le projet de these s'interesse a la cryptographie basee sur le codes. Nous proposons d'explorer deux voies de recherche :

1. Analyse des algorithmes de décodage générique. La meilleure attaque contre la plupart des cryptosystèmes basés sur les codes et en particulier contre le système de chiffrement de McEliece, consiste à décoder dans un code linéaire binaire (d'apparence) aléatoire. Ces techniques de décodage ont un coût exponentiel. Ces dernières années de nombreuses améliorations ont été proposées pour diminuer la valeur de l'exposant (la dernière amélioration date du printemps 2015). Des travaux préliminaires indiquent, que dans le cas où l'erreur est de poids sous-linéaire, cette amélioration devient asymptotiquement négligeable. Ce premier axe consistera à poursuivre l'analyse asymptotique de ces algorithmes pour mieux comprendre leur comportement. Cette analyse est rendue complexe par un grand nombre de paramètres à optimiser qui ne permet pas l'obtention de formules closes. Pour chaque taille de système il faut résoudre un problème d'optimisation pour obtenir le meilleur réglage de l'algorithme et sa complexité. En particulier, nous envisageons de concevoir et de mettre à la disposition de la communauté un outil logiciel permettant d'évaluer précisément les coûts algorithmiques des divers algorithmes. Un tel outil n'existe pas et serait d'une grande utilité pour les concepteurs de schémas cryptographiques basés sur les codes.

2.-Étude des codes en métrique rang. Les cryptosystèmes basés sur les codes utilisent le plus souvent la métrique de Hamming : le décodage consiste à trouver le mot de code le plus proche d'un mot donné pour la métrique de Hamming. Si l'on remplace les mots par des matrices, le code devient un espace vectoriel de matrices, et on parle de code matriciel. L'espace correspondant peut être muni de la métrique rang : la distance entre deux matrices est le rang de leur différence, une erreur de petit poids est une matrice de petit rang (mais pas de petit poids de Hamming). Des cryptosystèmes peuvent être définis comme pour la métrique de Hamming. Des travaux récents ont introduit les codes LRPC (Low Rank Parity Check) et ont montré que cette approche était digne d'intérêt, en particulier pour construire des schémas de signature numérique. Ce volet de l'étude est plus prospectif, et de nombreuses voies sont possibles. Nous étudierons en particulier la possibilité d'adapter les algorithmes de décodage générique en métrique de Hamming à la métrique rang.