ML-KEM (Kyber)

ML-KEM est normalisé par la FIPS 203 et déployé aujourd'hui dans les navigateurs. C'est le schéma post-quantique que vos étudiants rencontreront le plus sûrement en production. Ce chapitre le construit brique par brique, en partant d'un objet que le chapitre précédent a rendu presque évident.

Un KEM, et pourquoi pas un chiffrement

Première clarification, souvent sautée. ML-KEM ne chiffre pas de messages. C'est un mécanisme d'encapsulation de clé — trois algorithmes :

Encaps ne prend aucun message en entrée. Elle produit une clé symétrique $K$ tirée au hasard et un chiffré $c$ qui permet au détenteur de $dk$ de la retrouver. On chiffre ensuite les vraies données avec $K$ et un AEAD.

Pourquoi cette forme plutôt qu'un chiffrement à clé publique ordinaire ? Parce qu'elle est plus simple à sécuriser. Un KEM n'a pas à gérer de bourrage, ni de messages de taille variable, ni de messages choisis par l'attaquant. Sa seule obligation est que $K$ soit indistinguable d'une clé aléatoire. En pratique, c'est aussi la seule chose dont les protocoles ont besoin : TLS, SSH et les autres veulent une clé de session, pas un chiffrement asymétrique de charge utile.

Le chiffrement sous-jacent

Sous ML-KEM se trouve un chiffrement à clé publique, appelé K-PKE, qui est du Module-LWE à peine déguisé.

Génération. Tirer $A$ pseudo-aléatoire de taille $k \times k$ sur $R_q$, et deux vecteurs courts $s$ et $e$. Publier $t = As + e$, garder $s$.

Chiffrement de $m$. Tirer $r$, $e_1$, $e_2$ courts, et calculer

Déchiffrement. Calculer $v - s^{T} u$ et arrondir chaque coefficient au multiple de $q/2$ le plus proche.

Le calcul décisif tient en deux lignes :

Le message est encodé en plaçant chaque bit soit près de 0, soit près de $q/2$. Le terme d'erreur est petit ; tant qu'il reste sous $q/4$, l'arrondi retombe sur le bon bit. Tout le dimensionnement de ML-KEM consiste à garder ce terme d'erreur sous $q/4$.

La compression, et le bruit qu'elle achète

Publier $u$ et $v$ avec 12 bits par coefficient donnerait des chiffrés inutilement gros. On les compresse en jetant des bits de poids faible :

La décompression rend une valeur approchée, à $q/2^{d+1}$ près. Cette erreur d'arrondi s'ajoute au budget de bruit — c'est pour cela que la compression n'est pas gratuite, et qu'on ne peut pas compresser autant qu'on voudrait.

Le point à faire remarquer en cours : $u$ et $v$ ne sont pas compressés au même taux. $u$ garde 10 ou 11 bits, $v$ seulement 4 ou 5. Ce n'est pas une inconséquence — $v$ ne transporte qu'un bit de message par coefficient, décodé en comparant à $q/2$, donc une erreur de cent unités y est sans conséquence. Chaque terme est compressé selon ce qu'il transporte.

De IND-CPA à IND-CCA2 : Fujisaki-Okamoto

Le K-PKE ci-dessus est IND-CPA, et seulement IND-CPA. Il est malléable : un attaquant qui modifie un chiffré valide obtient un chiffré qui se déchiffre encore, en un message différent mais lié. Contre un attaquant capable de soumettre des chiffrés au déchiffrement, c'est fatal.

La transformation de Fujisaki-Okamoto, dans sa variante avec rejet implicite, corrige cela avec une idée simple. On ré-encapsule :

1. déchiffrer $c$ pour obtenir $m'$ ;
2. dériver l'aléa $r'$ à partir de $m'$ lui-même — le chiffrement devient déterministe ;
3. rechiffrer $m'$ avec $r'$, obtenant $c'$ ;
4. si $c' = c$, renvoyer la clé ; sinon, renvoyer une clé bidon dérivée d'un secret interne.

Le test $c' = c$ prouve que $c$ a réellement été produit par la procédure d'encapsulation. Un chiffré fabriqué ne peut pas passer, puisque l'attaquant devrait deviner $m'$ à l'avance.

Le point délicat est la dernière ligne. On ne renvoie pas d'erreur : on renvoie une clé pseudo-aléatoire, fausse mais indistinguable d'une vraie. C'est le rejet implicite. Dire « échec » créerait un oracle : l'attaquant apprendrait quels chiffrés sont valides, et c'est exactement ce dont il a besoin. Le chapitre 11 en donne la preuve, et le chapitre 12 montre comment une implémentation bavarde rouvre l'oracle par le temps d'exécution.

Les trois jeux de paramètres

Notez ce que la table ne contient pas : ni $n$, ni $q$, ni l'anneau. Ils sont identiques pour les trois niveaux. Seul $k$ change, avec les taux de compression. C'est le bénéfice d'implémentation du Module-LWE annoncé au chapitre précédent.

Le taux d'échec de déchiffrement

ML-KEM peut échouer. C'est déroutant pour qui vient de RSA, et c'est structurel : si le terme de bruit dépasse $q/4$, un bit est mal décodé et la clé obtenue est fausse.

Les probabilités affichées ci-dessus — de l'ordre de $2^{-164}$ — rendent l'événement inobservable : il ne se produira jamais, sur aucun parc, pendant aucune durée. Mais elles ne sont pas nulles, et cela a deux conséquences qu'il faut énoncer.

D'abord, ce taux est un paramètre de sécurité, pas seulement de fiabilité. Un attaquant capable de provoquer des échecs, en soumettant des chiffrés spécialement construits, apprendrait de l'information sur le secret — chaque échec est une inégalité satisfaite par $s$. C'est l'attaque par échec de déchiffrement, et c'est pourquoi le taux doit être astronomiquement bas plutôt que simplement négligeable en pratique.

Ensuite, cela impose que la ré-encapsulation FO soit implémentée en temps constant, échec compris. Une implémentation qui met plus de temps sur un échec que sur un succès restaure exactement l'oracle qu'on cherchait à fermer.

À vous

// La compression de ML-KEM : jeter des bits de poids faible pour réduire
// le chiffré, en acceptant l'erreur que cela introduit.

const q = 3329;

// Compress_d : ramène un élément de Z_q sur d bits.
function compresser(x, d) {
  // À COMPLÉTER — arrondir (2^d / q) · x, puis réduire modulo 2^d.
  return 0;
}

// Decompress_d : retour approximatif vers Z_q.
function decompresser(y, d) {
  // À COMPLÉTER — arrondir (q / 2^d) · y.
  return 0;
}

// Écart centré dans Z_q : 3328 est à distance 1 de 0.
const ecart = (a, b) => {
  const d = Math.abs(a - b) % q;
  return Math.min(d, q - d);
};

console.log("d | bits/coef | erreur max | erreur moyenne | borne q/2^(d+1)");
for (const d of [12, 11, 10, 5, 4, 3]) {
  let max = 0, total = 0;
  for (let x = 0; x < q; x++) {
    const e = ecart(x, decompresser(compresser(x, d), d));
    max = Math.max(max, e);
    total += e;
  }
  console.log(
    `${String(d).padStart(2)} | ${String(d).padStart(9)} | ${String(max).padStart(10)}` +
    ` | ${(total / q).toFixed(2).padStart(14)} | ${(q / 2 ** (d + 1)).toFixed(1).padStart(15)}`
  );
}

// Taille du chiffré ML-KEM : 32 · (du·k + dv) octets.
console.log("\nchiffré ML-KEM selon (du, dv) :");
for (const [nom, k, du, dv] of [["512", 2, 10, 4], ["768", 3, 10, 4], ["1024", 4, 11, 5]]) {
  console.log(`  ML-KEM-${nom.padEnd(4)} k=${k} du=${du} dv=${dv}  →  ${32 * (du * k + dv)} octets`);
}

const q = 3329;

function compresser(x, d) {
  // L'arrondi est la seule chose qui se passe ici : on projette Z_q, qui a
  // 3329 éléments, sur 2^d valeurs. Toute l'information au-delà de d bits
  // est jetée volontairement.
  return Math.round((2 ** d / q) * x) % 2 ** d;
}

function decompresser(y, d) {
  return Math.round((q / 2 ** d) * y);
}

const ecart = (a, b) => {
  const d = Math.abs(a - b) % q;
  return Math.min(d, q - d);
};

console.log("d | bits/coef | erreur max | erreur moyenne | borne q/2^(d+1)");
for (const d of [12, 11, 10, 5, 4, 3]) {
  let max = 0, total = 0;
  for (let x = 0; x < q; x++) {
    const e = ecart(x, decompresser(compresser(x, d), d));
    max = Math.max(max, e);
    total += e;
  }
  console.log(
    `${String(d).padStart(2)} | ${String(d).padStart(9)} | ${String(max).padStart(10)}` +
    ` | ${(total / q).toFixed(2).padStart(14)} | ${(q / 2 ** (d + 1)).toFixed(1).padStart(15)}`
  );
}

console.log("\nchiffré ML-KEM selon (du, dv) :");
for (const [nom, k, du, dv] of [["512", 2, 10, 4], ["768", 3, 10, 4], ["1024", 4, 11, 5]]) {
  console.log(`  ML-KEM-${nom.padEnd(4)} k=${k} du=${du} dv=${dv}  →  ${32 * (du * k + dv)} octets`);
}

// Trois lectures de la table.
//
// 1. L'erreur maximale colle à la borne théorique q / 2^(d+1). Ce n'est pas
//    une coïncidence : arrondir sur 2^d niveaux découpe Z_q en intervalles
//    de largeur q/2^d, et l'erreur d'arrondi vaut au plus la moitié.
//
// 2. Passer de 12 à 10 bits par coefficient économise 17 % du chiffré et
//    coûte une erreur de l'ordre de 1,6 — dérisoire devant le bruit LWE
//    déjà présent. C'est un excellent marché, et c'est pourquoi du = 10.
//
// 3. dv = 4 sur le second terme paraît brutal (erreur ~104) et ne l'est
//    pas : ce terme ne porte qu'UN BIT de message par coefficient, décodé
//    en comparant à q/2 ≈ 1664. Une erreur de 104 reste très loin du seuil.
//    Chaque terme est compressé selon ce qu'il transporte, pas uniformément.
//
// C'est tout le raisonnement de dimensionnement de ML-KEM : la compression
// ajoute du bruit, le bruit ajouté doit rester sous le budget qui sépare
// encore du seuil de décodage, et ce budget résiduel fixe le taux d'échec
// de déchiffrement.

À retenir