De nos jours, la cryptographie fait partie intégrante de notre quotidien. Initialement destinée à être utilisée pour les interactions entre humains, elle est aujourd’hui employée pour les interactions avec et entre des machines. À travers cette thèse, nous présenterons nos diverses contributions couvrant une partie du spectre de la cryptographie interactive. Dans un premier temps, nous la verrons comme un outil au service de l’apprentissage automatique. Nous montrerons qu’elle peut permettre à un client et à un serveur d’interagir afin de faire évaluer les données du client par le modèle du serveur, sans qu’aucun d’eux n’apprenne d’information confidentielle au sujet de l’autre. Ensuite, nous étendrons la notion déjà existante de Smooth Projective Hash Functions pour la rendre plus compatible avec la cryptographie post-quantique, et notamment les réseaux euclidiens. Cette extension servira de base à la construction de Transferts Inconscients, largement déployés aujourd’hui dans le cadre de Calculs Multipartites Sécurisés. Finalement, nous nous intéresserons à la cryptographie à bas-coût, permettant à des appareils techniquement limités d’interagir entre eux tout en jouissant d’une sécurité suffisante. Plus précisément, nous étudierons la sécurité d’un protocole authentifié d’échange de clés optimisé pour de tels appareils, permettant d’établir une communication sécurisée entre eux.
De nos jours, la cryptographie fait partie intégrante de notre quotidien. Initialement destinée à être utilisée pour les interactions entre humains, elle est aujourd’hui employée pour les interactions avec et entre des machines. À travers cette thèse, nous présenterons nos diverses contributions couvrant une partie du spectre de la cryptographie interactive. Dans un premier temps, nous la verrons comme un outil au service de l’apprentissage automatique. Nous montrerons qu’elle peut permettre à un client et à un serveur d’interagir afin de faire évaluer les données du client par le modèle du serveur, sans qu’aucun d’eux n’apprenne d’information confidentielle au sujet de l’autre. Ensuite, nous étendrons la notion déjà existante de Smooth Projective Hash Functions pour la rendre plus compatible avec la cryptographie post-quantique, et notamment les réseaux euclidiens. Cette extension servira de base à la construction de Transferts Inconscients, largement déployés aujourd’hui dans le cadre de Calculs Multipartites Sécurisés. Finalement, nous nous intéresserons à la cryptographie à bas-coût, permettant à des appareils techniquement limités d’interagir entre eux tout en jouissant d’une sécurité suffisante. Plus précisément, nous étudierons la sécurité d’un protocole authentifié d’échange de clés optimisé pour de tels appareils, permettant d’établir une communication sécurisée entre eux.
Contribution à la cryptographie interactive De nos jours, la cryptographie fait partie intégrante de notre quotidien. Initialement destinée à être utilisée pour les interactions entre humains, elle est aujourd’hui employée pour les interactions avec et entre des machines. À travers cette thèse, nous présenterons nos diverses contributions couvrant une partie du spectre de la cryptographie interactive. Dans un premier temps, nous la verrons comme un outil au service de l’apprentissage automatique. Nous montrerons qu’elle peut permettre à un client et à un serveur d’interagir afin de faire évaluer les données du client par le modèle du serveur, sans qu’aucun d’eux n’apprenne d’information confidentielle au sujet de l’autre. Ensuite, nous étendrons la notion déjà existante de Smooth Projective Hash Functions pour la rendre plus compatible avec la cryptographie post-quantique, et notamment les réseaux euclidiens. Cette extension servira de base à la construction de Transferts Inconscients, largement déployés aujourd’hui dans le cadre de Calculs Multipartites Sécurisés. Finalement, nous nous intéresserons à la cryptographie à bas-coût, permettant à des appareils techniquement limités d’interagir entre eux tout en jouissant d’une sécurité suffisante. Plus précisément, nous étudierons la sécurité d’un protocole authentifié d’échange de clés optimisé pour de tels appareils, permettant d’établir une communication sécurisée entre eux.
Cette these s'est elaboree dans cette periode de l'histoire de la cryptographie quantique ou plusieurs protocoles avaient ete proposes sans que leur fiabilite n'ait pu etre encore demontree, du moins pas face a toute attaque. De plus, certaines des attaques qui avaient ete mises de cote etaient en fait accessibles a l'aide de la technologie actuelle.
D'un autre cote, le but de la cryptographie quantique a toujours ete la conception de protocoles inconditionnellement fiables, cest-a-dire, fiables face a toute attaque permise par les lois de la physique sans consideration pour aucune contrainte dans le temps ou dans l'espace. Tel etait le niveau de fiabilite espere des protocoles quantiques proposes. Seule la cryptographie quantique pouvait meme oser offrir un tel niveau de securite.
Une certaine application appelee la mise en gage jouait un role primordial dans l'ensemble des applications proposees par les cryptographes quantiques et une preuve de securite inconditionnelle avait ete proposee par Brassard, Crepeau, Jozsa et Langlois pour un protocole realisant cette tache. Notre objectif de depart etait de demontrer que les protocoles de la cryptographie quantique permettent effectivement de realiser avec une securite inconditionnelle la plupart des applications proposees, pas seulement la mise en gage. Cependant, a notre grande surprise et a l'etonnement de plusieurs, nous avons au contraire demontre qu'un protocole quantique de mise en gage inconditionnelle fiable est impossible et ainsi avons remis serieusement en question une partie importante des applications de la cryptographie quantique, en plus d'avoir demoli la preuve mentionnee plus haut. Par contre, en nous appuyant sur les travaux de Bennett, Brassard, Crepeau, Salvail et plus recemment de Yao, nous avons obtenu une preuve de la securite inconditionnelle d'un protocole quantique de distribution de cle.
Un des principes importants que nous avons utilises dans notre these est celui qui dit que tous les phenomenes peuvent etre decrits comme l'execution d'une mesure quantique. De plus, nous avons utilise le fait que cette mesure peut elle-meme etre decrite comme une transformation unitaire sur le systeme qui est compose du systeme mesure, de l'appareil de mesure et du systeme final si celui-ci est different du systeme initial.
Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication .
Cryptographie classique et post-quantiqueCes nouvelles solutions doivent s'appuyer sur des problèmes mathématiques qui ne sont pas vulnérables à l'avantage qu'ont les ordinateurs quantiques sur les primitives cryptographiques se basant sur des problèmes mathématiques dits "standards".Ces outils mathématiques "standards" se composent notamment du cryptosystème RSA [RSA78] (du nom de ses auteurs Rivest, Shamir et Adleman) qui repose sur le problème de la factorisation, ou du cryptosystème El-Gamal reposant sur le problème du logarithme discret.Dans le cas des cryptosystèmes de type RSA, la clé secrète est composée entre autre de deux nombres premiers p et q dont leur produit N = p×q fait partie de la clé publique.Un attaquant qui arriverait donc à factoriser le nombre N pour retrouver les deux nombres premiers p et q, pourrait attaquer la sécurité des schémas de type RSA.Concernant les cryptosystèmes basés sur le logarithme discret, on considère un groupe G bien choisi, le plus souvent d'ordre premier p.On va ensuite choisir aléatoirement un entier a comme partie de la clé secrète et son pendant publique qui lui est associé est g a avec g un élément choisi aléatoirement dans le groupe G. On définit alors le problème du logarithme discret, demandant de retrouver l'entier a à partie de l'élément g a appartenant au groupe G.Ces deux types de problèmes ont été à l'origine de nombreux schémas cryptographiques sûrs et proposant une efficacité très attractive mais, comme énoncé précédemment, ils seront vulnérables dans une ère post-quantique.En effet, conserver leur sécurité impli- ContributionsDans la suite de cette introduction, je vais détailler les contributions que j'ai pu apportées durant mes 3 années de thèses, qui concernent principalement la conception de schémas cryptographiques respectueux de la vie privée, ainsi que l'adaptation en cas Signatures de groupesMa première contribution concerne la construction d'une signature de groupe sur les réseaux euclidiens, à laquelle nous ajoutons quelques propriétés attractives.Par définition, une signature de groupe est un schéma permettant à un groupe d'utilisateurs de signer au nom de ce même groupe, tout en restant anonyme parmi ses membres.Elles fournissent une caractéristique supplémentaire qui est de permettre "l'ouverture" d'une signature pour en retrouver le membre du groupe qui en est à l'origine.Ces schémas ont de nombreuses applications dans la vie courante.Prenons par exemple un cas où une personne doit prouver qu'elle a un certain âge (par exemple moins de 25 ans pour pouvoir prétendre à une réduction), il suffirait qu'elle produise sa carte d'identité qui contient sa date de naissance et donc son âge.Cependant en produisant ainsi sa carte d'identité, elle fournit par la même occasion son nom, son adresse..., alors que seul le fait qu'elle appartient au groupe des moins de 25 ans est nécessaire.Les signatures de groupes permettent donc d'éviter de tels désagréments.Il existe à ce jour de nombreux schémas de signature de groupe, mais les plus efficaces d'entre eux s'appuient sur des hypothèses qui ne résisteraient pas à un ordinateur quantique, tels que le logarithme discret défini précédemment.C'est pourquoi depuis une dizaine d'années, un grand nombre de constructions basées sur les réseaux euclidiens ont été conçues ([Gol+10; Lag+13; Lan+14; Lib+16b; Lin+17]...).Ces constructions doivent cependant se plier à l'inefficacité, sur les réseaux, des preuves de connaissance à divulgation nulle de connaissance nécessaires pour de telles constructions dans le modèle habituel de Bellare et al [BMW03].Cependant en 2019, un nouveau schéma publié à Eurocrypt par Kastumata et Yamada [KY19] s'écarte de ce modèle habituel.Leur construction s'appuie sur des primitives plus récentes telles que les signatures basées sur les attributs pour court-circuiter les problèmes d'inefficacité, en plus de reposer sur un modèle de sécurité plus commun.À partir de cette nouvelle construction nous proposons un schéma de signature de groupe basé sur les réseaux qui bénéficie des mêmes avantages que le schéma de [KY19] et nous ajoutons en plus une nouvelle propriété appelée forward security.Celle-ci permet de diviser le temps en plusieurs périodes, de sorte que les clés secrètes de tous les membres du groupe sont mises à jour à chaque nouvelle période de temps sans possibilité de récupérer Signature aveugleLes signatures aveugles ont été introduites en 1982 par Chaum [Cha82] pour le cas d'usage précis de la monnaie électronique.L'idée d'une signature aveugle est la suivante: un utilisateur veut générer une signature sur un message de son choix, cependant il ne possède pas la clé secrète lui permettant de générer une telle signature.Pour palier ce problème, il a la possibilité d'interagir avec une autorité qui possède cette clé secrète et qui est alors vu comme un signeur.Cependant l'utilisateur requiert que la signature qu'il va sortir à la fin de l'interaction avec le signeur ne puisse pas être tracée par ce dernier.Pour en revenir au cas d'usage de la monnaie électronique, ce type de schéma permet donc à un utilisateur de faire certifier de la monnaie électronique à une autorité (une banque par exemple), sans que celle-ci puisse retrouver l'identité de l'utilisateur lorsque celui-ci la dépense.Concernant les constructions existantes, elles sont nombreuses et très efficaces sur la cryptographie "classique".Nous pouvons notamment citer le schéma Blind RSA [Fer93] qui se base sur le cryptosystème RSA, tandis que l'histoire des signatures aveugles sur les réseaux euclidiens est bien plus complexes.Tout d'abord il n'existe qu'un seul modèle de construction basé sur un schéma d'identification de Lyubashevsky [Lyu08].Ce modèle requiert 3 échanges entre l'utilisateur et le signeur, comme d'autres schémas tel que Okamoto-Schnorr [Oka92], à contrario d'autres constructions comme blind RSA qui n'en demandent que 2.De plus toutes les constructions sur les réseaux euclidiens ont vu leur preuve de sécurité invalidées par un papier de Hauck et al [Hau+20] publié à Crypto 2020.En effet pour prouver qu'un utilisateur malhonnête ne peut pas générer plus de signatures qu'autorisées, une propriété appelée one-more unforgeability est nécessaire.Une modèle de preuve a été proposé par Pointcheval et Stern [PS00] pour des constructions basées sur des groupes finis, dans lesquels un élément secret était choisi aléatoirement dans tout le groupe.La différence sur les réseaux euclidiens vient du fait qu'une clé secrète est habituellement un petit élément de l'ensemble considéré, ce qui interdit toute adaptation directe sur les réseaux euclidiens de la preuve de Pointcheval et Stern.Dans notre construction, nous revenons sur cette preuve et sur la solution apportée par Hauck et al. [Hau+20] qui souffre d'un manque d'efficacité.Concernant notre construction, notre sécurité repose sur une conjecture qui n'a pas été prouvée.Tout d'abord, notre solution gagne en efficacité en utilisant l'avantage de distributions gaussiennes sur des distributions uniformes.De plus, nous utilisons des outils tels que les trappes sur les réseaux euclidiens pour effacer toute trace d'abandon durant le protocole de signature aveugle, notre construction étant la seule n'ayant pas recours aux abandons, qui est un impact négatif sur l'efficacité.Finalement, nous proposons une variante appelée signature partiellement aveugle, qui permet à l'utilisateur et au signeur d'inclure une information publique, sur laquelle ils se sont mis d'accord en amont de la génération de la signature.Notre construction n'entraîne quasiment aucun coût supplémentaire par rapport à la signature aveugle.Ce travail est décrit dans le chapitre 5 de cette thèse.
La conception d’ordinateurs quantiques aura un impact majeur sur la cryptographie que nous utilisons tous les jours pour sécuriser nos communications, en particulier sur la cryptographie dite asymétrique. De plus, la multiplication des objets connectés dans notre quotidien et leurs limitations en terme de capacité de calcul et de mémoire disponible en font des cibles privilégiées. Cette thèse est à la croisée des chemins de ces deux problématiques, et est découpée en trois axes d’études indépendants. Le premier porte sur la conception d’une primitive cryptographique appelée Hash Proof System (HPS). En nous basant sur le langage des chiffrés de RQC, nous allons montrer comment construire une telle primitive, puis nous en présenterons deux applications possibles : un schéma de chiffrement à témoin d’une part, puis un protocole d’échange de clés authentifié uniquement basé sur la connaissance d’un mot de passe commun, permettant ainsi de se passer d’une infrastructure à clé publique. Le deuxième axe d’étude est l’introduction d’un nouveau problème cryptographique, le problème LRE (Learning Rank with Errors), adaptation du problème LPN à la métrique rang. Nous étudierons quelques-unes de ses propriétés puis en présenterons une première application possible, un protocole d’authentification symétrique nommé HBLRE, adaptation du protocole HB au problème LRE. Enfin, le troisième axe d’étude est l’adaptation et l’implémentation de plusieurs schémas cryptographiques soumis au NIST, à savoir RQC et ROLLO (qui regroupe les schémas LAKE, LOCKER et Ouroboros-R) sur microcontrôleurs. Nous montrerons les divers algorithmes qui ont été utilisés et en décrirons leur fonctionnement. Nous présenterons la libraire RBC, une librairie mise au point afin de faciliter l’utilisation et la conception de schémas basés sur la métrique rang qui intègrent les travaux d’implémentation réalisés durant cette thèse. Enfin, nous présenterons les performances de ces implémentations sur un microcontrôleur doté d’un processeur de type ARM Cortex-M4 et les mettrons en perspective avec les performances d’autres schémas cryptographiques post-quantiques soumis à l’appel à standardisation du NIST.
Sécurité étendue de la cryptographie fondée sur les réseaux Euclidiens La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.