Sécurité prouvée en contexte post-quantique

« Prouvé sûr » est l'expression la plus mal comprise de la cryptographie. Elle ne signifie jamais « incassable ». Elle signifie : si telle hypothèse tient, et si le modèle décrit correctement l'attaquant, alors casser le schéma est au moins aussi difficile que résoudre tel problème. Trois conditions, trois endroits où la preuve peut ne rien garantir.

Ce chapitre précise ce que les preuves post-quantiques disent, et surtout où elles s'arrêtent.

Un jeu de sécurité, c'est une définition opérationnelle

On ne définit pas la sécurité par une propriété abstraite mais par un jeu entre un challenger et un adversaire. Trois jeux couvrent presque tout le cours.

IND-CPA. L'adversaire reçoit la clé publique, soumet deux messages de même longueur, et reçoit le chiffré de l'un des deux tiré au hasard. Il gagne s'il devine lequel avec un avantage non négligeable sur le hasard. C'est le minimum : il modélise un attaquant passif, qui observe.

IND-CCA2. Même jeu, mais l'adversaire dispose en plus d'un oracle de déchiffrement qu'il peut interroger sur n'importe quel chiffré, sauf celui du défi. C'est un attaquant actif, et c'est le modèle réaliste : dans un protocole, votre serveur déchiffre volontiers tout ce qu'on lui envoie et son comportement se lit dans sa réponse.

EUF-CMA. Pour les signatures : l'adversaire obtient des signatures sur les messages de son choix, et gagne s'il produit une signature valide sur un message jamais soumis.

L'écart entre IND-CPA et IND-CCA2 n'est pas académique. Le chiffrement du chapitre 6 est IND-CPA et parfaitement malléable : ajouter $q/2$ à un coefficient du chiffré inverse un bit du message, sans connaître la clé. L'exercice de ce chapitre vous le fait faire en trois lignes.

ROM : l'oracle aléatoire

Beaucoup de preuves, dont celle de Fujisaki-Okamoto, se placent dans le modèle de l'oracle aléatoire. On y suppose que la fonction de hachage se comporte comme une fonction véritablement aléatoire, à laquelle tout le monde — y compris le réducteur de la preuve — n'accède que par requêtes.

C'est une idéalisation, et une idéalisation fausse : SHA-3 est un algorithme public de quelques centaines de lignes, pas une fonction aléatoire. Canetti, Goldreich et Halevi ont même construit des schémas prouvés sûrs dans le ROM et cassés pour toute instanciation concrète du hachage.

Ces contre-exemples sont artificiels, et aucun schéma déployé n'en a jamais souffert. Le ROM reste donc largement accepté, mais comme un argument de conception plutôt que comme une garantie mathématique. Il faut le formuler ainsi devant des étudiants : une preuve ROM dit qu'il n'existe pas d'attaque générique, pas qu'il n'existe pas d'attaque.

QROM : ce que change un attaquant quantique

Voici le point spécifiquement post-quantique du chapitre, et il est plus subtil qu'il n'en a l'air.

Un attaquant quantique qui dispose du code de SHA-3 peut l'implémenter en circuit quantique et l'interroger en superposition : une seule requête sur une superposition de toutes les entrées possibles. Le modèle qui capture cela s'appelle le QROM, l'oracle aléatoire quantique.

Ce n'est pas seulement un attaquant plus fort. C'est un modèle où les techniques de preuve classiques cessent de fonctionner :

• l'échantillonnage paresseux disparaît. En ROM, le réducteur note les requêtes et choisit les réponses au fur et à mesure. En QROM, observer une requête en superposition la perturbe : on ne peut plus tenir de registre sans être détecté.
• l'extraction devient problématique. Beaucoup de preuves reposent sur le fait que l'adversaire a forcément interrogé l'oracle sur une valeur précise, qu'on lit dans le registre. En superposition, cette lecture n'a plus de sens direct.
• le rembobinage — rejouer l'adversaire avec des réponses différentes — se heurte au fait qu'on ne peut pas cloner un état quantique.

Il a fallu reconstruire l'outillage. Le lemme central s'appelle one-way to hiding (O2H), et les preuves QROM de Fujisaki-Okamoto ont été établies à partir de 2017, plusieurs années après les preuves ROM correspondantes. Certaines restent moins serrées que leurs analogues classiques.

Une preuve ROM ne vaut pas automatiquement en QROM. C'est la phrase à retenir de cette section, et c'est ce qui distingue un schéma « post-quantique » sérieux d'un schéma qui se contente d'une hypothèse résistante.

Fujisaki-Okamoto, déroulée

La transformation fait passer d'un PKE IND-CPA à un KEM IND-CCA2 en rendant le chiffrement vérifiable : on dérive l'aléa du message, ce qui rend le chiffrement déterministe, et le déchiffreur refait le chiffrement pour comparer.

L'argument de sécurité tient en une observation. Pour qu'un chiffré passe le test, il faut qu'il ait été produit par la procédure d'encapsulation à partir d'un message $m$ — donc que l'attaquant connaisse $m$. Or s'il connaît $m$, il connaît déjà la clé $K = G(m)$ : l'oracle de déchiffrement ne lui apprend rien. L'oracle devient simulable sans la clé secrète, et c'est exactement ce dont la réduction a besoin.

La branche « sinon » est le détail qui compte. Le rejet implicite renvoie une clé pseudo-aléatoire dérivée d'un secret interne et du chiffré, plutôt qu'une erreur. Deux raisons : l'erreur serait un oracle de validité, et la clé bidon est déterministe, donc un attaquant qui rejoue le même chiffré obtient la même réponse — il n'apprend rien non plus en répétant.

Les niveaux de sécurité du NIST

Le NIST n'exprime pas la sécurité en bits, ce qui serait ambigu entre modèles de coût, mais par équivalence avec des primitives symétriques bien comprises.

Le choix de cette échelle est habile. Il évite d'avoir à trancher entre les modèles de coût du chapitre 4, et il transporte automatiquement les hypothèses sur le matériel quantique : si Grover se révèle plus cher que prévu à cause de contraintes de profondeur de circuit, tous les niveaux se décalent ensemble, sans qu'aucune spécification n'ait à être réécrite.

En pratique, le niveau 3 — ML-KEM-768 et ML-DSA-65 — est la recommandation par défaut, et c'est ce que les navigateurs déploient.

Où la preuve s'arrête

Trois honnêtetés, à énoncer explicitement en cours.

Le serrage. Une réduction qui perd un facteur $2^{40}$ n'interdit pas les attaques en $2^{88}$ contre un schéma annoncé à 128 bits. En pratique, on dimensionne d'après l'estimation d'attaque du chapitre 4 et l'on ignore la perte de la réduction. C'est un choix raisonné, pas une conséquence de la preuve.

Le modèle décrit un attaquant, pas le monde. Aucun jeu de sécurité de ce chapitre ne donne à l'adversaire le temps d'exécution, la consommation électrique ou la possibilité d'injecter une faute. Un schéma peut être IND-CCA2 dans le QROM et tomber en quelques minutes sur une carte à puce. C'est le chapitre 12, et c'est là que se produisent la plupart des attaques réelles.

L'hypothèse peut être fausse. Toute la construction repose sur la difficulté de Module-LWE. SIKE était prouvé sûr sous son hypothèse ; l'hypothèse a cédé.

À vous

// Un mini K-PKE, réduit à n = 4 coefficients mais structurellement exact :
// Module-LWE de rang 1, arithmétique négacyclique, message encodé en q/2.
// Assez pour monter une attaque à chiffré choisi, et voir FO l'arrêter.

const q = 3329, n = 4;
const mod = (x) => ((x % q) + q) % q;
const centre = (x) => (mod(x) > q / 2 ? mod(x) - q : mod(x));

const mul = (f, g) => {
  const r = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) {
      const d = i + j;
      r[d % n] = mod(r[d % n] + (d >= n ? -1 : 1) * f[i] * g[j]);
    }
  return r;
};
const add = (f, g) => f.map((x, i) => mod(x + g[i]));
const sub = (f, g) => f.map((x, i) => mod(x - g[i]));

// Générateur pseudo-aléatoire déterministe : FO exige de pouvoir REFAIRE
// exactement le même chiffrement à partir de la même graine.
function prng(graine) {
  let v = 0x811c9dc5;
  for (const c of String(graine)) { v ^= c.charCodeAt(0); v = Math.imul(v, 0x01000193) >>> 0; }
  return () => { v ^= v << 13; v ^= v >>> 17; v ^= v << 5; v >>>= 0; return v; };
}
const petit = (suivant) => Array.from({ length: n }, () => (suivant() % 3) - 1);

const A = [2571, 913, 3200, 47];
const cleSecrete = petit(prng("secret"));
const t = add(mul(A, cleSecrete), petit(prng("erreur")));

const encoder = (bits) => bits.map((b) => b * Math.round(q / 2));
const decoder = (p) => p.map((c) => (Math.abs(centre(c)) > q / 4 ? 1 : 0));

function chiffrer(bits, graine) {
  const g = prng(graine);
  const r = petit(g), e1 = petit(g), e2 = petit(g);
  return { u: add(mul(A, r), e1), v: add(add(mul(t, r), e2), encoder(bits)) };
}
const dechiffrer = (c) => decoder(sub(c.v, mul(cleSecrete, c.u)));

const M = [1, 0, 1, 1];
const c = chiffrer(M, "aléa-honnête");
console.log("message           :", M.join(""));
console.log("déchiffré          :", dechiffrer(c).join(""));

// ── L'attaque : le schéma est MALLÉABLE ──
// Ajouter q/2 à un coefficient de v inverse le bit correspondant, sans
// jamais connaître la clé secrète.
function trafiquer(c, position) {
  const v = c.v.slice();
  // À COMPLÉTER — ajouter Math.round(q / 2) au coefficient d'indice position.
  return { u: c.u, v };
}

const cTrafique = trafiquer(c, 1);
console.log("\ntrafiqué (bit 1)   :", dechiffrer(cTrafique).join(""), " ← attendu 1111");

// ── La parade : Fujisaki-Okamoto ──
// L'aléa est dérivé du message lui-même, donc le chiffrement devient
// déterministe et le déchiffreur peut REFAIRE le chiffrement et comparer.
const memeChiffre = (a, b) => a.u.every((x, i) => x === b.u[i]) && a.v.every((x, i) => x === b.v[i]);

function decapsulerFO(chiffre) {
  const m = dechiffrer(chiffre);
  const c2 = chiffrer(m, "G:" + m.join(""));   // ré-encapsulation
  return memeChiffre(c2, chiffre) ? { ok: true, cle: m.join("") } : { ok: false, cle: "clé bidon" };
}

const cFO = chiffrer(M, "G:" + M.join(""));
console.log("\nFO, chiffré honnête :", JSON.stringify(decapsulerFO(cFO)));
console.log("FO, chiffré trafiqué:", JSON.stringify(decapsulerFO(trafiquer(cFO, 1))));

const q = 3329, n = 4;
const mod = (x) => ((x % q) + q) % q;
const centre = (x) => (mod(x) > q / 2 ? mod(x) - q : mod(x));

const mul = (f, g) => {
  const r = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) {
      const d = i + j;
      r[d % n] = mod(r[d % n] + (d >= n ? -1 : 1) * f[i] * g[j]);
    }
  return r;
};
const add = (f, g) => f.map((x, i) => mod(x + g[i]));
const sub = (f, g) => f.map((x, i) => mod(x - g[i]));

function prng(graine) {
  let v = 0x811c9dc5;
  for (const c of String(graine)) { v ^= c.charCodeAt(0); v = Math.imul(v, 0x01000193) >>> 0; }
  return () => { v ^= v << 13; v ^= v >>> 17; v ^= v << 5; v >>>= 0; return v; };
}
const petit = (suivant) => Array.from({ length: n }, () => (suivant() % 3) - 1);

const A = [2571, 913, 3200, 47];
const cleSecrete = petit(prng("secret"));
const t = add(mul(A, cleSecrete), petit(prng("erreur")));

const encoder = (bits) => bits.map((b) => b * Math.round(q / 2));
const decoder = (p) => p.map((c) => (Math.abs(centre(c)) > q / 4 ? 1 : 0));

function chiffrer(bits, graine) {
  const g = prng(graine);
  const r = petit(g), e1 = petit(g), e2 = petit(g);
  return { u: add(mul(A, r), e1), v: add(add(mul(t, r), e2), encoder(bits)) };
}
const dechiffrer = (c) => decoder(sub(c.v, mul(cleSecrete, c.u)));

const M = [1, 0, 1, 1];
const c = chiffrer(M, "aléa-honnête");
console.log("message           :", M.join(""));
console.log("déchiffré          :", dechiffrer(c).join(""));

function trafiquer(c, position) {
  const v = c.v.slice();
  // Le message est encodé en plaçant chaque bit près de 0 ou près de q/2.
  // Ajouter q/2 déplace donc le coefficient de l'un vers l'autre : le bit
  // s'inverse. Aucune connaissance de la clé n'est requise — c'est la
  // définition même de la malléabilité.
  v[position] = mod(v[position] + Math.round(q / 2));
  return { u: c.u, v };
}

const cTrafique = trafiquer(c, 1);
console.log("\ntrafiqué (bit 1)   :", dechiffrer(cTrafique).join(""), " ← attendu 1111");

const memeChiffre = (a, b) => a.u.every((x, i) => x === b.u[i]) && a.v.every((x, i) => x === b.v[i]);

function decapsulerFO(chiffre) {
  const m = dechiffrer(chiffre);
  const c2 = chiffrer(m, "G:" + m.join(""));
  return memeChiffre(c2, chiffre) ? { ok: true, cle: m.join("") } : { ok: false, cle: "clé bidon" };
}

const cFO = chiffrer(M, "G:" + M.join(""));
console.log("\nFO, chiffré honnête :", JSON.stringify(decapsulerFO(cFO)));
console.log("FO, chiffré trafiqué:", JSON.stringify(decapsulerFO(trafiquer(cFO, 1))));

// Ce que l'exercice démontre, dans l'ordre.
//
// 1. LE SCHÉMA CPA EST MALLÉABLE. Ajouter q/2 à un coefficient inverse le
//    bit correspondant, sans clé, sans calcul, sans rien. Le déchiffrement
//    ne proteste pas : il rend un message différent, parfaitement formé.
//    IND-CPA n'a jamais prétendu l'empêcher — il ne parle que d'un
//    attaquant PASSIF.
//
// 2. FO L'ARRÊTE, et le mécanisme est visible ici. L'aléa étant dérivé du
//    message, le chiffrement devient déterministe : le déchiffreur refait
//    le chiffrement et compare. Le chiffré trafiqué déchiffre en un autre
//    message, dont le rechiffrement ne redonne pas le chiffré soumis.
//
// 3. LA LIGNE À REGARDER est le "clé bidon". On ne renvoie PAS d'erreur.
//    Une erreur dirait à l'attaquant que sa modification a été détectée,
//    et il pourrait alors faire varier sa modification pour apprendre le
//    secret coefficient par coefficient. Le rejet implicite lui refuse ce
//    signal — à condition que l'implémentation mette exactement le même
//    temps dans les deux branches. C'est le chapitre suivant.

À retenir