MPC in the Head signature

Depuis 6 ans, une nouvelle technique pour concevoir des signatures a été introduite, à la suite du schéma de signature Picnic proposé pour le premier appel de la compétition organisée par le NIST en 2017. La technique est issue des travaux de Ishai, Kushilevitz, Ostrovsky, et Sahai [1] à STOC 2007. Dans cet article les auteurs montrent qu’on peut transformer n’importe quel protocole de calcul multi-parties sécurisé pour obtenir un protocole zero-knowledge. Pendant 10 ans, ce papier n’a eu que peu d’impact, mais en 2017, certains auteurs ont utilisé cette transformation pour construire un schéma de signature [2]. Il est bien connu qu’on peut concevoir des schémas de signature à partir de preuves d’authentification et de protocole zero-knowledge, mais dans le cas des codes correcteurs d’erreurs et de cryptographie multivariée, la taille des signatures n’est pas compétitive par rapport aux schémas reposant sur les réseaux euclidiens. Les schémas de signature issus de protocoles ZK, ont l’avantage de ne pas cacher une instance faible du problème, que seul le signataire légitime peut enlever. Le problème des instances faibles est que cette structure transparaît et que le problème à résoudre soit alors plus facile pour l’adversaire. Dans les signatures ZK, les instances sont parfaitement aléatoires et il n’y a pas d’instances faibles sous-jacentes. Cela renforce la sécurité des signatures. Cependant, pendant 30 ans, on a construit des schémas ZK directement à partir du problème difficile, on peut le faire à partir de n’importe quel problème dans la classe de complexité NP. La technique [1] permet de construire des schémas ZK à partir de n’importe quel protocole MPC. Les différentes parties de ce protocole sont simulées dans la tête d’une seule partie et sont appelés MPC-in-the-Head, MPCitH. On peut ensuite utiliser la transformation Fiat-Shamir pour obtenir un schéma de signature. Ceci permet d’obtenir des preuves pour une classe plus large de schémas, et en particulier, il est possible aujourd’hui de faire des preuves pour des hypothèses de cryptographie symétrique. La résistance repose sur le fait qu’il est difficile de trouver la clé secrète d’un schéma AES, comme dans le schéma FAEST [3]. Enfin, pour améliorer l’efficacité des schémas de signature, des auteurs ont utilisé des hypothèses de cryptographie à clé publique comme des problèmes difficiles sur les codes et de la cryptographie multivariée. Dans le dernier appel de la compétition du NIST, plusieurs constructions reposent sur ces techniques et actuellement, les 6 schémas MQOM, Mirath, PERK, RYDE, SDitH et FAEST, sur 14 schémas en tout, sont retenus pour le second tour de l’appel de 2022.

La recherche est toujours très active sur ce domaine et malgré ces schémas, ils sont actuellement encore trop gros pour certains pour être compétitif. L’avantage pour les schémas sur les codes et la cryptographie multivariée est que les tailles de clé publique et secrète sont ici vraiment petite. Cependant, la taille des signatures est un peu trop grande par rapport aux schémas directement construit sur des hypothèses multivariées par exemple où on peut espérer avoir des signatures d’une centaine d’octets, au prix d’avoir des clés publiques d’au moins 50 Koctets. De nombreuses techniques ont été proposées comme VOLE ou des techniques de partage de Shamir [4] pour améliorer l’efficacité et actuellement la taille des signatures est d’environ 5Koctets, ce qui est toutefois 2 fois plus gros que Dilithium (ML-DSA). On peut aussi observer qu’il n'y a pas de schémas MPCitH reposant sur un problème difficile de réseaux euclidiens. Enfin, on peut se demander quelle est la sécurité de ces nouveaux schémas contre les attaques par canaux auxiliaires. Est-ce qu’il existe une technique pour les protéger contre ces attaques ?

Description des objectifs et originalité de la thèse
L'objectif principal de cette thèse est d’étudier la sécurité et l’efficacité des implémentations de schémas de signature utilisant la technique MPCitH. Les trois pistes qui seront étudiées sont:

• Construction de schémas MPCitH en utilisant d’autres hypothèses cryptographiques : étudier la sécurité des schémas MPCitH proposés à la compétition du NIST ou depuis, et proposer de nouveaux schémas. En particulier, nous voudrions obtenir de meilleurs schémas utilisant des problèmes difficiles sur les réseaux euclidiens.
• Etudier la sécurité des implémentations de schémas MPCitH: étudier les attaques par canaux auxiliaires contre ces schémas. D’une part, les protocoles utilisent un partage de secret entre plusieurs parties. L’idée consiste à révéler presque tout le secret sauf une petite partie. Si l’adversaire obtient des informations sur cette dernière partie, alors il sera capable de retrouve tout le secret. Dans le cas des attaques par canaux auxiliaires, cela réduit la tache de l’adversaire à une variable, et mener à des attaques. D’un autre côté, les schémas utilisent nativement des techniques de partage de secret, et il est sûrement possible de combiner ces idées avec des techniques de masquage pour garantir la sécurité des implémentations.
• Utiliser les schémas MPCitH pour obtenir des protocoles avancées garantissant la vie privée : Le dernier objectif consiste d’utiliser ces protocoles pour construire des schémas avancées garantissant plus de propriétés.

Description des principaux verrous et techniques envisagées

Les principaux défis de ce projet incluent :

• Hypothèses réseaux euclidiens : Les schémas de signature reposant sur des problèmes difficiles concernant les réseaux euclidiens demandent de prouver que le secret est petit. C’est particulièrement difficile dans le cas des signatures MPCitH car le masquage est effectué modulo un nombre premier assez gros. La taille des meilleurs schémas de signature est actuellement de plusieurs dizaines de Koctets, alors qu’on sait construire des schémas avec des signatures de l’ordre de moins d’un Koctet. De nouvelles techniques doivent être trouvées ou de nouveaux problèmes pour améliorer l’efficacité de ces schémas. Enfin, certaines preuves ZK utilisant les réseaux ou pour construire des signatures aveugles ou avec d’autres propriétés sont volumineuses, plusieurs dizaines de Koctets. Nous souhaitons voir si ces nouvelles techniques peuvent être utilisées pour construire ces signatures plus efficacement.
• Attaque par canaux auxiliaires: Il n’existe pas de travaux actuellement concernant la sécurité des implémentations de schémas de signature MPCitH contre les attaques par canaux auxiliaires. Nous voulons monter de telles attaques et ensuite les protéger en utilisant des techniques de masquage. Le masquage permet d’obtenir des preuves de sécurité des implémentations, mais les contre-mesures sont quelquefois trop grosses en fonction de l’ordre de masquage. Avoir des contre-mesures efficaces et sûres est un problème difficile.

Approche méthodologique et critères de qualité des résultats obtenus

La démarche s'articulera autour des axes suivants :

• Étudier les techniques de constructions de schémas MPCitH. Cette partie est difficile car plusieurs techniques de calcul sécurisées multiparties sont actuellement utilisées.
• Attaquer la sécurité des candidats proposés par exemple à la compétition du NIST. En effet, même si le problème ne repose pas sur des instances faibles, les cryptographes utilisent quelque fois des variantes des problèmes difficiles et il se trouve que ces variantes sont plus faibles que le problème initial [5].
• Construire de nouveaux schémas en utilisant des problèmes difficiles sur les réseaux euclidiens et obtenir des signatures avec une taille inférieure à 10 Koctets.
• Étudier la sécurité des implémentations en utilisant les attaques par canaux auxiliaires contre ces schémas.
• Étudier la sécurité des implémentations en utilisant des techniques de masquage et en faisant des preuves de sécurité.

La qualité de la thèse s’évaluera en grande partie sur la qualité des publications dans des conférences A* et A du domaine, e.g. TCHES, Eurocrypt, Crypto, Asiacrypt et PKC.

État de l'art s’appuyant sur un choix de publications importantes liées au sujet
L’état de l’art s’appuie sur les thèses qui ont été récemment soutenues dans le domaine comme la thèse de Thibauld Feneuil [7]. Puis, les articles sur les techniques de MPC comme [1,8] et les techniques de preuves comme Labrador [6]. Enfin, les spécifications des différents schémas de signature soumis à la compétition du NIST. Pour ce qui est des techniques de masquages, on utilisera [9] et [10].