# Cryptographie post-quantique

La cryptographie post-quantique est une branche de la cryptographie visant à garantir la sécurité de l'information face à un attaquant disposant d'un calculateur quantique. Cette discipline est distincte de la cryptographie quantique, qui vise à construire des algorithmes cryptographiques utilisant des propriétés physiques, plutôt que mathématiques, pour garantir la sécurité.
En l'effet, les algorithmes quantiques de Shor, de Grover et de Simon étendent les capacités par rapport à un attaquant ne disposant que d'un ordinateur classique. S'il n'existe pas à l'heure actuelle de calculateur quantique représentant une menace concrète sur la sécurité des cryptosystèmes déployés, ces algorithmes permettent conceptuellement de résoudre certains problèmes calculatoires sur lesquels sont fondés plusieurs primitives populaires.

## Algorithmes quantiques et cryptographie

En 1995, Peter Shor a publié un algorithme permettant de résoudre le problème du logarithme discret et le problème de la factorisation des entiers. Cet algorithme, utilisant les spécificités d'un calculateur quantique (dont on n'avait alors pas encore construit de prototypes), produit une réponse en temps polynomial. En comparaison, les meilleurs algorithmes classiques connus pour ces problèmes ont une complexité exponentielle en général, et sous-exponentielle mais sur-polynomiale pour les corps finis. En résumé, pour ces deux problèmes, aucun algorithme classique efficace n'est connu, mais puisqu'un algorithme quantique efficace est disponible, on dit qu'ils appartiennent à la classe de complexité BQP.
En conséquence, les constructions cryptographiques dont la sécurité repose sur le problème du logarithme discret (notamment l'échange de clé de Diffie-Hellman et la signature ECDSA), ou sur le problème de la factorisation d'entiers (notamment la signature RSA) seraient vulnérables à un attaquant disposant d'un calculateur quantique suffisamment grand et fiable.
L'algorithme de Grover, quant à lui, améliore de manière faible mais générique l'efficacité des problèmes de recherche. Contrairement à l'algorithme de Shor, il ne dote pas l'attaquant d'un avantage exponentiel, mais seulement quadratique, c'est-à-dire qu'il divise le niveau de sécurité d'un problème de recherche par deux.

## Cryptographie symétrique

En 2018, le principal algorithme quantique affectant les cryptosystèmes symétriques est l'algorithme de Grover. Cet algorithme est générique, c'est-à-dire qu'il s'applique en principe à toute primitive indépendamment de sa construction, et permet d’effectuer une recherche parmi $n$ éléments en temps $O(n^{1/2})$ à la place de $O(n)$ dans le cas classiques.
Par conséquent, la sécurité des algorithmes n'est affectée que par un facteur 2. Autrement dit, pour atteindre la même sécurité que dans le modèle classique, il suffit de doubler la taille des clefs utilisées, ce qui ne pose aucune difficulté conceptuelle, mais peut nécessiter des ajustement techniques. En effet, de nombreux algorithmes symétriques sont conçus et analysés avec une taille de clef fixe.
Dans certains cas, il est possible qu'une construction symétrique soit sujette à des attaques spécialisées par l'algorithme de Simon, ce qui s'est produit pour un schéma proposé à la compétition CAESAR. Enfin, l'algorithme d'Ambainis permet de gagner un facteur polynomial la recherche de collisions.

## Cryptographie à clef publique

Pour les problèmes de la factorisation d'un entier $n$, le meilleur algorithme classique connu est en complexité temporelle heuristique $L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right].$ Ce qui permet d'appuyer la sécurité d'algorithmes tels que la signature de Rabin à 128 bits en utilisant un module $n$ de 3072 bits. La sécurité d’une signature RSA utilisant un tel module est alors d'au plus 128 bits face à un attaquant classique. Le meilleur algorithme quantique connu possède une complexité quadratique en $n$ ; adapter la sécurité de RSA à ce contexte serait possible, mais requiert des tailles de clef phénoménales, de l'ordre du téraoctet. En pratique, au-delà des problèmes de stockage et de transmission de telles clefs et de tels messages, l'inconvénient est que toutes les opérations sont ralenties d'autant. De plus, il n'existe pas de preuves que l'algorithme de Shor soit le plus efficace possible : chercher à sauver RSA dans ce contexte est une course perdue d'avance.
De manière générale, les algorithmes à clef publique reposant sur la factorisation peuvent être considérés cassés par un attaquant quantique : RSA, Paillier, Naccache-Stern, Rabin, Benaloh, Blum-Goldwasser, Damgård–Jurik, Goldwasser-Micali, Okamoto-Uchiyama, Schmidt-Samoa.
Le problème du logarithme discret peut aussi être résolu par une variante du même algorithme, de sorte que les algorithmes à clef publique dont la sécurité repose sur l'hypothèse de la difficulté du logarithme discret sont également cassés par l'algorithme de Shor. Contrairement au cas classique, où le crible du corps de nombres s'applique dans les corps finis mais pas en général dans le groupe des points rationnels d'une courbe elliptique, l'approche de l'algorithme de Shor ne fait aucune différence.
Ainsi, les algorithmes à clef publique reposant sur la difficulté du calcul d'un logarithme discret peuvent être considérés cassés par un attaquant quantique : Diffie-Hellman, Cramer-Shoup, DSA et ECDSA (aussi ses précurseurs Schnorr et ElGamal, et ses variantes comme EdDSA), SRP, etc.
D'autres problèmes classiquement difficiles reposant sur des problèmes d'arithmétique modulaire sont eux aussi affectés par des variantes de l'algorithme de Shor.

## Candidats post-quantiques

Plusieurs constructions cryptographiques ne sont pas affectées par les attaques discutées ci-dessus, et constitueraient une solution facile de substitution. Par exemple, on peut espérer construire l'équivalent de constructions à clef publique en n'utilisant que des primitives symétriques. Mais le risque demeure qu'un algorithme quantique (qui n'a pas encore été découvert) puisse les casser.
La communauté cryptographique s'est donc tournée vers des approches qu'un attaquant quantique ne peut pas casser. La logique générale est de construire des primitives cryptographiques à partir de problèmes NP-complets, dont on sait qu'un ordinateur quantique (limité à la classe BQP) ne peut les résoudre plus efficacement qu'un ordinateur classique, sous l'hypothèse que P ≠ NP. Les candidats les plus sérieux reposent sur les problèmes suivants :
* Problèmes de vecteurs courts dans les réseaux euclidiens (1996) ;
* Décodage de codes linéaires aléatoires (1978) ;
* Inversion de polynômes multivariés (1995) ;
* Navigation dans les isogénies des courbes elliptiques supersingulières (2006) ;
* Inversion de fonctions de hachage (1978).
Le prix à payer est une perte d'efficacité et des clefs plus larges. Pour essayer de gagner sur ces terrains, plusieurs propositions ont été faites qui n'ont qu'heuristiquement la sécurité d'un problème NP. La conséquence est que parfois, ces variantes s'avèrent vulnérables à des attaques classiques (ou quantiques).
En 2017, le NIST a annoncé une compétition visant à établir une standardisation des algorithmes cryptographiques post-quantiques. Ce protocole de standardisation, a fait émerger 4 candidats pour la standardisation en juillet 2022: un schéma d’encapsulation de clefs, CRYSTALS-Kyber (en) dont la sécurité repose sur la sécurité de problèmes de réseaux euclidiens (structurés), ainsi que trois schémas de signature numérique, CRYSTALS-Dilithium, Falcon (en) et SPHINCS+ (en), les deux premiers reposant sur des hypothèses de sécurité sur les réseaux euclidiens (structurés) et le dernier étant une construction fondée sur les fonctions de hachage.

### Réseaux euclidiens

Les premières méthodes pour produire des problèmes difficiles en cas moyen (une propriété importante en cryptographie, c'est ce qui fait par exemple que n'importe quel problème NP-Complet ne peut pas être utilisé en cryptographie étant donné qu'il n'est pas toujours évident de produire une instance difficile) ont été proposées par Ajtai en 1996, mais c'est Oded Regev qui a introduit en 2005 le problème de l'apprentissage avec erreur (LWE en anglais, pour learning with errors), accompagné d'une réduction quantique depuis les problèmes difficiles connus (recherche du vecteur le plus court, et recherche du vecteur le plus proche). Ces analyses ont été ensuite améliorées par Chris Peikert en 2009.
C'est un domaine de recherche actif depuis les travaux de Regev en 2005, et de nombreuses primitives avancées comme le chiffrement complètement homomorphe ne sont possibles que dans ce contexte. Cela a été rendu possible par l'introduction de la délégation de bases, permettant de générer une base aléatoire pour un sur-réseau de celui de travail. Cette méthode a été introduite par Gentry, Peikert et Vaikuntanathan en 2008, puis raffinée par Cash, Hofheinz, Kiltz et Peikert en 2010 puis par Micciancio et Peikert en 2012.
Cette technique permettant de débloquer ces fonctionnalités intéressantes pose néanmoins un problème de performances, étant peu efficace en pratique. En revanche, il existe des cryptosystèmes à base de réseaux euclidiens qui proposent des solutions efficaces, comme NTRU.

#### Hypothèses de sécurité

La cryptographie sur les réseaux repose principalement sur les hypothèses standards suivantes :
* L’apprentissage avec erreurs (learning with errors ou LWE en anglais), qui consiste à distinguer la distribution $(\mathbf {A} ,\mathbf {A} \cdot \mathbf {s} +\mathbf {e} )$ de la distribution $(\mathbf {A} ,\mathbf {r} )$ pour $\mathbf {A} \in \mathbb {Z} _{q}^{m\times n},\mathbf {s} \in \mathbb {Z} _{q}^{n},\mathbf {r} \in \mathbb {Z} _{q}^{m}$ prises uniformément, et $\mathbf {e} \in \mathbb {Z} ^{m}$ tirée suivant une gaussienne d'écart-type σ. Ce problème est paramétré par n, q, et α = σ/q dont le choix va faire varier la difficulté du problème.
* La recherche d’une solution entière courte (en) (short integer solution ou SIS en anglais), qui consiste à calculer un vecteur solution $\mathbf {s} \in \mathbb {Z} ^{m}$ tel que $\mathbf {A} \cdot \mathbf {s} =\mathbf {0} {\bmod {q}}$ et $\|\mathbf {s} \|_{2}\leq \beta$ étant donné une matrice $\mathbf {A} \in \mathbb {Z} _{q}^{n\times m}$. Ce problème est paramétré par n, q et β, et possède une variante inhomogène: ISIS (pour Inhomogeneous SIS), où au lieu de résoudre une équation linéaire homogène (ou le second terme est nul), on résout l'équation $\mathbf {A} \cdot \mathbf {s} =\mathbf {u}$ pour un vecteur cible $\mathbf {u} \in \mathbb {Z} _{q}^{n}$.
Ces hypothèses ont été introduites par Oded Regev dans son article fondateur. Elles ont leur pendant sur des anneaux de polynômes (Ring-LWE (en) par exemple), qui sont plus compactes, mais qui souffrent d’une cryptanalyse moins poussée.

#### Constructions

Parmi les constructions reposant sur des hypothèses sur la difficulté des problèmes sur les réseaux euclidiens, on peut citer :
* Le chiffrement NTRU.
* Le schéma de signature BLISS (en).
* Le chiffrement fondé sur l'identité de Gentry, Peikert et Vaikuntanathan dans le modèle de l'oracle aléatoire, ou celui d'Agrawal, Boneh et Boyen dans le modèle standard.
* Le chiffrement complètement homomorphe de Gentry, Sahai et Waters.

### Codes correcteurs d'erreur

La cryptographie sur les codes est une autre solution pour concevoir des cryptosystèmes post-quantiques introduite en 1978 par Robert McEliece. Le problème difficile sous-jacent venant de la théorie des codes provient du fait qu’il est difficile, étant donné une famille de codes, de déterminer quel code a été utilisé pour le codage, la clef privée étant la matrice génératrice du code (permettant de corriger l'erreur), et la clef publique étant une version randomisée de cette matrice (pour le cryptosystème de McEliece), permettant de générer des mots du code, sans pouvoir décoder. Ainsi pour chiffrer un message, l'expéditeur rajoute une erreur à son message encodé, ce qui le rend inintelligible pour une personne ne disposant pas de la matrice génératrice.
La principale difficulté de la cryptographie sur les codes correcteurs étant de trouver une famille de codes efficaces et exhibant la difficulté nécessaire. Une famille qui possède ces propriétés sont les codes de Goppa.

#### Hypothèses de sécurité

Le cryptosystème de McEliece est prouvé sûr sous l'hypothèse du décodage de syndrome (syndrome decoding problem ou SDP en anglais), qui est similaire à la recherche d’une solution inhomogène entière courte mais dans le cadre des codes. Autrement dit, étant donné une matrice $\mathbf {H} \in \mathbb {F} _{2}^{m\times n}$, un entier $w\leq n$ et un syndrome $\mathbf {u} \in \mathbb {F} _{2}^{m}$, le problème consiste à trouver un vecteur $\mathbf {x} \in \mathbb {F} _{2}^{n}$ solution de l'équation $\mathbf {H} \cdot \mathbf {x} =\mathbf {u}$ et tel que son poids de Hamming soit fixé à $w$.

### Polynômes multivariés

La cryptographie à base de polynômes multivariés repose sur le fait qu'il est difficile de résoudre des systèmes polynomiaux à plusieurs variables (appelés aussi multivariés). Pour passer de cette observation à un système permettant de construire des primitives cryptographique, des tentatives de réalisations ont été proposées comme les équations sur un corps caché.
Des attaques efficaces ont été proposées sur de nombreuses réalisations (Kipnis-Shamir'99, Faugère-Joux'03, Beullens'22), mais il reste le mélange non-équilibré d'huile et de vinaigre (en) (en anglais UOV pour Unbalanced Oil and Vinegar) et ses variantes.

### Recherche d'isogénie de courbes supersingulières

Une isogénie est un morphisme de groupe surjectif et de noyau fini entre deux courbes elliptiques. L'introduction du problème de la recherche d'isogénie de courbes (c'est-à-dire qu'étant donné deux courbes elliptiques $E_{1}$ et $E_{2}$ telles qu'il existe une isogénie $\varphi$ telle que $\varphi (E_{1})=E_{2}$, trouver $\varphi$) comme étant un problème difficile date de 2006, et a été proposé par Rostovtsev et Stolbunov pour faire de l'échange de clefs. Mais cette proposition a été cryptanalysée par Childs, Jao et Soukharev qui ont proposé une attaque quantique efficace.
Cette attaque a été réparée en 2011 par Jao et de Feo qui ont proposé l'utilisation de courbes supersingulières. La raison étant que l'attaque repose principalement sur la commutativité de la composition des isogénies dans le cas général; propriété qui n'est pas vérifiée pour les courbes supersingulières.
Étant une solution jeune comparée à ses concurrents comme la cryptographie à base de code (1978), ou la cryptographie sur les réseaux euclidiens (1996), elle possède encore peu d'applications, mais offre des tailles de clefs très compétitives comparées à ses concurrents.

## Comparaison de tailles de clefs

La taille des clefs est importante pour évaluer l'efficacité des systèmes de chiffrement, et s’avère critique sur les systèmes embarqués comme les cartes à puces où la mémoire est critique. Il existe d'autres métriques, comme les temps pour chiffrer/déchiffrer, mais elles sont difficiles à évaluer puisqu’il est possible d’avoir des performances incomparables par l'utilisation de circuits programmables par exemple.
Une caractéristique des cryptosystèmes post-quantiques est de fournir des clefs plus grandes que celles utilisées par leurs concurrents (comme le chiffrement El Gamal sur courbes elliptiques par exemple).
Comparaison de tailles de clefs :
| Algorithme | Type d'hypothèses | Taille de la clef publique (en bits) | Taille de la clef privée (en bits) |
| Ring-LWE (en) | Réseaux euclidiens | 6 595 | 14 000 |
| NTRU | Réseaux euclidiens | 6 130 | 6 743 |
| Rainbow | Polynômes multivariés | 991 000 | 740 000 |
| Hash signature | Fonctions de hachage | 36 000 | 36 000 |
| McEliece sur des codes de Goppa | Codes correcteurs | 8 373 911 | 92 027 |
| McEliece sur des codes MDPC quasi-cycliques | Codes correcteurs | 65 542 | 4 384 |
| SIDH (en) | Isogénie de courbes | 6 144 | 6 144 |
Ces clefs sont évaluées pour un niveau de sécurité de 128 bits face à un attaquant quantique (256 bits face à un attaquant classique). À titre équivalent, un module RSA pour 256 bits de sécurité classique est estimé à 15360 bits (clef publique).