La cryptographie multivariée peut être définie comme la cryptographie à clé publique basée sur la difficulté de résoudre des systèmes polynomiaux à plusieurs variables. Bien que la recherche de tels schémas soit apparue dès le début des années 80, elle s'est surtout développée depuis une dizaine d'années, et a conduit à plusieurs propositions jugées promet-teuses, telles que le cryptosystème HFE et le schéma de signature SFLASH. Les shémas multivariés se posent ainsi en alternative possible aux schémas traditionnels basés sur des problèmes de théorie des nombres, et constituent des solutions efficaces pour l'implantation des fonctionnalités de la cryptographie à clé publique. Lors d'Eurocrypt 2005, Fouque, Granboulan et Stern ont proposé une nouvelle approche cryptanalytique pour les schémas multivariés basée sur l'étude d'invariants liés à la différentielle, et ont démontré la pertinence de cette approche par la cryptanalyse du schéma PMI proposé par Ding. Au cours de cette thèse, nous avons développé l'approche différentielle proposée par Fouque et al. dans deux directions. La première consiste en un traitement combinatoire des invariants dimensionnels de la différentielle. Ceci nous a permis de montrer qu'une clé publique HFE pouvait être distinguée d'un système quadratique aléatoire en temps quasipolynomial. Une seconde application de cette même approche nous a permis de cryptanalyser une variation de HFE proposée par Ding et Schmidt à PKC 2005. Le second développement de la thèse est la découverte d'invariants fonctionnels de la différentielle et nous a permis de montrer la faiblesse du schéma SFLASH.

En 1978, McEliece introduit un schéma de chiffrement à clé publique issu de la théorie des codes correcteurs d’erreurs. L’idée du schéma de McEliece est d’utiliser un code correcteur dont lastructure est masquée, rendant le décodage de ce code difficile pour toute personne ne connaissant pas cette structure. Le principal défaut de ce schéma est la taille de la clé publique. Dans ce contexte, on se propose d'étudier l'utilisation de codes dont on connaît une représentation compacte, en particulier le cas de codes quais-cyclique ou quasi-dyadique. Les deux familles de codes qui nous intéressent dans cette thèse sont: la famille des codes alternants et celle des sous--codes sur un sous--corps de codes géométriques. En faisant agir un automorphisme $sigma$ sur le support et le multiplier des codes alternants, on saitqu'il est possible de construire des codes alternants quasi-cycliques. On se propose alors d'estimer la sécurité de tels codes à l'aide du textit{code invariant}. Ce sous--code du code public est constitué des mots du code strictement invariant par l'automorphisme $sigma$. On montre ici que la sécurité des codes alternants quasi-cyclique se réduit à la sécurité du code invariant. Cela est aussi valable pour les sous—codes sur un sous--corps de codes géométriques quasi-cycliques. Ce résultat nous permet de proposer une analyse de la sécurité de codes quasi-cycliques construit sur la courbe Hermitienne. En utilisant cette analyse nous proposons des clés compactes pour la schéma de McEliece utilisant des sous-codes sur un sous-corps de codes géométriques construits sur la courbe Hermitienne. Le cas des codes alternants quasi-dyadiques est aussi en partie étudié. En utilisant le code invariant, ainsi que le textit{produit de Schur}et le textit{conducteur} de deux codes, nous avons pu mettre en évidence une attaque sur le schéma de McEliece utilisant des codes alternants quasi-dyadique de degré $2$. Cette attaque s'applique notamment au schéma proposé dans la soumission DAGS, proposé dans le contexte de l'appel du NIST pour la cryptographie post-quantique. / In 1978, McEliece introduce a new public key encryption scheme coming from errors correcting codes theory. The idea is to use an error correcting code whose structure would be hidden, making it impossible to decode a message for anyone who do not know a specific decoding algorithm for the chosen code. The McEliece scheme has some advantages, encryption and decryption are very fast and it is a good candidate for public-key cryptography in the context of quantum computer. The main constraint is that the public key is too large compared to other actual public-key cryptosystems. In this context, we propose to study the using of some quasi-cyclic or quasi-dyadic codes. In this thesis, the two families of interest are: the family of alternant codes and the family of subfield subcode of algebraic geometry codes. We can construct quasi-cyclic alternant codes using an automorphism which acts on the support and the multiplier of the code. In order to estimate the securtiy of these QC codes we study the em{invariant code}. This invariant code is a smaller code derived from the public key. Actually the invariant code is exactly the subcode of code words fixed by the automorphism $sigma$. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on the invariant code. This is also true in the case of QC algebraic geometry codes. This result permits us to propose a security analysis of QC codes coming from the Hermitian curve. Moreover, we propose compact key for the McEliece scheme using subfield subcode of AG codes on the Hermitian curve. The case of quasi-dyadic alternant code is also studied. Using the invariant code, with the em{Schur product} and the em{conductor} of two codes, we show weaknesses on the scheme using QD alternant codes with extension degree 2. In the case of the submission DAGS, proposed in the context of NIST competition, an attack exploiting these weakness permits to recover the secret key in few minutes for some proposed parameters.

En cette ère numérique, l’utilisation des documents papier s’avère peu pratique et inefficace, ce qui motive les sociétés à évoluer vers l’utilisation des documents électroniques (ou e-docs). Ce désir d’innover vers une opération sans papier peut améliorer l’efficacité et la qualité des services d’administrations publiques ou privées de manière à accélérer leurs activités et en même temps mieux satisfaire les besoins des clients. Cependant, cette pratique a créé des nouveaux besoins, tels que la signature numérique réelle de documents. Dans ce mémoire, nous avons proposé un nouveau schéma de signature numérique utilisant FIDO2, qui se trouve être une nouvelle norme d’authentification sécurisée en ligne basée sur la signature numérique. Le fait que FIDO2 soit un standard libre permet aux développeurs de logiciel et de matériel d’implémenter plus facilement leurs propres produits. Cela nous a inspiré à l’utiliser pour une fin de signature numérique, l’idée étant de remplacer le défi envoyé par le serveur avec le hash de e-docs et de l’envoyer à l’appareil du signataire afin que ce dernier signe avec sa clé privée. Comme dans le cas de l’infrastructure à clé publique, chaque utilisateur possédait une paire de clés, c’est-à-dire une clé privée et une clé publique. Un signataire doit confirmer son identification biométrique (empreinte digitale, reconnaissance faciale, voix, etc.) ou son code PIN pour accéder à la clé privée stockée localement sur son appareil et signer un document. Au cours de notre recherche, nous avons effectué plusieurs tests avec différents équipements (PC, USB FIDO, Smartphone) ainsi que différentes OS (Android, iOS, Windows). Les résultats de nos tests nous montrent que nous pouvons utiliser FIDO2 pour signer un document électronique. Cette nouvelle approche proposée peut être utilisée pour une signature face à face (en locale) ou à distance (en ligne). Le prototype développé pour la mise en œuvre de notre approche a été validé auprès d’usagers types (membres clients et conseillers) dans une entreprise. / In this digital era, the use of paper documents is impractical and inefficient, which motivates companies to move towards the use of electronic documents (or e-docs). This desire to innovate towards a paperless operation can improve the efficiency and quality of public or private administration services so as to speed up their activities and at the same time better meet customer needs. However, this practice has created new needs, such as the actual digital signature of documents. In this thesis, we have proposed a new digital signature scheme using FIDO2, which happens to be a new standard for secure online authentication based on digital signatures. The fact that FIDO2 is a free standard makes it easier for software and hardware developers to implement their own products. This inspired us to use it a digital signature purpose, the idea being, to replace the challenge sent by the server with the hash of e-docs and send it to the signer’s device so that the latter signs with his private key. As with public key infrastructure, each user had a key pair, that is, a private key and a public key. A signatory must confirm their biometric identification (fingerprint, facial recognition, voice, etc.) or PIN code to access the private key stored locally on their device and sign a document. During our research, we carried out several tests with different equipment (PC, USB FIDO, Smartphone) as well as different OS (Android, iOS, Windows). The results of our tests show us that we can use FIDO2 to sign an electronic document. This proposed new approach can be used for a face-to-face (local) or remote (online) signature. The prototype developed for the implementation of our approach has been validated with typical users (member-clients and advisers) in a company.

Les questions d'anonymat surgissent dans de nombreux contextes et tout particulièrement dans celui des transactions électroniques. Il est souvent souhaitable de protéger l'identité des participants afin d'éviter la constitution de profils de consommateurs ou de bases de données de renseignements commerciaux. De nombreuses solutions cryptographiques ont été apportées afin de renforcer la confiance des utilisateurs dans ces applications. Une nouvelle approche dans l'élaboration de mécanismes d'anonymat sûrs et performants s'appuie sur des applications bilinéaires (couplages de Weil et de Tate sur les courbes elliptiques). Dans cette thèse nous présentons tout d'abord un état de l'art des différentes signatures utilisées pour l'anonymat en cryptographie, en particulier les signatures de groupe, les signa- tures aveugles et les signatures d'anneau. Dans ce contexte nous décrivons un nouveau protocole d'authentification et montrons comment il peut être converti en signature d'anneau. Notre étude porte ensuite sur les signatures aveugles à anonymat révocable. Il s'agit de signatures aveugles dont l'anonymat et l'intraçabilité peuvent être révoqués par une autorité. Nous proposons le pre- mier véritable modèle de sécurité pour ces signatures, ainsi qu'une nouvelle construction basée sur les couplages dont nous prouvons la sécurité dans ce modèle. Nos derniers travaux portent sur les systèmes de multi-coupons et de monnaie électronique. L'utilisation des couplages nous permet d'introduire de nouvelles propriétés destinées à faciliter leur usage. Pour chacun de ces systèmes nous proposons un modèle de sécurité, puis décrivons un schéma dont nous prouvons la sécurité dans ce modèle.

Les schémas de Chiffrement Complètement Homomorphe (FHE) permettent de manipuler des données chiffrées avec grande flexibilité : ils rendent possible l'évaluation de fonctions à travers les couches de chiffrement. Depuis la découverte du premier schéma FHE en 2009 par Craig Gentry, maintes recherches ont été effectuées pour améliorer l'efficacité, atteindre des nouveaux niveaux de sécurité, et trouver des applications et liens avec d'autres domaines de la cryptographie. Dans cette thèse, nous avons étudié en détail ce type de schémas. Nos contributions font état d'une nouvelle attaque de récuperation des clés au premier schéma FHE, et d'une nouvelle notion de sécurité en structures hierarchiques, évitant une forme de trahison entre les usagers tout en gardant la flexibilité FHE. Enfin, on décrit aussi des implémentations informatiques. Cette recherche a été effectuée au sein du Laboratoire de Mathématiques de Versailles avec le Prof. Louis Goubin. / Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since the groundbreaking discovery of the first FHE scheme in 2009 by Craig Gentry, an impressive amount of research has been conducted to improve efficiency, achieve new levels of security, and describe real applications and connections to other areas of cryptography. In this Dissertation, we first give a detailed account on research these past years. Our contributions include a key-recovery attack on the ideal lattices FHE scheme and a new conception of hierarchic encryption, avoiding at some extent betrayal between users while maintaining the flexibility of FHE. We also describe some implementations. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin.

Les problématiques de respect de la vie privée sont aujourd'hui indissociables des technologies modernes. Dans ce contexte, cette thèse s'intéresse plus particulièrement aux outils cryptographiques et à la façon de les utiliser pour répondre à ces nouvelles questions.Dans ce mémoire, je m'intéresserai tout d'abord aux preuves de connaissance sans divulgation qui permettent notamment d'obtenir la propriété d'anonymat pour les usagers de services de télécommunications. Je proposerai ainsi une nouvelle solution de preuve de connaissance d'un secret appartenant à un intervalle, ainsi que la première étude comparative des preuves existantes sur ce sujet. Je décrirai ensuite une nouvelle méthode permettant de vérifier efficacement un ensemble de preuves de type "Groth-Sahaï'', accélérant ainsi considérablement le travail du vérifieur pour de telles preuves. Dans un second temps, je m'intéresserai aux signatures caméléons. Celles-ci permettent de modifier, sous certaines conditions, un message signé. Ainsi, pour ces schémas, il est possible d'exhiber, à l'aide d'une trappe, une signature valide du signataire initial sur le message modifié. Je proposerai d'abord un nouveau schéma qui est à ce jour le plus efficace dans le modèle simple. Je m'intéresserai ensuite à certaines extensions de ce modèle qui ont pour vocation de donner au signataire les moyens de garder un certain contrôle sur les modifications faites a posteriori sur le message initial. Je décrirai ainsi à la fois le nouveau modèle de sécurité et les schémas associés prenant en compte ces nouvelles extensions. Enfin, je présenterai un ensemble d'applications se basant sur les briques cryptographiques introduites ci-dessus et qui permettent d'améliorer la protection de la vie privée des utilisateurs. J'aborderai tout particulièrement les problématiques d'abonnement, d'utilisation ou de facturation de services, ainsi que la gestion de contenus protégés dans un groupe hiérarchisé. / Privacy is, nowadays, inseparable from modern technology. This is the context in which the present thesis proposes new cryptographic tools to meet current challenges.Firstly, I will consider zero-knowledge proofs of knowledge, which allow in particular to reach the anonymity property. More precisely, I will propose a new range proof system and next give the first comparison between all existing solutions to this problem. Then, I will describe a new method to verify a set of ``Groth-Sahaï'' proofs, which significantly decreases the verification time for such proofs.In a second part, I will consider sanitizable signatures which allow, under some conditions, to manipulate (we say ``sanitize'') a signed message while keeping a valid signature of the initial signer. I will first propose a new scheme in the classical case. Next, I will introduce several extensions which enable the signer to obtain better control of the modifications done by the ``sanitizer''. In particular, I will propose a new security model taking into account these extensions and give different schemes achieving those new properties.Finally, I will present different applications of the above cryptographic tools that enhance customer privacy. In particular, I will consider the questions of subscription, use and billing of services and also address the issue of managing protected content in a hierarchical group.

Dans cette thèse, j'étudie deux aspects distincts de la cryptographie basée sur les courbes elliptiques et hyperelliptiques. Dans une première partie, je confronte deux méthodes de calcul de couplages, originales car ne reposant pas sur le traditionnel algorithme de Miller. Ainsi, dans [42], K. Stange calcula le couplage de Tate sur une courbe elliptique à partir d'un nouvel outil, les elliptic nets. Y. Uchida et S. Uchiyama généralisèrent ces objets au cas hyperelliptique ([47]), mais ne donnèrent un algorithme pour le calcul de couplages que dans le cas des courbes de genre 2. Mon premier travail dans cette thèse fut de donner cet algorithme pour le cas général. De leur côté, D. Lubicz et D. Robert donnèrent dans [28] une autre méthode de calcul de couplage, basée sur les fonctions thêta. Le second résultat de ma thèse est de réunifier ces deux méthodes : je montre que la formule de récurrence à la base des nets est une conséquence des formules d'addition des fonctions thêta utilisées dans l'algorithme de Lubicz et Robert. Dans la seconde partie de ma thèse, je me suis intéressé à l'algorithme de calcul d'index attaquant le problème du logarithme discret sur les courbes elliptiques et hyperelliptiques. Dans le cas elliptique, une des étapes principales de cette attaque repose sur les polynômes de Semaev. Je donne une nouvelle construction ces polynômes en utilisant la fonction sigma de Weierstrass, pour pouvoir ensuite les généraliser pour la première fois au cas hyperelliptique. / In this thesis, I study two different aspects of elliptic and hyperelliptic curves based cryptography.In the first part, I confront two methods of pairings computation, whose original feature is that they are not based the traditional Miller algorithm. Therefore, in [42], K. Stange computed Tate pairings on elliptic curves using a new tool, the elliptic nets. Y. Uchida and S. Uchiyama generalized these objects to hyperelliptic case ([47]), but they gave an algorithm for pairing computation only for the genus 2 case. My first work in this thesis was to give this algorithm for the general case. Meanwhile, D. Lubicz and D. Robert gave in [28] an other pairing computation method, based on theta functions. The second result of my thesis is the reunification of these two methods : I show that the recurrence equation which is the basis of nets theory is a consequence of the addition law of theta functions used in the Lubicz and Robert’s algorithm. In the second part, I study the index calculus algorithm attacking the elliptic and hyperelliptic curve discrete logarithm problem. In the elliptic case, one of the main steps of this attack requires the Semaev polynomials. I reconstruct these polynomials using Weierstrass sigma function, with the purpose of giving their first hyperelliptic generalization.

La cryptographie à base de réseaux euclidiens est aujourd'hui un domaine scientifique en pleine expansion et connait une évolution rapide et accélérée par l'attractivité du chiffrement complètement homomorphe ou des applications multilinéaires cryptographiques. Ses propriétés sont très attractives : une sécurité pouvant être réduite à la difficulté des pires cas de problèmes sur les réseaux euclidiens, une efficacité asymptotique quasi-optimale et une résistance présupposée aux ordinateurs quantiques. Cependant, on dénombre encore peu de résultats de recherche sur les constructions à visée pratique pour un niveau de sécurité fixé. Cette thèse s'inscrit dans cette direction et travaille à réduire l'écart entre la théorie et la pratique de la cryptographie à clé publique récente. Dans cette thèse, nous concevons et implémentons une signature numérique basée sur les réseaux euclidiens, deux schémas de chiffrement complètement homomorphe et des applications multilinéaires cryptographiques. Notre signature digitale ultra-performante, BLISS, ouvre la voie à la mise en pratique de la cryptographie à base de réseaux sur petites architectures et est un candidat sérieux à la cryptographie post-quantique. Nos schémas de chiffrement complètement homomorphes permettent d'évaluer des circuits non triviaux de manière compétitive. Finalement, nous proposons la première implémentation d'applications multilinéaires et réalisons, pour la première fois, un échange de clé non interactif entre plus de trois participants en quelques secondes.

La cryptographie basée sur les réseaux a connu depuis quelques années un très fort développement notamment du fait qu’il existe des systèmes cryptographiques basés sur les réseaux avec des propriétés de sécurité plus fortes que dans les cas plus classiques de théorie des nombres. Les problèmes difficiles des réseaux, par exemple le problème de trouver des vecteurs courts non nuls, semblent résister aux attaques utilisant des ordinateurs quantiques et les meilleurs algorithmes qui existent pour les résoudre sont exponentiels en fonction du temps. L’objet de cette thèse est la construction de primitives cryptographiques à clé publique pour l’ano- nymat dont la sécurité repose sur des problèmes difficiles des réseaux.Nous nous intéressons aux schémas de signature de cercle. Tout d’abord, nous proposons une nouvelle définition d’anonymat et nous exposons un nouveau schéma de signature de cercle. Ensuite, nous donnons une étude de sécurité rigoureuse suivant deux définitions de résistance la contrefaçon. La première est la résistance à la contrefaçon contre les attaques à sous-cercles choisis et la deuxième est la résistance à la contrefaçon contre les attaques de corruption interne.Nous présentons ensuite un nouveau schéma d’identification de cercle et nous développons une analyse complète de sa sécurité. Enfin, nous montrons que les techniques utilisées pour construire le schéma précédent peuvent être utilisées pour construire un schéma d’identification de cercle à seuil. / Lattice-based cryptography has known during the last decade rapid develop- ments thanks to stronger security properties. In fact, there exist lattice-based cryp- tographic systems whose security is stronger than those based on the conventional number theory approach. The hard problems of lattices, for example the problem of finding short non-zero vectors, seems to resist quantum computers attacks. Mo- reover, the best existing algorithms solving them are exponential in time. The pur- pose of this thesis is the construction of public key cryptographic primitives for anonymity, whose security is based on the latter.In particular, we are interested in ring signature schemes. First, we propose a new formal definition of anonymity and we present a new ring signature scheme. Second, we give a rigorous study of security, following two definitions of unfor- geability. The first of which is unforgeability against chosen-subring attacks and the other one is unforgeability with respect to insider corruption.Afterwards, we present a new ring identification scheme and we develop a full analysis of its security. Finally, we show that the techniques used to build this scheme, can be used to construct a threshold ring identification scheme.

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art. / Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.