Cryptanalyse I : l'estimateur et sa calibration

Une hypothèse sans réduction du pire cas vaut exactement ce que vaut sa cryptanalyse. §5 l'énonce sans détour, et fait trois choses : elle cartographie la surface d'attaque — vue en séance 4 — elle fixe un seul estimateur, calibré par référence externe, et elle dit ce que cet estimateur ne modélise pas. Cette séance couvre les deux dernières.

À lire avant la séance

§5.2, §5.4 et §5.5, avec les Tables 3 à 5. Puis les Annexes A et B, qui portent respectivement la mesure sous réduction et le remplacement de l'hypothèse de série géométrique. La Remarque 12 est courte et décide du signe de toute la section : ne la sautez pas.

La calibration

Tout chiffre de sécurité de l'article sort d'un unique estimateur, calibré en le faisant tourner sur les instances module-LWE de Kyber et en comparant à leurs coûts core-SVP publiés.

L'accord est à 1,2 bit près, et l'estimateur est uniformément et légèrement optimiste. C'est la précision à laquelle tous les chiffres de la séance 8 doivent être lus, et l'article énonce en conséquence ses revendications comme des parités sous estimateur partagé, non comme des coûts absolus.

La méthode a une limite que les auteurs formulent eux-mêmes : calibrer vérifie qu'on calcule la même chose que les autres, pas que le calcul soit juste.

L'estimateur sous réduction

L'Annexe A répond à cette limite en confrontant l'estimateur à de la réduction réelle, sur des instances réduites du réseau de clé du KEM lui-même.

La forme employée pour produire les chiffres publiés est la première : elle sur-estime le blocksize dont un attaquant a besoin, de 9 à 20 unités, soit 3 à 6 bits de coût core-SVP. C'est le sens défavorable. La forme remise à l'échelle, elle, suit la réduction de près.

Largeurs inégales, et le retrait

Pourquoi deux formes ? Parce que secret et erreur n'ont pas la même largeur. Le secret du réseau est $s = 1 + p\,s'$, pas $s'$ ; l'erreur, elle, n'est pas mise à l'échelle par $p$, puisque le schéma compact publie $e_1$ et non $p\,e_1$. Il en résulte $\sigma_s/\sigma_e = 2{,}45$, le plus grand rapport de tout l'article — et nul chez Kyber, où les deux formes coïncident, ce qui explique que la question ne se pose pas là-bas.

Le remède standard est de remettre le bloc secret à l'échelle par $\omega := \sigma_e/\sigma_s$ avant d'appliquer l'estimation. Et cela baisse l'estimation au lieu de la relever.

Les auteurs en tirent une conclusion qu'il faut lire mot à mot, car c'est le mouvement le plus important de toute la cryptanalyse : ils ne révisent pas les jeux de paramètres, mais retirent la lecture selon laquelle les chiffres cités seraient conservateurs. Sur les éléments disponibles, ils sont optimistes, des montants ci-dessus.

L'attaque hybride

L'attaque hybride de Howgrave-Graham devine $g$ coordonnées d'un secret étroit par rencontre au milieu et résout le problème résiduel en dimension $d - g$. Elle mord exactement là où poussent les leviers de §4.1 : il faut donc la modéliser, non l'écarter. Deux modèles circulent, et ils divergent de dizaines de bits.

Le modèle strict suppose une réduction uSVP fraîche pour chaque devinette. Appliqué à Kyber-512, il prédit un gain hybride de 22 bits sur l'attaque primale — que les analyses publiées excluent. La calibration de §5.2 l'élimine donc d'elle-même, et il n'est conservé qu'en colonne de stress.

Le modèle Babai/GSA, standard depuis Wunderer, suppose que BKZ tourne une fois sur la base résiduelle et que chaque devinette coûte un appel au plan le plus proche, qui réussit lorsque la plus petite norme de Gram–Schmidt dépasse l'écart-type du bruit d'un facteur $\tau$. Cette constante doit être ajustée :

Le tableau donne le coût hybride moins le coût primal : négatif signifie que l'hybride gagne. À $\tau = 1{,}0$ le modèle offrirait 20 à 28 bits sur Kyber, ce qui est exclu ; à $\tau = 3{,}0$ il ne concède rien et n'apprend rien. Le croisement est entre 1,5 et 2,0, et l'article adopte $\tau = 2{,}0$ — en notant explicitement que cette valeur se situe au croisement et non confortablement au-delà.

Et la conclusion qui compte

L'Annexe B ne s'arrête pas à la constante. Elle remplace l'hypothèse de série géométrique par un simulateur de profil, et vérifie l'un contre l'autre sur les profils de Gram–Schmidt réellement mesurés en §5.6. La GSA sur-estime la plus petite norme de Gram–Schmidt d'un facteur 1,31 en moyenne sur 34 cellules non dégénérées, là où le simulateur de Chen–Nguyen la reproduit à 0,98–1,09.

Recalculée avec le simulateur, l'attaque hybride ne mord à aucun jeu de paramètres : son coût passe au-dessus du coût primal partout, et l'optimum dégénère en pure devinette. La conclusion est donc que la sensibilité à $\tau$ — et l'ambiguïté de largeur qui l'accompagne — sont des artefacts de la GSA. L'attaque primale est la contrainte mordante à chaque jeu de paramètres de l'article, et la forme fermée n'est gardée qu'en modèle de stress.

Point de discussion

La calibration sur Kyber est utilisée deux fois, et de deux manières différentes : pour étalonner l'estimateur primal, puis pour écarter un modèle hybride au motif qu'il prédirait un gain que la littérature exclut. Le second usage est-il légitime ? Il revient à traiter le consensus publié sur Kyber comme une donnée expérimentale. Quelles en sont les conditions de validité, et que se passerait-il si ce consensus bougeait ?

À retenir