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.

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.

Cette thèse se concentre sur les problèmes liés à l’authentification dans la technologie RFID. Cette technologie est l’une des technologies les plus prometteuses dans le domaine de l’informatique ubiquitaire, elle est souvent désignée comme la prochaine révolution après Internet. Cependant, à cause des ressources très limitées en termes de calcul, mémoire et énergie sur les étiquettes RFID, les algorithmes classiques de sécurité ne peuvent pas être implémentés sur les étiquettes à bas coût rendant ainsi la sécurité et la vie privée un important sujet de recherche aujourd’hui. Dans un premier temps, nous étudions le passage à l’échelle dans les systèmes RFID à bas coût en développant un module pour ns-3 qui simule le standard EPC Class 1 Generation 2 pour établir un cadre stricte pour l’identification sécurisée des RFID à bas coût, ce qui nous conduit à l’utilisation de la cryptographie à clés publiques. Ensuite, nous proposons un protocole d’authentification basé sur une adaptation que nous avons introduit sur le célèbre cryptosystème NTRU. Ce protocole est spécialement conçu pour les RFID à bas coût comme les étiquettes n’implémentent que des opérations simples (xor, décalages, addition) et il garantit le passage à l’échelle. Enfin, nous considérons l’identification à divulgation nulle de connaissance, ce type d’approches est très utile dans de nombreuses applications RFID. Nous proposons deux protocoles à divulgation nulle de connaissance basés sur cryptoGPS et cryptoGPS randomisé. Ces approches consistent à stocker sur le serveur des coupons pré-calculés, ainsi la sécurité et la vie privée sont mieux supportées que dans les autres approches de ce type / This thesis focuses on issues related to authentication in low-cost radio frequency identification technology, more commonly referred to as RFID. This technology it is often referred to as the next technological revolution after the Internet. However, due to the very limited resources in terms of computation, memory and energy on RFID tags, conventional security algorithms cannot be implemented on low-cost RFID tags making security and privacy an important research subject today. First of all, we investigate the scalability in low-cost RFID systems by developing a ns-3 module to simulate the universal low-cost RFID standard EPC Class-1 Generation-2 in order to establish a strict framework for secure identification in low-cost RFID systems. We show that, the symmetrical key cryptography is excluded from being used in any scalable low-cost RFID standard. Then, we propose a scalable authentification protocol based on our adaptation of the famous public key cryptosystem NTRU. This protocol is specially designed for low-cost RFID systems, it can be efficiently implemented into low-cost tags. Finally, we consider the zero-knowledge identification i.e. when the no secret sharing between the tag and the reader is needed. Such identification approaches are very helpful in many RFID applications when the tag changes constantly the field of administration. We propose two lightweight zero-knowledge identification approaches based on GPS and randomized GPS schemes. The proposed approaches consist in storing in the back-end precomputed values in the form of coupons. So, the GPS-based variant can be private and the number of coupons can be much higher than in other approaches thus leading to higher resistance to denial of service attacks for cheaper tags

Les smooth (ou universal) projective hash functions ont été introduites par Cramer et Shoup, à Eurocrypt'02, comme un outil pour construire des schémas de chiffrement efficaces et sûrs contre les attaques à chiffrés choisis. Depuis, elles ont trouvé de nombreuses applications, notamment pour la construction de schémas d'authentification par mot de passe, d'oblivious transfer, de signatures en blanc, et de preuves à divulgation nulle de connaissance. Elles peuvent êtres vues comme des preuves implicites d'appartenance à certains langages. Un problème important est de caractériser pour quels langages de telles fonctions existent.Dans cette thèse, nous avançons dans la résolution de ce problème en proposant la notion de diverse modules. Un diverse module est une représentation d'un langage, comme un sous-module d'un module plus grand, un module étant un espace vectoriel sur un anneau. À n'importe quel diverse module est associée une smooth projective hash function pour le même langage. Par ailleurs, presque toutes les smooth projective hash functions actuelles sont construites de cette manière.Mais les diverse modules sont aussi intéressants en eux-mêmes. Grâce à leur structure algébrique, nous montrons qu'ils peuvent facilement être combinés pour permettre de nouvelles applications, comme les preuves implicites à divulgation nulle de connaissance (une alternative légère aux preuves non-interactives à divulgation nulle de connaissance), ainsi que des preuves non-interactives à divulgation nulle de connaissance et one-time simulation-sound très efficaces pour les langages linéaires sur les groupes cycliques. / Smooth (or universal) projective hash functions were first introduced by Cramer and Shoup, at Eurocrypt'02, as a tool to construct efficient encryption schemes, indistinguishable under chosen-ciphertext attacks. Since then, they have found many other applications, including password-authenticated key exchange, oblivious transfer, blind signatures, and zero-knowledge arguments. They can be seen as implicit proofs of membership for certain languages. An important question is to characterize which languages they can handle.In this thesis, we make a step forward towards this goal, by introducing diverse modules. A diverse module is a representation of a language, as a submodule of a larger module, where a module is essentially a vector space over a ring. Any diverse module directly yields a smooth projective hash function for the corresponding language, and almost all the known smooth projective hash functions are constructed this way.Diverse modules are also valuable in their own right. Thanks to their algebraic structural properties, we show that they can be easily combined to provide new applications related to zero-knowledge notions, such as implicit zero-knowledge arguments (a lightweight alternative to non-interactive zero-knowledge arguments), and very efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups.

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.