2022

Mitaka - a simpler, parallelizable, maskable variant of Falcon

Par Alexandre Wallet (CAPSULE, INRIA) le 2022-11-22*

• Falcon est un schéma de signature fondé sur les réseaux euclidiens, et récemment sélectionné par le NIST comme futur standard post-quantique. En consommation de bande passante, Falcon est actuellement la meilleure alternative, et ses performances sont proches de celle de l’autre schéma sélectionné, Dillithium. Cependant, les choix de design de Falcon imposent des limites conceptuelles freinant son utilisation dans différents scénarios : 1) les jeux de paramètres sont très restreints ; 2) implémenter le schéma est un exercice délicat ; 3) protéger son implémentation actuelle a un coût prohibitif en plus d’être difficile.

Les facteurs limitants du schéma sont principalement liés à son échantillonneur de vecteurs Gaussiens dans des réseaux euclidiens. Notre variante Mitaka, qui suit le design général de Falcon, évite les écueils précédents en utilisant un échantillonneur différent, appelé « hybride », et qui avait été mis de côté en raison d’un niveau de sécurité estimé plus faible. De manière générale, nos travaux ont montré que la sécurité apportée par l’hybride pouvait être équivalente à celle de Falcon, et que sa simplicité conceptuelle permet de plus grands choix de design et de protection, à faible coût. L’exposé présentera des techniques et outils qui nous ont permis d’obtenir ces résultats pour Mitaka, et mentionnera d’autres récentes améliorations générales pour hash-then-sign sur des réseaux.

L’exposé sera inspiré de plusieurs travaux en collaboration avec Thomas Espitau, Pierre-Alain Fouque, François Gérard, Melissa Rossi, Akira Takahashi, Mehdi Tibouchi et Yang Yu.

Éléments courts dans des idéaux de corps de nombres

Par Andréa Lesavourey (IRISA, Rennnes) le 2022-10-25*

• Dans la recherche actuelle de primitives pouvant résister à l'utilisation d'un ordinateur quantique, une des pistes majeure se base sur les réseaux euclidiens, et en particulier sur le problème Learning With Errors (LWE). En effet, il existe une réduction pire cas -- moyen cas vers le problème classique de réseaux qu'est le Shortest Vector Problem (SVP). Pour des raisons d'efficacité, les schémas envisagés se basent sur des versions structurées de LWE, comme Ring ou Module-LWE. Il existe par ailleurs des réductions pire cas -- moyen cas de ces problèmes vers le SVP restreint respectivement aux réseaux idéaux (Ideal-SVP) et modules (Module-SVP). C'est pourquoi l'analyse de Ideal-SVP a reçu une attention soutenue ces dernières années.

Dans cet exposé je ferai d'abord des rappels concernant les réseaux euclidiens, la cryptographie basée sur ces objets, ainsi que les principales attaques algébriques sur Ideal-SVP. Je décrirai ensuite le travail fait pendant mon post-doctorat sur la possibilité de résoudre Ideal-SVP dans des corps cyclotomiques. Nous utilisons des générateurs courts de l'idéal de Stickelberger pour calculer en temps raisonnable le réseau des Log-S-unités pour des corps de dimension aussi grande que 200. Nous faisons également des expériences pour évaluer les performances de l'algorithme Twisted-PHS dans ce mode dégradé (travail accepté à ASIACRYPT 2022, avec Olivier Bernard, Thuong Huy et Adeline Roux-Langlois).

Années passées

2022 |2021 |2020 |2019 |2018 |2017 |2016 |2015 |2014 |2013 |2012 |2011 |2010 |2009 |2008