Sécurité cryptographique des réseaux modules – CHARM

L'avènement du calcul quantique s'approchant, la sécurité des standards de cryptographie à clé publique actuellement déployés pourrait arriver à son terme. Il est ainsi impérieux d'étudier des fondements mathématiques et de théorie de la complexité qui résistent au calcul quantique. Motivés par l'effort de standardisation de la cryptographie post-quantique mené par le NIST (l'agence américaine des standards), de nombreux progrès ont été réalisés pour rendre la cryptographie post-quantique prête à un large déploiement. Parmi les finalistes du projet de standardisation du NIST, cinq sur sept ont leur sécurité qui repose sur la difficulté algorithmique présumée de problèmes impliquant des réseaux euclidiens issus de la théorie algébrique des nombres. Cette proposition de projet collaboratif ANR-NSF vise à étudier les aspects algorithmiques et de complexité des problèmes de réseaux quand ceux-ci sont restreints à des modules sur des anneaux d'entiers de corps de nombres.

À ce jour, on ne connaît aucun algorithme exploitant cette structure algébrique additionnelle pour résoudre ces problèmes de réseaux modules plus rapidement que les algorithmes pour des réseaux génériques, pour des paramètres cryptographiques typiques. Néanmoins, il existe quelques attaques tirant parti de la structure additionnelle pour des cas spécifiques (modules de rang 1 ou de rang 2 avec un vecteur inhabituellement petit), mais elles sont limitées à des régimes de paramètres de faible intérêt cryptographique. Déterminer si ces attaques peuvent être étendues au problème standard Ring Learning With Errors est complètement ouvert. En fait, l'étude algorithmique des réseaux modules, tels que ceux provenant de Ring-LWE, n'en est qu'à ses débuts : c'est seulement il y a un peu plus d'un an qu'a été proposé le premier algorithme de réduction de réseaux exploitant la structure de module. D'un point de vue complexité, la situation est tout aussi déroutante, avec une absence de liens établis entre des problèmes centraux tels que Ring-LWE et le problème NTRU, également très utilisé.

L'objectif principal de ce projet collaboratif est de fournir une compréhension plus claire de la difficulté algorithmique des problèmes sur les réseaux modules utilisés en cryptographie, via des améliorations d'algorithmes dédiés et des améliorations des réductions entre eux. Les axes de recherche incluent : (i) L'étude d'algorithmes pour le problème Ideal-SVP qui atteignent des facteurs d'approximation plus bas qu'aujourd'hui sans nécessiter de pré-calcul ; la conception d'algorithmes dédiés pour des corps de nombres spécifiques comme les cyclotomiques et les multiquadratiques. (ii) La caractérisation précise de la complexité du problème NTRU et sa relation avec les autres problèmes moyen-cas classiques portant sur les réseaux modules ; la recherche de meilleurs algorithmes pour attaquer le problème NTRU ; la compréhension précise de l'impact éventuel d'une structure de sous-corps du corps de définition sur la difficulté du problème NTRU. (iii) La compréhension de la transition de complexité entre le rang 1 et le rang 2 pour les problèmes de réseaux modules ; l'extension au rang 2 des algorithmes existant pour le rang 1. (iv) La contribution à des logiciels libres efficaces et robustes pour les réseaux euclidiens et la théorie algébrique des nombres. Les résultats de ce projet bénéficieront la communauté cryptographique, notamment les concepteurs de cryptosystèmes reposant sur les réseaux, et participeront à informer le projet de standardisation post-quantique du NIST.

Ce projet collaboratif CISE-ANR regroupe des chercheurs de quatre sites, avec des expertises complémentaires et des compétences couvrant les réseaux euclidiens, les réseaux algébriques, la complexité des problèmes de réseaux, et les algorithmes heuristiques et implémentations efficaces de codes résolvant ces problèmes.