Le KEM : leviers, correction, sécurité

La forme du schéma n'est pas libre. L'algèbre en impose une partie — c'est l'objet de l'Annexe E — et la cryptanalyse de la séance précédente en autorise une autre, prise ici à crédit et honorée en séance 7. Cette séance suit ces deux déterminations jusqu'à l'IND-CCA.

À lire avant la séance

§4 en entier, des leviers de §4.1 aux tailles de §4.10, en passant par les Algorithmes 1 à 5 et les Théorèmes 1 et 2. Puis l'Annexe D, courte, sur la probabilité d'échec exacte, et les deux premiers paragraphes de l'Annexe E sur ce que l'algèbre force.

Ce que l'algèbre force

Deux contraintes précèdent tout choix de conception.

La trappe rescale par $s$, donc l'encodage est $p$-adique. La seule opération secrète dont dispose le receveur est la multiplication par $M_s$ : tout ce qui est extrait se trouve donc mis à l'échelle par $s$. Un encodage à la Kyber, $\Delta\cdot m$ avec $\Delta = \lceil q/2 \rceil$, ferait récupérer $\Delta\, s m$ dont la norme est bien trop grande pour éviter le repli modulo $q$. On suit donc la route NTRU : tous les termes parasites sont rendus nuls modulo $p$, et le message se lit modulo un petit premier.

L'aléa de chiffrement doit vivre dans $\mathcal{A}$. Le déchiffrement ne se referme que si l'aléa de l'émetteur commute avec $M_s$. Par le Lemme 6, le commutant d'une matrice générique ne rencontre $M(\mathcal{A})$ qu'en les scalaires : l'aléa doit donc être pris dans $\mathcal{A}$ lui-même, et non comme une matrice courte arbitraire de $\mathcal{M}_k$.

Les trois leviers

Troncature de ligne. En imposant $s \equiv 1 \pmod p$ et en restreignant le message à la première coordonnée, on obtient $\mathrm{coef}(sm) \equiv (m_0, 0, \ldots, 0) \pmod p$ : le déchiffrement ne lit que la première coordonnée. Le receveur n'a donc besoin que d'une ligne de $t$ et d'une ligne de $c_2$, d'où une clé publique de $nk$ coefficients et un chiffré de $2nk$ — au lieu de $nk^2$ et $nk(k+1)$. Le réseau d'attaque tronqué coïncide exactement avec le régime $m^{*} = 1$ de la séance 4 : rien n'est perdu.

Encodage MSB, pour la compression seule. Le budget de bruit est identique ; le gain est que l'erreur d'arrondi entre additivement comme un bruit ordinaire, là où un encodage LSB détruirait le résidu modulo $p$. Deux limites méritent d'être nommées. La clé publique tronquée n'est pas compressible : son erreur d'arrondi multiplie un produit de deux secrets, et un seul bit brise la correction. Et le chiffré ne tolère qu'une compression modérée, $d = 11$ à 12 bits, parce qu'à la différence du $v$ de Kyber il multiplie un secret et non un haché.

Distributions découplées. Une largeur unique partout est sous-optimale : élargir $\chi_r$ durcit la seconde hypothèse à un coût linéaire dans le budget de bruit, alors que $\chi_f$ y entre quadratiquement. Le découplage en trois largeurs $(\eta_f, \eta_r, \eta_{s'})$ récupère la catégorie 3, qui échouerait autrement.

Le levier qu'on ne peut pas tirer. La Remarque 6 mérite d'être lue en séance : annuler les coordonnées d'erreur que l'attaque n'utilise pas est dangereux. La relation publique est colonne par colonne une équation linéaire en $\mathrm{coef}(s)$ ; mettre une coordonnée à zéro impose une contrainte exacte qui, combinée à la brièveté de $s$, récupère la clé. Les leviers changent ce qui est publié, jamais la façon dont on échantillonne.

Correction, et la probabilité d'échec exacte

Le Lemme 7 donne l'identité de déchiffrement, la Proposition 2 la condition de correction, et l'équation (5) la variance coordonnée par coordonnée. Jusque-là, la mécanique est classique.

§4.5 l'est beaucoup moins, et c'est la partie de §4 à ne pas survoler. La borne gaussienne sous-estime la queue d'une somme de produits de variables bornées. Le calcul exact, par convolution et avec le terme d'arrondi énuméré plutôt qu'approché, coûte 2 à 9 bits sur la variance et 2 à 3 de plus sur la queue : le $\delta$ gaussien est optimiste de 5 à 12 bits à ces paramètres.

La conséquence est concrète. À la catégorie 1, la marge passe de 16 bits à 4 — et c'est précisément ce qui rend la contrainte de correction mordante dans le réglage de la séance 8, où un jeu sélectionné contre le $\delta$ gaussien s'avère inadmissible. Le Lemme 8 clôt la section sur une note plus légère : la clé $p$-adique est gratuite, le facteur $p$ pouvant être ignoré dans l'analyse de sécurité.

La seconde hypothèse

Il faut être clair là-dessus, car le résumé peut induire en erreur : la sécurité passive ne repose pas sur $\mathrm{NTC}$ seule. La pseudo-aléatoirité de la clé publique ne cache pas le message ; il faut encore que le chiffré soit pseudo-aléatoire. La Définition 8 isole cette seconde hypothèse décisionnelle, $\mathsf{cLWE}_{\mathcal{A}}$ — exactement l'analogue de la situation NTRU, où le NTRU décisionnel se combine à une hypothèse de type LWE sur le quotient devenu uniforme.

La Remarque 8 en établit la plausibilité, et vaut d'être détaillée : l'échantillon tronqué en colonne est précisément du module-LWE de rang $k$ sur $R_q$ ; l'échantillon tronqué en ligne est du ring-LWE sur $\mathcal{A}$, qui se trouve être l'anneau cyclotomique de degré $nk$ — $\varPhi_{4n}$ dans la famille en puissance de deux, et l'anneau $\varPhi_{2304}$ à la catégorie 3. Ce sont deux objets standards, et la seule structure jointe est le secret $r$ partagé, c'est-à-dire le cadre ordinaire du LWE à échantillons multiples.

De l'IND-CPA à l'IND-CCA

Le Théorème 1 borne l'avantage par la somme des deux hypothèses, en deux sauts de jeu : le premier remplace la ligne publiée de $t$ par de l'uniforme — un distingueur tronque un défi $\mathrm{NTC}$-Dec — le second remplace le chiffré, qui est exactement une instance $\mathsf{cLWE}_{\mathcal{A}}$ tronquée à $\ell = 2$ sous secret commun.

Deux remarques encadrent le résultat. La Remarque 9 souligne que la réduction est serrée et n'invoque ni l'Heuristique 6 ni le non-scindage — ceux-ci servent au problème de recherche ; le non-scindage reste cependant nécessaire en amont, faute de quoi l'attaque CRT récupère la clé et $\mathrm{NTC}$-Dec est simplement fausse. La Remarque 10 précise que les deux sauts ne consomment que ce que le schéma publie, la corrélation de colonnes du schéma non tronqué n'étant jamais exposée.

La transformation de Fujisaki–Okamoto à rejet implicite donne enfin l'IND-CCA dans le ROM. Le terme $q_G\,\delta$ du Théorème 2 est ce qui impose $\delta \leqslant 2^{-140}$ : à $\lambda = 128$ et $q_G \leqslant 2^{64}$, la queue doit être coupée à six ou sept écarts-types.

Point de discussion

La Remarque 11 chiffre ce que coûterait la conception naïve : publier les $k$ lignes, encoder $p$-adiquement, une seule largeur de bruit — soit 2,3 à 2,7 fois la clé publique et 1,5 à 2 fois le chiffré, à sécurité égale. Autrement dit, la compacité annoncée du schéma tient pour bonne moitié à une lecture fine de sa propre cryptanalyse. Est-ce une pratique saine ? Elle crée une dépendance : si §5.1 se révélait fautive sur $m^{*} = 1$, le schéma perdrait sa compacité sans que sa sécurité soit d'abord en cause. Discutez cette dette, que l'article assume explicitement en parlant de crédit.

À retenir