L’avènement des ordinateurs quantiques, capables de casser les systèmes cryptographiques traditionnels comme RSA ou ECC, a poussé la communauté scientifique à développer de nouvelles méthodes de protection de l’information. Ces méthodes, regroupées sous le terme de cryptographie post-quantique, sont conçues pour résister aux attaques d’ordinateurs quantiques tout en restant utilisables par des systèmes classiques. Les algorithmes post-quantiques se divisent en plusieurs familles, chacune reposant sur des problèmes mathématiques spécifiques. Voici un aperçu des principales familles d’algorithmes post-quantiques, accompagnées d’exemples concrets.
1. Cryptographie Basée sur les Réseaux (Lattice-Based Cryptography)
Les algorithmes basés sur les réseaux exploitent des problèmes liés à des réseaux euclidiens (ensembles de points réguliers dans l’espace) pour créer des systèmes de chiffrement et de signature résistants aux attaques quantiques. Ces problèmes, comme le Learning with Errors (LWE) et le Shortest Vector Problem (SVP), sont réputés difficiles à résoudre, même avec un ordinateur quantique.
Exemple : Kyber
Kyber est un algorithme de chiffrement à clé publique qui utilise le problème LWE pour générer des clés sécurisées. Il a été sélectionné comme finaliste dans le processus de standardisation du NIST. Kyber est utilisé pour l’échange de clés dans des protocoles de communication, comme TLS, garantissant que les communications restent privées même en présence d’un attaquant équipé d’un ordinateur quantique.
Exemple : Dilithium
Dilithium est un schéma de signature numérique basé sur le même problème de LWE. Il permet de générer des signatures numériques qui restent inviolables par des ordinateurs quantiques. Il est également finaliste dans le processus du NIST et est réputé pour offrir un bon compromis entre sécurité, taille des signatures et performances.
Pourquoi les réseaux ?
Les réseaux deviennent complexes en haute dimension, rendant les problèmes de cryptographie basés sur eux très difficiles à résoudre, même avec des ordinateurs quantiques. La sécurité repose sur l’impossibilité de trouver des vecteurs courts dans ces réseaux ou de résoudre des systèmes d’équations bruités.
2. Cryptographie Basée sur les Codes Correcteurs d’Erreurs (Code-Based Cryptography)
Les algorithmes basés sur les codes correcteurs d’erreurs utilisent des problèmes issus de la théorie des codes pour garantir la sécurité des systèmes. Le problème clé ici est le problème de décodage de syndrome, qui consiste à corriger un message bruité sans connaître la structure interne du code utilisé pour encoder ce message.
Exemple : McEliece
Proposé en 1978 par Robert McEliece, cet algorithme de chiffrement repose sur des codes de Goppa pour protéger les données. La sécurité du système est basée sur la difficulté de décoder un message bruité, un problème complexe même pour des ordinateurs quantiques. Bien que McEliece nécessite des clés publiques volumineuses, il reste l’un des schémas les plus robustes contre les attaques quantiques.
Exemple : BIKE (Bit Flipping Key Encapsulation)
BIKE est un schéma d’encapsulation de clés, conçu pour sécuriser l’échange de clés dans les communications. Il est basé sur des codes cycliques et garantit une sécurité robuste face aux attaques quantiques, tout en étant plus efficace en termes de taille de clé par rapport à McEliece.
Pourquoi les codes correcteurs d’erreurs ?
Les problèmes liés à la correction d’erreurs sont bien étudiés depuis des décennies, et ils sont réputés difficiles à résoudre sans connaître les propriétés internes des codes utilisés. Cela en fait une base solide pour la cryptographie post-quantique.
3. Cryptographie Basée sur les Isogénies (Isogeny-Based Cryptography)
Les isogénies sont des fonctions qui relient deux courbes elliptiques entre elles tout en conservant leurs propriétés algébriques. Les algorithmes basés sur les isogénies exploitent la difficulté de calculer ces isogénies pour créer des systèmes cryptographiques inviolables.
Exemple : SIDH (Supersingular Isogeny Diffie-Hellman)
SIDH est un algorithme conçu pour sécuriser l’échange de clés à l’aide d’isogénies entre courbes elliptiques supersingulières. Ce protocole fonctionne comme une extension du célèbre Diffie-Hellman, mais en utilisant des courbes elliptiques spécifiques, ce qui le rend résistant aux attaques quantiques.
Exemple : SIKE (Supersingular Isogeny Key Encapsulation)
SIKE est une variante de SIDH qui encapsule des clés pour garantir la confidentialité des échanges. SIKE se distingue par ses petites tailles de clé, le rendant très adapté aux environnements où la bande passante ou la mémoire sont limitées, comme les appareils mobiles ou les objets connectés (IoT).
Pourquoi les isogénies ?
Le calcul d’isogénies entre courbes elliptiques est un problème mathématique extrêmement complexe, sans solution efficace connue pour les ordinateurs quantiques. Cette complexité garantit une sécurité élevée, même dans des systèmes avec des ressources limitées.
4. Cryptographie Multivariée (Multivariate-Based Cryptography)
Les algorithmes multivariés reposent sur des systèmes d’équations polynomiales multivariées sur des corps finis. Résoudre ces systèmes est un problème réputé difficile, surtout lorsque le nombre d’équations et de variables est élevé.
Exemple : Rainbow
Rainbow est un schéma de signature numérique qui repose sur la résolution difficile d’un système d’équations polynomiales. Il divise ces équations en plusieurs couches pour augmenter la sécurité. Rainbow est finaliste dans le processus du NIST et se distingue par ses signatures rapides et son efficacité dans divers environnements.
Exemple : UOV (Unbalanced Oil and Vinegar)
UOV est un autre schéma de signature multivariée qui utilise deux types de variables (l’huile et le vinaigre) pour créer des signatures résistantes aux attaques. UOV est l’une des variantes les plus simples et sécurisées de la cryptographie multivariée.
Pourquoi les polynômes multivariés ?
Les systèmes d’équations polynomiales multivariées sont NP-difficiles à résoudre, ce qui signifie qu’ils sont résistants aux attaques tant classiques que quantiques. Cette complexité garantit la sécurité des signatures et des systèmes basés sur cette méthode.
5. Cryptographie Basée sur les Fonctions de Hachage (Hash-Based Cryptography)
Les algorithmes basés sur les fonctions de hachage utilisent la sécurité prouvée des fonctions de hachage cryptographiques pour créer des signatures numériques résistantes aux ordinateurs quantiques. Contrairement aux autres méthodes, ces systèmes ne reposent pas sur des problèmes algébriques, mais sur la difficulté de trouver des collisions dans les fonctions de hachage.
Exemple : SPHINCS+
SPHINCS+ est un schéma de signature sans état qui utilise des arbres de Merkle et des signatures à usage unique (One-Time Signatures, OTS). La sécurité de SPHINCS+ repose uniquement sur la solidité des fonctions de hachage, ce qui en fait un candidat robuste pour les applications où la sécurité à long terme est cruciale.
Exemple : XMSS (eXtended Merkle Signature Scheme)
XMSS est un autre schéma de signature basé sur des arbres de Merkle, conçu pour offrir une sécurité post-quantique tout en garantissant que les signatures numériques sont efficaces et ne nécessitent pas de gestion d’état complexe.
Pourquoi les fonctions de hachage ?
Les fonctions de hachage sont bien étudiées et largement utilisées dans la cryptographie moderne. Elles sont réputées pour être résistantes aux attaques, et la création de collisions dans ces fonctions est un problème difficile pour les ordinateurs classiques et quantiques.
Conclusion
La cryptographie post-quantique repose sur une variété de familles d’algorithmes, chacune exploitant des problèmes mathématiques difficiles à résoudre, même pour les ordinateurs quantiques. Que ce soit par des réseaux, des codes correcteurs d’erreurs, des isogénies, des polynômes multivariés ou des fonctions de hachage, ces familles offrent des solutions robustes pour protéger les données et les communications à long terme. À mesure que les ordinateurs quantiques se rapprochent, ces algorithmes deviendront essentiels pour garantir la sécurité de l’ère numérique.