Conception de cryptosystèmes post-quantiques : l'exemple de la signature Falcon

Les progrès réguliers de l'informatique quantique pourraient à terme menacer tous les protocoles de communications sécurisées actuels. En effet, l'algorithme de Shor résout en temps polynomial les problèmes de la factorisation ou du logarithme discret, qui fondent la sécurité de tous les cryptosystèmes à clé publique déployés, comme les échanges de clés ou les signatures numériques. Concevoir de nouveaux cryptosystèmes robustes face aux algorithmes quantiques est le domaine de la cryptographie post-quantique. Parmi les nouvelles propositions, les schémas dont la sécurité repose sur des problèmes algorithmiques difficiles dans les réseaux Euclidiens semblent les plus attirants : ils représentent la quasi-totalité des récents vainqueurs de la compétition de standardisation du NIST, démarrée en 2017.

L'un de ces vainqueurs, la signature numérique "Falcon", illustrera les étapes de conception d'un cryptosystème moderne, partant des problèmes théoriques de réseaux Euclidiens fondant la sécurité jusqu'à des aspects plus concrets liés à son implémentation. L'un des ces problèmes, l'échantillonnage Gaussien dans des réseaux Euclidien, est fondamental dans l'estimation de la sécurité offerte par Falcon. Nous verrons certains des choix de conception qui peuvent être fait pour obtenir des solutions, et les problèmes toujours ouverts soulevés par le futur déploiement du schéma.