Matrix Algebraic Systems and Application to DAGS Cryptanalysis

Systèmes algébriques matriciels et applicatiοn à la cryptanalyse de DAGS Le National Institute of Standards and Technology (NIST) a lancé en 2017 un Appel à Soumissions pour trouver des algorithmes candidats pour sécuriser les données contre les ordinateurs quantiques. Le candidat DAGS est un mécanisme d’encapsulation de clé basée sur les codes de Srivastava quasi-dyadiques. En 2018, une attaque algébrique a été publiée, permet de retrouver une partie du secret du cryptosystème. Après étude de cette modélisation, nous avons essayé de l’améliorer de différentes façons. Nous avons d’abord modifié le système donné en entrée de l’agorithme de bases de Gröbner, ce qui nous a permis de raccourcir le temps de l’attaque ainsi que d’être efficace contre un ensemble de paramètres qui n’avait pas encore été cassé. Nous avons pu noter à ce moment que le calcul des bases de Gröbner n’avait pas le même comportement que pour un système générique : les chutes de degrés sont plus nombreuses. En comparant nos observations avec les récentes publications sur les systèmes modélisant le problème MinRank, nous avons remarqué qu’ils étaient similaires. Cela nous a permis d’avoir un modèle à suivre et des formules de base pour la complexité, tout en soulignant le fait que la structure du cryptosystème DAGS réduit cette même complexité. Nous avons continué les améliorations en considérant les mineurs comme de nouvelles variables, ce qui a pour avantage de réduire la taille des matrices utilisées, comme c’est le cas pour la modélisation SupportMinors. Grâce à cette dernière modification, il est possible de trouver une base de Gröbner en utilisant seulement de l’algèbre linéaire, donc la complexité est plus faible que celle d’un algorithme de calcul de bases de Gröbner.