Preuves de sécurité et réductions dans les schémas fondés sur les réseaux

Une preuve de sécurité pour un schéma cryptographique est un raisonnement mathématique formel montrant que compromettre le schéma implique de résoudre un problème difficile sous-jacent. La preuve ne garantit pas une sécurité absolue ; elle montre que tout adversaire efficace contre le schéma peut être transformé en un algorithme efficace permettant de résoudre le problème difficile. Si ce problème est impossible à résoudre en pratique, le schéma est sûr.

La preuve fondatrice de Regev, publiée en 2005, montre qu’un algorithme polynomial résolvant LWE décisionnel peut être utilisé pour résoudre GapSVP (problème du vecteur le plus court avec écart) sur des réseaux de dimension n dans le pire des cas. La réduction est quantique : elle utilise une procédure d’échantillonnage quantique pour transformer un algorithme résolvant LWE en algorithme résolvant un problème de réseau. Cela signifie que LWE est au moins aussi difficile que les problèmes de réseaux dans le pire des cas avec un calcul quantique.

La réduction de Regev n’est pas serrée : les facteurs polynomiaux de la réduction signifient que le niveau de sécurité garanti par la preuve est quelque peu inférieur à ce que laissent penser les meilleures attaques connues. Pour choisir les paramètres en pratique, les cryptographes utilisent la sécurité concrète fournie par les meilleures attaques connues, au moyen de l’estimateur de réseaux, plutôt que la borne théorique de la réduction, car celle-ci est prudente.

Un schéma de chiffrement fondé sur LWE est démontré IND-CPA (indistinguabilité sous attaque à texte en clair choisi) au moyen d’un argument hybride. La preuve montre qu’un distingueur IND-CPA implique un distingueur LWE. Dans le premier hybride, le texte chiffré réel est remplacé par une chaîne aléatoire uniforme ; l’indistinguabilité découle de l’hypothèse LWE. Cela fournit une preuve de sécurité claire pour le chiffrement élémentaire fondé sur les réseaux.

La sécurité IND-CPA ne suffit pas pour les mécanismes d’encapsulation de clés utilisés dans TLS : ceux-ci doivent assurer la sécurité IND-CCA2 (sous attaque à texte chiffré choisi). La transformation de Fujisaki-Okamoto (FO) convertit tout schéma IND-CPA en un KEM IND-CCA2 dans le modèle de l’oracle aléatoire (ROM). ML-KEM applique une variante de la transformation FO au chiffrement Module-LWE sous-jacent, fournissant la sécurité CCA2 requise pour un déploiement en conditions réelles.

Le modèle de l’oracle aléatoire (ROM) modélise les fonctions de hachage comme des fonctions véritablement aléatoires. De nombreuses preuves de sécurité, notamment celles de la transformation FO, nécessitent le ROM. En pratique, les fonctions de hachage telles que SHA-3 ne sont pas de véritables oracles aléatoires ; les preuves dans le ROM ne garantissent donc pas la sécurité dans le modèle standard. Toutefois, la communauté cryptographique accepte largement les preuves dans le ROM comme des éléments solides en faveur de la sécurité.

Une preuve dans le modèle standard ne fait aucune idéalisation des fonctions de hachage et est strictement plus forte qu’une preuve dans le ROM. La plupart des schémas pratiques fondés sur les réseaux utilisent des preuves dans le ROM, car les preuves CCA2 dans le modèle standard pour les KEM fondés sur les réseaux sont beaucoup plus complexes et produisent de moins bons paramètres concrets. Le NIST a accepté les preuves fondées sur le ROM pour ML-KEM, les considérant suffisantes pour les niveaux de sécurité visés.

La preuve de sécurité de ML-KEM se déroule en deux étapes. Premièrement, il est démontré que le chiffrement Module-LWE sous-jacent est sécurisé IND-CPA sous l’hypothèse M-LWE. Deuxièmement, la transformation de Fujisaki-Okamoto (plus précisément les transformations T et U utilisées dans Kyber) élève cette sécurité au niveau IND-CCA2 dans le ROM quantique (QROM), qui prend en compte les adversaires interrogeant l’oracle aléatoire en superposition.

L’estimateur de réseaux d’Albrecht, Player et Scott est l’outil de référence pour calculer la sécurité concrète des schémas fondés sur LWE. Il modélise le coût des meilleures attaques sur les réseaux connues, notamment BKZ avec criblage ou énumération, et fournit une estimation de la sécurité en bits pour les paramètres donnés (n, q, sigma). Cet outil est régulièrement mis à jour à mesure que de nouveaux algorithmes et modèles de coût matériel sont publiés.

L’algorithme de réduction par blocs de Korkine-Zolotarev (BKZ) est le meilleur algorithme pratique de réduction des réseaux. BKZ avec une taille de bloc beta trouve des vecteurs courts avec une complexité d’environ 2^{0.292*beta} opérations de portes en utilisant les meilleurs algorithmes de criblage. Pour ML-KEM-768, la sécurité classique estimée est d’environ 180 bits et la sécurité quantique d’environ 164 bits, bien au-dessus de l’objectif de 192 bits.

Les preuves de sécurité asymptotique montrent qu’un schéma est sûr pour des paramètres suffisamment grands, mais ne précisent pas ce que signifie « suffisamment grands » en pratique. L’analyse de la sécurité concrète comble cette lacune en estimant le coût réel de la meilleure attaque pour les paramètres choisis. La normalisation post-quantique repose largement sur l’analyse de la sécurité concrète, les paramètres étant choisis pour résister aux attaques menées avec le matériel quantique prévu sur un horizon de 30 ans.

Quelle transformation est utilisée dans ML-KEM pour faire passer un chiffrement sur les réseaux de la sécurité IND-CPA à la sécurité IND-CCA2 ?

Les preuves de sécurité des schémas fondés sur les réseaux réduisent la sécurité du schéma à la difficulté de LWE ou de SVP. La réduction de Regev garantit que LWE est au moins aussi difficile que les problèmes de réseaux dans le pire des cas. La transformation de Fujisaki-Okamoto fait passer la sécurité IND-CPA à IND-CCA2 dans le ROM. La sécurité concrète est évaluée avec l’estimateur de réseaux au moyen de modèles de complexité BKZ. Les écarts de précision des réductions signifient que les paramètres pratiques reposent sur les estimations du coût des attaques plutôt que sur les seules bornes des réductions.