Résumé
Kyber base sa sécurité sur le problème Module-LWE (Learning With Errors sur modules), une variante du LWE classique défini par Regev en 2005. Comprendre LWE, c'est comprendre pourquoi Kyber est sécurisé et, plus important, jusqu'à quand il pourrait l'être.
Le Problème LWE
Étant donné un secret s, une matrice A et un vecteur d'erreurs e :
s = vecteur secret (dimension n)
A = matrice aléatoire (m × n)
e = vecteur d'erreur petit (échantillonné d'une distribution χ)
b = A·s + e (module q)
Problème de recherche (Search-LWE) : Étant donnés (A, b), trouver s.
Problème de décision (Decision-LWE) : Étant donnés (A, b), distinguer si b = A·s + e ou si b est uniformément aléatoire.
La sécurité dépend du fait que, bien que A·s soit déterministe, l'erreur e rend le système difficilement inversible. Sans e, ce serait de l'algèbre linéaire triviale.
Pourquoi c'est dur
Récupérer s à partir de (A, b) est équivalent à résoudre des problèmes de réseaux (latices) qui sont NP-difficiles dans le pire des cas. La réduction de Regev (2005) a montré que briser LWE est au moins aussi dur que certains problèmes de réseaux dans le pire des cas (GapSVP, SIVP).
Module-LWE
Kyber utilise Module-LWE, où A et s ne sont pas des entiers scalaires mais des éléments d'un module sur un anneau de polynômes :
R_q = Z_q[x] / (x^n + 1)
Où n = 256 pour Kyber. La matrice A a des entrées dans R_q et la dimension k × k (où k = 2, 3, 4 selon le niveau de sécurité).
A ∈ R_q^{k×k}, s ∈ R_q^{k}, e ∈ R_q^{k}
b = A·s + e
Avantage sur LWE standard : Module-LWE offre un équilibre entre efficacité (les anneaux permettent une multiplication rapide via NTT) et sécurité (le module k contrôle la dimension sans croître au carré).
Pourquoi un module et pas un anneau complet ?
Ring-LWE (utilisé par NewHope, par exemple) opère sur un seul anneau (R_q). Module-LWE interpole entre LWE standard et Ring-LWE :
| Schéma | Dimension | Efficacité | Sécurité conservatrice |
|---|---|---|---|
| LWE standard | n × k |
Faible | Élevée |
| Ring-LWE | n |
Élevée | Moyenne |
| Module-LWE | n × k |
Élevée | Élevée |
La Distribution d'Erreur
Kyber utilise une distribution binomiale centrée CBD(η) au lieu d'une gaussienne discrète. Cela simplifie l'implémentation (pas d'échantillonnage par table) et évite les attaques de temporisation.
Pr[ e = x ] = (C(2η, η+x)) / 2^(2η)
Pour ML-KEM-512 : η = 2. Pour ML-KEM-768 et 1024 : η = 3.
Le Module q = 3329
Le choix de q = 3329 n'est pas accidentel :
- C'est un nombre premier tel que
q ≡ 1 (mod 2n)pourn = 256, ce qui permet d'utiliser NTT (Number Theoretic Transform) pour une multiplication rapide dansR_q. - Il est suffisamment petit pour que les ciphertexts et les clés soient compacts.
- Il est suffisamment grand pour que l'erreur ne déborde pas et ne cause pas de déchiffrements incorrects.
La Conjecture Centrale
La sécurité de Kyber (et de toute la cryptographie basée sur les réseaux) repose sur la conjecture que :
Il n'existe pas d'algorithme quantique (ni classique) qui résolve Module-LWE pour les paramètres de Kyber en temps polynomial.
Cette conjecture est plausible mais non démontrée. L'histoire de la cryptographie enseigne que les conjectures de dureté échouent parfois. Ce qui distingue LWE de RSA/ECC est qu'on ne connaît pas d'analogue quantique de Shor pour les réseaux — mais cela ne signifie pas qu'il ne puisse pas être découvert.
Références
- Regev, O. (2005). "On lattices, learning with errors, random linear codes, and cryptography." STOC 2005.
- Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM." EuroS&P 2018.
- Langlois, A. & Stehlé, D. (2015). "Worst-case to average-case reductions for module lattices." Designs, Codes and Cryptography.