Le développement de la société de l'information et de la monnaie virtuelle, a soulevé de nouveaux problèmes aux communautés de la sécurité et du circuit intégré, faisant devenir la cryptologie un outil incontournable permettant de répondre aux exigences sécuritaires telles que l'identification, l'authentification ou la confidentialité. L'intégration des primitives cryptographiques dans différents dispositifs électroniques est largement répandue aujourd'hui dans le domaine des communications, des services financiers, des services gouvernementaux ou de la PayTV. Au premier rang de ces dispositifs, figure la carte à puce. D'après un rapport publié en août 2010, IMS Research prévoit que le marché de la carte à puce atteindra les 5.8 milliards d'unités vendues en fin d'année. La grande majorité est utilisée dans les télécommunications (carte SIM) et les services bancaires. La carte à puce incorpore un circuit intégré qui peut être, soit un processeur dédié aux calculs cryptographiques, soit seulement de la mémoire non-volatile ou les deux. Ces circuits intégrés manipulent et contiennent donc des secrets comme les clefs secrètes ou privées utilisées par les algorithmes de cryptographie symétriques ou asymétriques. Ces clefs doivent donc, rester absolument confidentielles et intègres afin de garantir la chaîne de sécurité. Par conséquent la robustesse des cartes à puces aux attaques cryptographiques est cruciale. En effet, les attaques sur les circuits intégrés sont aujourd'hui très performantes. Elles peuvent être classées selon trois grandes familles : invasives, semi-invasives et non-invasives. 1- Les attaques invasives sont des attaques menées en général par des experts et requièrent du matériel spécifique. 2- Les attaques semi-invasives, famille d'attaques récemment introduite par l'équipe de Ross Anderson, dont le principe est de décapsuler le package contenant le circuit, afin de se positionner le plus proche possible de la surface, sans pour autant en détériorer les fonctionnalités. 3- Les attaques non-invasives ne nécessitent aucune préparation préalable du dispositif soumis aux attaques. Elles consistent à espionner les phénomènes physiques engendrés par la manipulation des données et notamment les clefs secrètes. Les attaques non-invasives peuvent être considérées comme les plus dangereuses, dans la mesure où ce type d'attaque peut être réalisé sans contact avec le circuit. En effet, pendant l'utilisation d'appareils électroniques, les circuits qui les composent sont soumis à des variations de courant et de tension. Ces variations génèrent des ondes électromagnétiques qui se propagent dans le voisinage du circuit. Ces émanations présentent une corrélation avec des informations censées être stockées dans la puce de façon sécurisée (exemple: la clef secrète d'une carte bancaire utilisée pour l'authentification). Plusieurs attaques dites par canaux auxiliaires, et basées sur ces fuites électromagnétiques ont été publiées par la communauté scientifique ces dernières années. Cette thèse a pour objectifs: (a) comprendre les différentes sources des émanations électromagnétiques des circuits intégrés, et de proposer un flot d'attaque électromagnétique localisée et en champ proche afin de tester la robustesse d'un circuit cryptographique contre les attaques et analyses utilisant le canal électromagnétique, et (b) proposer des contre-mesures afin de contrecarrer ces attaques par analyse de champ électromagnétique. Afin d'atteindre ces objectifs, nous présentons, dans un premier temps, une technique efficace nommée WGMSI (Weighted Global Magnitude Squared Incoherence) pour localiser les positions, au-dessus du circuit cryptographique, qui génèrent les émanations électromagnétiques les plus dépendantes des données secrètes. Dans un deuxième temps la WGMSI est utilisée aussi pour améliorer la stabilité et la convergence des différentes attaques électromagnétiques proposées dans la littérature. La suite de la thèse décrit les différentes contre-mesures aux attaques par canaux auxiliaires. En effet, face à ces techniques d'attaques évoluées, il est primordial, de rendre les fonctions cryptographiques implantées dans les circuits intégrés pour la sécurité (confidentialité, authentification, intégrité ... ), inattaquables en un temps raisonnable et ceci même en manipulant des sous-clefs dans des chiffrements par blocs. Pour cela, on se focalisera principalement aux contre-mesures basées sur des logiques différentielles et dynamiques. Ces contre-mesures sont dites par conception, puisqu'elles se situent au niveau des portes logiques qui sont considérées comme les éléments de base pour la conception d'un circuit intégré. Ceci permet une certaine indépendance des algorithmes cryptographiques vis à vis de l'architecture ou de la technologie considérées. Parmi les différentes logiques différentielles et dynamiques, on s'intéressera plus spécifiquement à la logique STTL (Secure Triple Track logic) qui peut être considérée comme une amélioration de la logique double rail, dans la mesure où un troisième rail est ajouté afin de contrecarrer la faiblesse principale de la logique double rail, à savoir l'évaluation anticipée. Enfin, nous présenterons un flot d'implémentation sur FPGA de la logique STTL prouvée robuste aux attaques par analyse de courant, et nous implémenterons un prototype de DES STTL afin de tester sa robustesse aux attaques électromagnétiques localisées en champ proche. / The integration of cryptographic primitives in different electronic devices is widely used today incommunications, financial services, government services or PayTV.Foremost among these devices include the smart card. According to a report published in August 2010, IMS Research forecasts that the smart card market will reach 5.8 billion units sold in this year. The vast majority is used in telecommunications (SIM) and banking.The smart card incorporates an integrated circuit which can be a dedicated processor for cryptographic calculations. Therefore, these integrated circuits contain secrets such as secret or private keys used by the symmetric or asymmetric cryptographic algorithms. These keys must remain absolutely confidential to ensure the safety chain.Therefore the robustness of smart cards against attacks is crucial. These attacks can be classifiedinto three main categories: invasive, semi-invasive and non-invasive.Non-invasive attacks can be considered the most dangerous, since this kind of attack can be achieved without any contact with the circuit.Indeed, while using electronic circuits that compose them are subjected to variations in current and voltage. These variations generate an electromagnetic radiation propagating in the vicinity of the circuit.These radiations are correlated with secret information (eg a secret key used for authentication). Several attacks based on these leakages were published by the scientific community.This thesis aims to: (a) understand the different sources of electromagnetic emanations of integrated circuits, and propose a localized near field attack to test the robustness of a cryptographic circuit and (b) propose counter-measures to these attacks.

Dans cette thèse, nous étudions les constructions cryptographiques prouvées pour la protection de la vie privée. Pour cela nous nous sommes intéressés aux preuves et arguments à divulgation nulles de connaissance et leurs applications. Un exemple de ces constructions est la signature de groupe. Ce protocole a pour but de permettre à un utilisateur de s'authentifier comme appartenant à un groupe, sans révéler son identité. Afin que les utilisateurs restent responsable de leurs agissements, une autorité indépendante est capable de lever l'anonymat d'un utilisateur en cas de litige. Une telle construction peut ainsi être utilisée, par exemple, dans les systèmes de transport en commun. Un utilisateur qui rentre dans un bus prouve ainsi son appartenance aux utilisateurs possédant un abonnement valide, sans révéler qui il est, et évitant ainsi que la société de transport ne le trace. En revanche, en cas d'incident sur le réseau, la société peut faire appel à la police pour lever l'anonymat des usagers présents au moment de l'incident. Nous avons proposé deux constructions de ces signatures de groupe, prouvées sûres sous des hypothèses simples dans le monde des couplages et des réseaux euclidiens. Dans la continuité de ces travaux, nous avons aussi proposé la première construction de chiffrement de groupe (l'équivalent de la signature de groupe pour le chiffrement) à base de réseaux euclidiens. Finalement, ces travaux nous ont amené à la construction d'un schéma de transfert inconscient adaptatif avec contrôle d'accès à base de réseaux euclidiens. Ces constructions à base de réseaux ont été rendues possibles par des améliorations successives de l'expressivité du protocole de Stern, qui reposait initialement sur la difficulté du problème du décodage de syndrome. / In this thesis, we study provably secure privacy-preserving cryptographic constructions.We focus on zero-knowledge proofs and their applications.Group signatures are an example of such constructions.This primitive allows users to sign messages on behalf of a group (which they formerly joined), while remaining anonymous inside this group.Additionally, users remain accountable for their actions as another independent authority, a judge, is empowered with a secret information to lift the anonymity of any given signature.This construction has applications in anonymous access control, such as public transportations.Whenever someone enters a public transportation, he signs a timestamp. Doing this proves that he belongs to the group of people with a valid subscription.In case of problem, the transportation company hands the record of suspicious signatures to the police, which is able to un-anonymize them.We propose two constructions of group signatures for dynamically growing groups. The first is based on pairing-related assumptions and is fairly practical. The second construction is proven secure under lattice assumptions for the sake of not putting all eggs in the same basket.Following the same spirit, we also propose two constructions for privacy-preserving cryptography.The first one is a group encryption scheme, which is the encryption analogue of group signatures. Here, the goal is to hide the recipient of a ciphertext who belongs to a group, while proving some properties on the message, like the absence of malwares. The second is an adaptive oblivious transfer protocol, which allows a user to anonymously query an encrypted database, while keeping the unrequested messages hidden.These constructions were made possible through a series of work improving the expressiveness of Stern's protocol, which was originally based on the syndrome decoding problem.

Cette thèse traite de la conception de méthodes automatisées ou semi-automatisées pour détecter et identifier des algorithmes cryptographiques dans des programmes compilés en langage machine. La première méthode proposée a pour but l'identification de primitives symétriques. L'implémentation en langage machine d'une primitive symétrique, assimilée à une suite d'instructions, est représentée par un graphe. Sous cette forme, le code est modifié à l'aide de règles de réécriture tout en préservant une certaine notion de sémantique lors d'une phase dite de normalisation. L'objectif est de faire émerger des expressions communes à différentes implémentations d'une même primitive. Ces expressions servent alors de base à la création de signatures efficaces. La recherche de ces signatures s'effectue à l'aide d'un algorithme énumérant les isomorphismes de sous-graphe. La seconde méthode, conçue en complément de la première, produit une représentation synthétique facilitant l'identification des modes opératoires. Cette représentation se définit comme le plus petit sous-graphe préservant les distances entre des sous-ensembles de nœuds précédemment identifiés comme étant les paramètres d'entrée et de sortie des primitives impliquées. / This thesis is about the design of automatic or semi-automatic methods to detect and identify cryptographic algorithms inside programs compiled into machine code. Two methods are presented. The objective of the first method is to identify cryptographic primitives. A machine code implementation of a cryptographic primitive, regarded as a sequence of instructions, is represented by a graph structure. During a normalization phase, a set of rewrite rules is used to modify this graph representation while preserving a specific notion of semantics. The goal is to converge towards expressions which are shared across several implementations of the same primitive. We use these expressions as a basis to create efficient signatures. A subgraph isomorphism enumeration algorithm is used to search for signatures. The second method is built on top of the first one. It produces a synthetic representation designed to help in the identification of modes of operation. This synthetic representation is defined as the smallest subgraph which preserve distances between sets of vertices previously identified as the input and output parameters of the primitives involved within the mode of operation.

Les besoins constants d’innovation en matière de performances et d’économie des ressources nous poussent à effectuer des optimisations dans la conception et l’utilisation des outils cryptographiques. Cela nous amène à étudier plusieurs aspects dans cette thèse : les algorithmes cryptographiques parallèles, les algorithmes cryptographiques incrémentaux et les dictionnaires authentifiés.Dans le cadre de la cryptographie parallèle, nous nous intéressons aux fonctions de hachage basées sur des arbres. Nous montrons en particulier quelles structures arborescentes utiliser pour atteindre un temps d’exécution optimum avec un nombre de processeurs que nous cherchons à minimiser dans un second temps. Nous étudions également d'autres formesd'arborescence favorisant l'équité et la scalabilité.Les systèmes cryptographiques incrémentaux permettent, lorsque nous modifions des documents, de mettre à jour leurs formes cryptographiques efficacement. Nous montrons que les systèmes actuels restreignent beaucoup trop les modifications possibles et introduisons de nouveaux algorithmes s’appuyant sur ces derniers, utilisés comme des boites noires, afin de rendre possible une large gamme de modifications aux documents tout en conservant une propriété de secret de l’opération effectuée.Notre intérêt porte ensuite sur les dictionnaires authentifiés, utilisés pour authentifier les réponses aux requêtes des utilisateurs sur un dictionnaire, en leur fournissant une preuve d’authenticité pour chaque réponse. Nous nous focalisons sur des systèmes basés sur des arbres de hachage et proposons une solution pour amoindrir leur principal inconvénient, celui de la taille des preuves. / The need for continuing innovation in terms of performances and resource savings impel us to optimize the design and the use of cryptographic mechanisms. This leads us to consider several aspects in this dissertation: parallel cryptographic algorithms, incremental cryptographic algorithms and authenticated dictionaries.In the context of parallel cryptography we are interested in hash functions. In particular, we show which tree structures to use to reach an optimal running time. For this running time, we show how to decrease the amount of involved processors. We also explore alternative (sub-optimal) tree structures which decrease the number of synchronizations in multithreaded implementations while balancing at best the load of the work among the threads.Incremental cryptographic schemes allow the efficient updating of cryptographic forms when we change some blocks of the corresponding documents. We show that the existing incremental schemes restrict too much the possible modification operations. We then introduce new algorithms which use these ones as black boxes to allow a broad range of modification operations, while preserving a privacy property about these operations.We then turn our attention to authenticated dictionaries which are used to authenticate answers to queries on a dictionary, by providing to users an authentication proof for each answer. We focus on authenticated dictionaries based on hash trees and we propose a solution to remedy their main shortcoming, the size of proofs provided to users.

Les circuits cryptographiques, parce qu'ils contiennent des informations confidentielles, font l'objet de manipulations frauduleuses, appelées communément attaques, de la part de personnes mal intentionnées. Plusieurs attaques ont été répertoriées et analysées. Parmi elles, les attaques DPA (Differential Power Analysis), DEMA (Differential Electromagnetic Analysis), DBA (Differential Behavior Analysis) et les attaques en probing forment la classe des attaques par corrélation et sont considérés comme les plus redoutables car elles permettent de retrouver, à moindre coût, les clefs de chiffrement des algorithmes cryptographiques. Les concepteurs de circuits sécurisés ont été donc amené à ajouter des parades, appelées contre-mesures, afin de protéger les circuits de ces attaques. Ces contremesures doivent impacter au minimum les performances et le coût du circuit. Dans cette thèse, nous nous intéressons dans un premier temps aux attaques par corrélation, le principe de ces attaques est décrit ainsi que les principales contre-mesures pour y parer. Un formalisme décrivant de manière unique ces attaques est aussi proposé. Dans un deuxième temps, nous étudions les outils d'évaluation sécuritaires qui permettent d'estimer la résistance des circuits intégrés face aux attaques par corrélation. Après un état de l'art sur les outils existants, nous décrivons notre outil basé sur une recherche de corrélations entre le modèle du concepteur et le modèle qui peut être prédit par un attaquant. L'analyse de corrélations permet de déterminer les bits les plus sensibles pour mener à bien une attaque. Cet outil est intégré dans le flot de conception permettant ainsi d'évaluer la résistance des algorithmes cryptographiques au niveau RTL (Register Transfer Level) et portes. / The cryptographic circuits, because they contain confidential information, are subject to fraudulent manipulations called attacks from malicious people. Several attacks have been identified and analyzed. Among them DPA (Differential Power Analysis), DEMA (Differential Electromagnetic Analysis), DBA (Differential Behaviour Analysis) and probing attacks form the class of correlation attacks and are considered as the most dangerous because they allow to retrieve, at lower cost, secret keys of cryptographic algorithms. Designers of secure circuits have thus added counter-measures to protect their circuits from these attacks. Counter-measures overhead got to have a minimum of impact on circuit’s cost and performances. In this thesis, we first focus on correlation attacks; the principle of these attacks is described as well as the main counter-measures to address them. A formalism describing these attacks is also proposed. Second, we study the safe evaluation tools to estimate the resistance of integrated circuits towards correlation attacks. After a state of the art on the existing tools, we describe our tool based on a search of correlations between the designer's model and the model which can be predicted by an attacker. The analysis of the correlations determines the most sensitive bits to complete an attack. This tool is integrated into the design flow to asses the strength of cryptographic algorithms at RTL (Register Transfer Level) and gate levels. An application of our flow on several models of the algorithm AES (Advanced Encryption Standard) with and without counter-measures is proposed. The obtained results have demonstrated the effectiveness of our technique.Les circuits cryptographiques, parce qu'ils contiennent des informations confidentielles, font l'objet de manipulations frauduleuses, appelées communément attaques, de la part de personnes mal intentionnées. Plusieurs attaques ont été répertoriées et analysées. Parmi elles, les attaques DPA (Differential Power Analysis), DEMA (Differential Electromagnetic Analysis), DBA (Differential Behavior Analysis) et les attaques en probing forment la classe des attaques par corrélation et sont considérés comme les plus redoutables car elles permettent de retrouver, à moindre coût, les clefs de chiffrement des algorithmes cryptographiques. Les concepteurs de circuits sécurisés ont été donc amené à ajouter des parades, appelées contre-mesures, afin de protéger les circuits de ces attaques. Ces contremesures doivent impacter au minimum les performances et le coût du circuit. Dans cette thèse, nous nous intéressons dans un premier temps aux attaques par corrélation, le principe de ces attaques est décrit ainsi que les principales contre-mesures pour y parer. Un formalisme décrivant de manière unique ces attaques est aussi proposé. Dans un deuxième temps, nous étudions les outils d'évaluation sécuritaires qui permettent d'estimer la résistance des circuits intégrés face aux attaques par corrélation. Après un état de l'art sur les outils existants, nous décrivons notre outil basé sur une recherche de corrélations entre le modèle du concepteur et le modèle qui peut être prédit par un attaquant. L'analyse de corrélations permet de déterminer les bits les plus sensibles pour mener à bien une attaque. Cet outil est intégré dans le flot de conception permettant ainsi d'évaluer la résistance des algorithmes cryptographiques au niveau RTL (Register Transfer Level) et portes.

La cryptographie reposant sur les réseaux Euclidiens est une branche récente de la cryptographie dans laquelle la sécurité des primitives repose sur la difficulté présumée de certains problèmes bien connus dans les réseaux Euclidiens. Le principe de ces preuves est de montrer que réussir une attaque contre une primitive est au moins aussi difficile que de résoudre un problème particulier, comme le problème Learning With Errors (LWE) ou le problème Small Integer Solution (SIS). En montrant que ces problèmes sont au moins aussi difficiles à résoudre qu'un problème difficile portant sur les réseaux, présumé insoluble en temps polynomial, on en conclu que les primitives construites sont sûres. Nous avons travaillé sur l'amélioration de la sécurité et des constructions de primitives cryptographiques. Nous avons étudié la difficulté des problèmes SIS et LWE et de leurs variantes structurées sur les anneaux d'entiers de corps cyclotomiques, et les modules libres sur ceux-ci. Nous avons montré d'une part qu'il existe une preuve de difficulté classique pour le problème LWE (la réduction existante de Regev en 2005 était quantique), d'autre part que les variantes sur les modules sont elles-aussi difficiles. Nous avons aussi proposé deux nouvelles variantes de signatures de groupe dont la sécurité repose sur SIS et LWE. L'une est la première reposant sur les réseaux et ayant une taille et une complexité poly-logarithmique en le nombre d'utilisateurs. La seconde construction permet de plus la révocation d'un membre du groupe. Enfin, nous avons amélioré la taille de certains paramètres dans le travail sur les applications multilinéaires cryptographiques de Garg, Gentry et Halevi. / Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013.

SSL/TLS, un protocole de sécurité datant de 1995, est devenu aujourd'hui une brique essentielle pour la sécurité des communications, depuis les sites de commerce en ligne ou les réseaux sociaux jusqu'aux réseaux privés virtuels (VPN), en passant par la protection des protocoles de messagerie électronique, et de nombreux autres protocoles. Ces dernières années, SSL/TLS a été l'objet de toutes les attentions, menant à la découverte de nombreuses failles de sécurité et à des améliorations du protocole. Dans cette thèse, nous commençons par explorer l'écosystème SSL/TLS sur Internet en énumérant les serveurs HTTPS sur l'espace IPv4; nous proposons pour cela des méthodologies de collecte et d'analyse permettant d'obtenir des résultats reproductibles et comparables entre différentes campagnes de mesure. Au-delà de ces observations, nous nous sommes intéressés en détail à deux aspects essentiels de la sécurité TLS: comment parer les attaques sur le Record Protocol, et comment implémenter des parsers sûrs et efficaces. Finalement, en se basant sur les nombreuses failles d'implémentation qui ont affecté presque toutes les piles TLS ces dernières années, nous tirons quelques enseignements concernant les difficultés liées à l'écriture d'une bibliothèque TLS de confiance / SSL/TLS, a 20-year old security protocol, has become a major component securing network communications, from HTTPS e-commerce and social network sites to Virtual Private Networks, from e-mail protocols to virtually every possible protocol. In the recent years, SSL/TLS has received a lot of attentions, leading to the discovery of many security vulnerabilities, and to protocol improvements. In this thesis, we first explore the SSL/TLS ecosystem at large using IPv4 HTTPS scans, while proposing collection and analysis methodologies to obtain reproducible and comparable results across different measurement campaigns. Beyond these observations, we focused on two key aspects of TLS security: how to mitigate Record Protocol attacks, and how to write safe and efficient parsers. Finally, building on the numerous implementation flaws in almost all TLS stacks in the last years, we propose some thoughts about the challenges in writing a secure TLS library

Les codes localement corrigibles ont été introduits dans le but d'extraire une partie de l'information contenue dans un mot de code bruité, en effectuant un nombre limité de requêtes à ses symboles, ce nombre étant appelé la localité du code. Ces dernières années ont vu la construction de trois familles de tels codes, dont la localité est sous-linéaire en la taille du message, et le rendement est arbitrairement grand. Ce régime de paramètres est particulièrement intéressant pour des considérations pratiques.Dans cette thèse, nous donnons une rapide revue de littérature des codes localement corrigibles, avant d'en proposer un modèle combinatoire générique, à base de block designs. Nous définissons et étudions ensuite un analogue, dans le cas projectif, des relèvements affine de codes introduits par Guo, Kopparty et Sudan. Nous établissons par ailleurs plusieurs liens entre ces deux familles, pour finir par une analyse précise de la structure monomiale de ces codes dans le cas du relèvement plan.Une deuxième partie de la thèse se focalise sur l'application de ces codes à deux protocoles cryptographiques. D'abord, nous proposons un protocole de récupération confidentielle d'information (private information retrieval, PIR) à partir de codes basés sur des designs transversaux, dont la taille des blocs s'apparente à la localité d'un code localement corrigible. Les protocoles ainsi construits ont l'avantage de n'exiger aucun calcul pour les serveurs, et de présenter une faible redondance de stockage ainsi qu'une complexité de communication modérée. Ensuite, nous donnons une construction générique de preuve de récupérabilité (proof of retrievability, PoR) à base de codes admettant une riche structure d'équations de parité à petit poids. Nous en donnons finalement une analyse de sécurité fine ainsi que plusieurs instanciations fondées sur des codes à propriétés locales. / Locally correctable codes (LCCs) were introduced in order to retrieve pieces of information from a noisy codeword, by using a limited number of queries to its symbols, this number being called the locality. Three main families of LCCs reaching sublinear locality and arbitrarily high rate have been built so far. This specific range of parameters is of particular interest concerning practical applications of LCCs.In this thesis, after giving a state of the art for LCCs, we study how they can be built using block designs. We then give an analogue over projective spaces of the family of affine lifted codes introduced by Guo, Kopparty and Sudan. We exhibit several links between both families, and we give a precise analysis of the monomial structure of the code in the case of the lifting of order 2.The second part of the thesis focuses on the application of these codes to two cryptographic protocols. We first build a new private informatin retrieval (PIR) protocol from codes based on transversal designs, whose block size defines the locality of the code. Our construction features no computation on the server side, low storage overhead and moderate communication complexity. Then, we propose a new generic construction of proof-of-retrievability (PoR) that uses codes equipped with an elaborate structure of low-weight parity-check equations. We give a rigorous analysis of the security of our scheme, and we finally propose practical instantiations based on codes with locality.

L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques.

Cette thèse traite de la vérification des protocoles cryptographiques. Son sujet est la modélisation symbolique de protocoles avec pour objectif la preuve de propriétés de sécurité. La thèse comprend deux parties: La première partie définit quatre modèles symboliques différant par les moyens syntaxiques que les concepteur peuvent utiliser pour représenter les primitives cryptographiques. On a observé que les vérificateurs utilisent des astuces de codage dans des modèles peu riches pour représenter les primitives manquantes. Nous montrons que ces codages sont corrects dans le sens où un protocole qui satisfait une propriété dans un modèle peu expressif la satisfait aussi dans un modèle plus riche. Nous terminons cette partie par la description d'un module que nous avons implémenté pour la plate-forme de vérification AVISPA. Ce module est basé sur des résultats permettant le transfert des propriétés d'un protocole, prouvées dans un modèle symbolique, vers un modèle calculatoire. Dans la deuxième partie de cette thèse, nous développons un modèle symbolique pour représenter des protocoles récursifs. Ces protocoles sont difficiles à analyser et peu de résultats de décidabilité existent. Nous montrons que notre modèle symbolique permet de retrouver une attaque connue contre une propriété d'un protocole de commerce électronique. Nous proposons ensuite une modification de ce protocole et montrons que le protocole modifié satisfait cette propriété.