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 présente des résultats appartenant aux trois thèmes fondamentaux de la cryptographie à clé publique : l’intégrité, l’authentification et la confidentialité. Au sein de chaque thème nous concevons des nouvelles primitives et améliorons des primitives existantes. Le premier chapitre, dédié à l’intégrité, introduit une preuve non-interactive de génération appropriée de clés publiques RSA et un protocole de co-signature dans lequel tout irrespect de l’équité laisse automatiquement la partie lésée en possession d’une preuve de culpabilité incriminant la partie tricheuse. Le second chapitre, ayant pour sujet l’authentification, montre comme une mesure de temps permet de raccourcir les engagements dans des preuves à divulgation nulle et comment des biais, introduits à dessin dans le défi, permettent d’accroitre l’efficacité de protocoles. Ce chapitre généralise également le protocole de Fiat-Shamir à plusieurs prouveurs et décrit une fraude très sophistiquée de cartes-à-puce illustrant les dangers de protocoles d’authentification mal-conçus. Au troisième chapitre nous nous intéressons à la confidentialité. Nous y proposons un cryptosystème à clé publique où les hypothèses de complexité traditionnelles sont remplacées par un raffinement du concept de CAPTCHA et nous explorons l’application du chiffrement-pot-de-miel au langage naturel. Nos dernières contributions concernent le chiffrement basé sur l’identité (IBE). Nous montrerons comment ajouter des fonctions d’émission à l’IBE hiérarchique et comment l’IBE permet de réduire la fenêtre temporelle de risque lors de la diffusion de mises à jour logicielles. / This thesis presents new results in three fundamental areas of public-key cryptography: integrity, authentication and confidentiality. In each case we design new primitives or improve the features of existing ones. The first chapter, dealing with integrity, introduces a non-interactive proof for proper RSA public key generation and a contract co-signature protocol in which a breach in fairness provides the victim with transferable evidence against the cheater. The second chapter, focusing on authentication, shows how to use time measurements to shorten zeroknowledge commitments and how to exploit bias in zero-knowledge challenges to gain efficiency. This chapter also generalizes Fiat-Shamir into a one-to-many protocol and describes a very sophisticated smart card fraud illustrating what can happen when authentication protocols are wrongly designed. The third chapter is devoted to confidentiality. We propose public-key cryptosystems where traditional hardness assumptions are replaced by refinements of the CAPTCHA concept and explore the adaptation of honey encryption to natural language messages. Our final contributions focus on identity-based encryption (IBE) showing how to add broadcast features to hierarchical IBE and how to use IBE to reduce vulnerability exposure time of during software patch broadcast.

Dans cette thèse, nous étudions les preuves à divulgation nulle de connaissance, une primitive cryptographique permettant de prouver une assertion en ne révélant rien de plus que sa véracité, et leurs applications au calcul sécurisé. Nous introduisons tout d’abord un nouveau type de preuves à divulgation nulle, appelées arguments implicites à divulgation nulle, intermédiaire entre deux notions existantes, les preuves interactives et les preuves non interactives à divulgation nulle. Cette nouvelle notion permet d’obtenir les mêmes bénéfices en terme d’efficacité que les preuves non-interactives dans le contexte de la construction de protocoles de calcul sécurisé faiblement interactifs, mais peut être instanciée à partir des mêmes hypothèses cryptographiques que les preuves interactives, permettant d’obtenir de meilleures garanties d’efficacité et de sécurité. Dans un second temps, nous revisitons un système de preuves à divulgation nulle de connaissance qui est particulièrement utile dans le cadre de protocoles de calcul sécurisé manipulant des nombres entiers, et nous démontrons que son analyse de sécurité classique peut être améliorée pour faire reposer ce système de preuve sur une hypothèse plus standard et mieux connue. Enfin, nous introduisons une nouvelle méthode de construction de systèmes de preuves à divulgation nulle sur les entiers, qui représente une amélioration par rapport aux méthodes existantes, tout particulièrement dans un modèle de type client-serveur, où un client à faible puissance de calcul participe à un protocole de calcul sécurisé avec un serveur à forte puissance de calcul. / In this thesis, we study zero-knowledge proofs, a cryptographic primitive that allows to prove a statement while yielding nothing beyond its truth, and their applications to secure computation. Specifically, we first introduce a new type of zero-knowledge proofs, called implicit zero-knowledge arguments, that stands between two existing notions, interactive zeroknowledge proofs and non-interactive zero-knowledge proofs. Our new notion provides the same efficiency benefits than the latter when used to design roundefficient secure computation protocols, but it can be built from essentially the same cryptographic assumptions than the former, which allows to get improved efficiency and security guarantees. Second, we revisit a zero-knowledge proof system that is particularly useful for secure computation protocols manipulating integers, and show that the known security analysis can be improved to base the proof system on a more wellstudied assumption. Eventually, we introduce a new method to build zero-knowledge proof systems over the integers, which particularly improves over existing methods in a client-server model, where a weak client executes a secure computation protocol with a powerful server.

La sécurité de l’information repose sur la bonne interaction entre différents niveaux d’abstraction : les composants matériels, systèmes d’exploitation, algorithmes, et réseaux de communication. Cependant, protéger ces éléments a un coût ; ainsi de nombreux appareils sont laissés sans bonne couverture. Cette thèse s’intéresse à ces différents aspects, du point de vue de la sécurité et de la cryptographie. Nous décrivons ainsi de nouveaux algorithmes cryptographiques (tels que des raffinements du chiffrement de Naccache–Stern), de nouveaux protocoles (dont un algorithme d’identification distribuée à divulgation nulle de connaissance), des algorithmes améliorés (dont un nouveau code correcteur et un algorithme efficace de multiplication d’entiers),ainsi que plusieurs contributions à visée systémique relevant de la sécurité de l’information et à l’intrusion. En outre, plusieurs de ces contributions s’attachent à l’amélioration des performances des constructions existantes ou introduites dans cette thèse. / Information security relies on the correct interaction of several abstraction layers: hardware, operating systems, algorithms, and networks. However, protecting each component of the technological stack has a cost; for this reason, many devices are left unprotected or under-protected. This thesis addresses several of these aspects, from a security and cryptography viewpoint. To that effect we introduce new cryptographic algorithms (such as extensions of the Naccache–Stern encryption scheme), new protocols (including a distributed zero-knowledge identification protocol), improved algorithms (including a new error-correcting code, and an efficient integer multiplication algorithm), as well as several contributions relevant to information security and network intrusion. Furthermore, several of these contributions address the performance of existing and newly-introduced constructions.