La sécurité des protocoles cryptographiques repose sur la difficulté présumée de problèmes algorithmiques. A ce jour, les meilleurs problèmes pouvant servir de fondation à une cryptographie résistante aux ordinateurs quantiques sont issus des réseaux euclidiens, une structure mathématique définie comme un ensemble de vecteurs de l’espace générés par les combinaisons entières d’un nombre fini de vecteurs réels linéairement indépendants (sa base). Un exemple typique de problème de sécurité relié est le Shortest Vector Problem (SVP), qui s’énonce de la manière suivante : « Étant donnée une base d’un réseau euclidien en dimension n, trouver un vecteur non nul le plus court ».
Pour des raisons d’efficacité, ces problèmes sont souvent restreints à des réseaux issus de la théorie des nombres, dit structurés. Les hypothèses de sécurité relatives à ces réseaux particuliers étant différentes de celles des réseaux non structurés, il est nécessaire de les étudier spécifiquement.
Nous étudions le cas des modules NTRU et uSVP en rang 2, prouvant que le problème SVP est équivalent sur ces deux familles de réseaux, et montrant également une réduction pire cas vers cas moyen pour les réseaux uSVP en rang 2.
Nous prouvons ensuite que résoudre SVP sur un idéal premier de petite norme n’est pas plus facile que de résoudre SVP sur un idéal arbitraire.
Enfin, nous nous intéressons à un problème issu de la théorie des nombres : l’étude d’un algorithme quantique de calcul du groupe des S-unités d’un corps de nombres. Nous prouvons que ce calcul est réalisable en temps et espace polynomial quantique, avec des bornes précises sur la complexité.
Gratuit
Disciplines