La cryptographie post-quantique repose sur des concepts mathématiques fondamentaux, qui offrent une résistance aux attaques d’ordinateurs quantiques. Ces systèmes sont conçus pour résoudre des problèmes particulièrement complexes, non seulement pour les ordinateurs classiques, mais aussi pour les ordinateurs quantiques, dont la puissance de calcul représente une menace majeure pour les systèmes cryptographiques traditionnels comme RSA ou ECC (Elliptic Curve Cryptography). Cet article explore les principaux fondements mathématiques et théoriques de la cryptographie post-quantique, avec des exemples concrets de problèmes mathématiques sur lesquels reposent ces nouveaux systèmes.
1. Problème du Learning with Errors (LWE)
L’un des problèmes mathématiques les plus étudiés dans le domaine de la cryptographie post-quantique est le Learning with Errors (LWE), qui fait partie de la cryptographie basée sur les réseaux. Ce problème repose sur la résolution d’un système d’équations linéaires bruitées, c’est-à-dire des équations où une petite erreur aléatoire est ajoutée. Cette erreur rend la résolution exacte du système extrêmement difficile, même avec des ordinateurs quantiques.
Exemple
Imaginez un système d’équations linéaires basées sur des valeurs secrètes :Ax=bAx = bAx=b
où AAA est une matrice publique, xxx est un vecteur secret, et bbb est le résultat des opérations sur AAA et xxx. Si nous ajoutons un bruit aléatoire (erreur) à chaque équation, obtenir xxx devient extrêmement difficile. Ce problème est fondamental pour plusieurs algorithmes post-quantiques, comme Kyber (pour le chiffrement) et Dilithium (pour les signatures numériques).
Pourquoi LWE est-il difficile ?
La présence de bruit empêche l’utilisation d’algorithmes simples pour résoudre le système, car il devient impossible de déduire directement les bonnes valeurs pour xxx. Même pour des ordinateurs quantiques, aucune solution efficace n’a encore été trouvée pour ce type de problème.
2. Problème du Vecteur le Plus Court (SVP)
Un autre fondement de la cryptographie basée sur les réseaux est le problème du vecteur le plus court (Shortest Vector Problem, ou SVP). Ce problème concerne les réseaux mathématiques (ensembles réguliers de points dans un espace euclidien) et consiste à trouver le vecteur non nul le plus court dans un réseau donné. Ce problème est connu pour être extrêmement difficile à résoudre, surtout lorsque la dimension du réseau augmente.
Exemple
Imaginez un réseau en deux dimensions comme une grille infinie de points. Le problème SVP consiste à identifier le vecteur le plus court reliant deux points de cette grille. Dans un réseau de dimension plus élevée, cette tâche devient de plus en plus difficile à mesure que le nombre de dimensions augmente.
Dans la cryptographie post-quantique, les algorithmes comme NTRU ou Lyubashevsky utilisent des problèmes liés aux réseaux pour le chiffrement et la signature numérique. La difficulté de trouver des vecteurs courts dans ces réseaux garantit la sécurité de ces systèmes.
Pourquoi SVP est-il difficile ?
Dans des espaces de dimension élevée, les réseaux deviennent très complexes, et trouver le vecteur le plus court nécessite d’explorer un espace exponentiellement grand. Les ordinateurs quantiques, bien qu’extrêmement puissants, ne peuvent résoudre ce problème efficacement.
3. Problème de Décodage de Syndrome (Code-Based Cryptography)
Le problème de décodage de syndrome est le fondement de la cryptographie basée sur les codes correcteurs d’erreurs, l’une des plus anciennes approches de cryptographie post-quantique. Proposé dès 1978 par Robert McEliece, ce type de cryptographie repose sur la difficulté de corriger un mot de code bruité sans connaître le schéma de codage sous-jacent.
Exemple
Supposons que nous ayons un mot de code envoyé via un canal bruité (par exemple, un message transmis avec des erreurs introduites par le bruit). Le récepteur connaît une matrice de parité publique, mais pour retrouver le message original, il doit corriger les erreurs introduites. Ce problème de décodage devient difficile lorsque les erreurs sont suffisamment nombreuses et aléatoires.
Le schéma McEliece est basé sur des codes correcteurs d’erreurs comme les codes de Goppa, et il est réputé inviolable même face à des ordinateurs quantiques.
Pourquoi le problème de décodage de syndrome est-il difficile ?
Décoder un message bruité sans connaître la structure interne du code correcteur est un problème complexe, surtout lorsque les erreurs introduites sont nombreuses. Le fait de devoir corriger ces erreurs rend le décodage difficile à résoudre de manière efficace, tant pour les ordinateurs classiques que pour les ordinateurs quantiques.
4. Isogénies entre Courbes Elliptiques Supersingulières
La cryptographie basée sur les isogénies repose sur un concept mathématique particulièrement complexe : les isogénies entre courbes elliptiques supersingulières. Une isogénie est une fonction qui relie deux courbes elliptiques tout en préservant leur structure géométrique.
Exemple
Supposons que deux courbes elliptiques E1E_1E1 et E2E_2E2 soient données. Une isogénie est une fonction qui prend des points sur E1E_1E1 et les “projette” sur E2E_2E2, tout en respectant les relations algébriques entre les points. Le problème est de trouver une isogénie donnée les deux courbes, ce qui est extrêmement difficile à résoudre lorsque les courbes sont supersingulières.
Le protocole SIDH (Supersingular Isogeny Diffie-Hellman) utilise ce problème pour sécuriser l’échange de clés. Il repose sur la difficulté de trouver une isogénie entre deux courbes sans connaître la structure interne des isogénies utilisées.
Pourquoi les isogénies sont-elles difficiles à exploiter ?
Calculer une isogénie entre deux courbes elliptiques est un problème mathématique très complexe, en particulier lorsque les courbes sont de type supersingulier. Aucun algorithme quantique efficace n’a encore été découvert pour résoudre ce problème, ce qui en fait une base solide pour la cryptographie post-quantique.
5. Polynômes Multivariés (Cryptographie Multivariée)
La cryptographie multivariée repose sur des systèmes d’équations polynomiales multivariées sur des corps finis. Il s’agit de trouver une solution à ces équations, ce qui est un problème particulièrement difficile, surtout lorsque le nombre d’équations et de variables est grand.
Exemple
Imaginez un système d’équations polynomiales comme :
P1(x1,x2,…,xn)=0
P2(x1, x2, …, xn) = 0
Résoudre ce système consiste à trouver les valeurs des variables x1,x2,…,xnx1, x2, …, xnx1,x2,…,xn qui satisfont toutes les équations. Pour des systèmes de grande taille, cette tâche devient impraticable avec des méthodes de résolution classiques.
Des schémas de signature numérique, tels que Rainbow ou UOV (Unbalanced Oil and Vinegar), exploitent cette difficulté pour garantir une sécurité robuste contre les attaques quantiques.
Pourquoi les systèmes polynomiaux multivariés sont-ils difficiles ?
Résoudre un système d’équations polynomiales multivariées est un problème NP-complet, ce qui signifie qu’il est très difficile à résoudre dans des cas généraux, même avec des algorithmes avancés. Cela en fait une base fiable pour la cryptographie post-quantique.
Conclusion
Les fondements mathématiques et théoriques de la cryptographie post-quantique sont divers et robustes, basés sur des problèmes reconnus pour leur complexité, tant pour les ordinateurs classiques que quantiques. Du problème du vecteur le plus court (SVP) aux isogénies entre courbes elliptiques, en passant par le décodage de syndrome et les polynômes multivariés, ces approches offrent des solutions prometteuses pour garantir la sécurité des systèmes à l’ère des ordinateurs quantiques.