Nouvelles hypothèses pour la cryptographie fondée sur les réseaux – TOTORO

Le problème de l'apprentissage avec erreurs (Learning With Errors en anglais, ou LWE) et sa variante algébrique module-LWE sont probablement les problèmes algorithmiques les plus connus de la cryptographie fondée sur les réseaux. Leur notoriété peut s'expliquer par le fait qu'ils sont polyvalents (leur formulation les rend faciles à utiliser dans de nombreuses constructions cryptographiques) et leur sécurité est bien comprise (il existe des réductions depuis des problèmes algorithmiques pire cas sur les réseaux euclidiens, vers les problèmes LWE et module-LWE en moyenne). En plus de cela, le problème module-LWE utilise des réseaux structurés, ce qui permet aux constructions qui l'utilisent d'être efficaces (i.e., d'avoir des tailles de clés relativement petites et des algorithmes rapides pour le chiffrement ou la signature par exemple).
Dans le catalogue des problèmes algorithmiques fondés sur les réseaux que nous possédons actuellement, il est difficile de trouver un candidat qui soit meilleur que module-LWE pour l'une des trois caractéristiques mentionnées ci-dessus (polyvalence, sécurité, efficacité), sans être significativement plus mauvais pour l'une des autres.

L'objectif du projet TOTORO est d'étudier trois problèmes prometteurs, qui pourraient surpasser le problème module-LWE: le problème de l'isomorphisme de réseaux, le problème middle-product LWE, et le problème NTRU. Chacun de ces problèmes a des avantages ainsi que des inconvénients comparé au problème module-LWE : l'objectif du projet sera de remédier à ces inconvénients.