Fondements de complexité de la cryptographie efficace sur réseaux – HELO

La cryptographie post-quantique vise à concevoir des primitives cryptographiques qui peuvent être exécutées par des ordinateurs classiques, mais qui résistent aux attaques des ordinateurs quantiques. La cryptographie basée sur les réseaux, standardisée par L'Institut national des normes et de la technologie des États-Unis, sera bientôt déployée dans notre vie quotidienne.

L’une des propriétés les plus attrayantes de la cryptographie sur les réseaux est que sa sécurité repose sur la complexité des problèmes sur réseaux dans le pire des cas. Cependant, pour des raisons pratiques, les schémas cryptographiques hautement efficaces sont instanciés avec des paramètres extrêmement petits ou même avec des fuites supplémentaires sur les informations secrètes. Dans ce cas, le fondement de la sécurité sur les problèmes sur réseaux dans le pire des cas n'est plus présent.

Dans ce projet, nous visons à étudier la difficulté de ces problèmes sans connexion aux problèmes dans le pire des cas. Notre enquête se fera de deux manières. D'un côté, nous essaierons de rétablir la connexion aux problèmes du pire des cas au cas où la fuite supplémentaire n’invalide pas la complexité des problèmes. De l'autre côté, nous continuerons à améliorer les meilleurs algorithmes de résolution existants ou à proposer de nouveaux algorithmes en intégrant ces fuites supplémentaires de secrets.

Enfin, il existe peu de connaissances sur la complexité quantique des problèmes des réseaux, notamment sur leurs variantes algébriques. Notre dernier axe de recherche portera sur la complexité quantique des problèmes sur réseaux, en particulier ceux avec des structures algébriques et de petits paramètres. L'idée principale sera d'établir la connexion/équivalence entre les problèmes des réseaux et les problèmes quantiques. Une telle connexion nous fournira une nouvelle direction pour analyser la difficulté des problèmes sur réseaux.