Anonymous communications networks help to solve the real and important problem of enabling users to communicate privately over the Internet. However, by doing so, they also introduce an entirely new problem: How can service providers on the Internet---such as websites, IRC networks and mail servers---allow anonymous access while protecting themselves against abuse by misbehaving anonymous users? Recent research efforts have focused on using anonymous blacklisting systems (also known as anonymous revocation systems) to solve this problem. As opposed to revocable anonymity systems, which enable some trusted third party to deanonymize users, anonymous blacklisting systems provide a way for users to authenticate anonymously with a service provider, while enabling the service provider to revoke access from individual misbehaving anonymous users without revealing their identities. The literature contains several anonymous blacklisting systems, many of which are impractical for real-world deployment. In 2006, however, Tsang et al. proposed Nymble, which solves the anonymous blacklisting problem very efficiently using trusted third parties. Nymble has inspired a number of subsequent anonymous blacklisting systems. Some of these use fundamentally different approaches to accomplish what Nymble does without using third parties at all; so far, these proposals have all suffered from serious performance and scalability problems. Other systems build on the Nymble framework to reduce Nymble's trust assumptions while maintaining its highly efficient design. The primary contribution of this thesis is a new anonymous blacklisting system built on the Nymble framework---a nimbler version of Nymble---called Nymbler. We propose several enhancements to the Nymble framework that facilitate the construction of a scheme that minimizes trust in third parties. We then propose a new set of security and privacy properties that anonymous blacklisting systems should possess to protect: 1) users' privacy against malicious service providers and third parties (including other malicious users), and 2) service providers against abuse by malicious users. We also propose a set of performance requirements that anonymous blacklisting systems should meet to maximize their potential for real-world adoption, and formally define some optional features in the anonymous blacklisting systems literature. We then present Nymbler, which improves on existing Nymble-like systems by reducing the level of trust placed in third parties, while simultaneously providing stronger privacy guarantees and some new functionality. It avoids dependence on trusted hardware and unreasonable assumptions about non-collusion between trusted third parties. We have implemented all key components of Nymbler, and our measurements indicate that the system is highly practical. Our system solves several open problems in the anonymous blacklisting systems literature, and makes use of some new cryptographic constructions that are likely to be of independent theoretical interest.

Anonymous communications networks help to solve the real and important problem of enabling users to communicate privately over the Internet. However, by doing so, they also introduce an entirely new problem: How can service providers on the Internet---such as websites, IRC networks and mail servers---allow anonymous access while protecting themselves against abuse by misbehaving anonymous users? Recent research efforts have focused on using anonymous blacklisting systems (also known as anonymous revocation systems) to solve this problem. As opposed to revocable anonymity systems, which enable some trusted third party to deanonymize users, anonymous blacklisting systems provide a way for users to authenticate anonymously with a service provider, while enabling the service provider to revoke access from individual misbehaving anonymous users without revealing their identities. The literature contains several anonymous blacklisting systems, many of which are impractical for real-world deployment. In 2006, however, Tsang et al. proposed Nymble, which solves the anonymous blacklisting problem very efficiently using trusted third parties. Nymble has inspired a number of subsequent anonymous blacklisting systems. Some of these use fundamentally different approaches to accomplish what Nymble does without using third parties at all; so far, these proposals have all suffered from serious performance and scalability problems. Other systems build on the Nymble framework to reduce Nymble's trust assumptions while maintaining its highly efficient design. The primary contribution of this thesis is a new anonymous blacklisting system built on the Nymble framework---a nimbler version of Nymble---called Nymbler. We propose several enhancements to the Nymble framework that facilitate the construction of a scheme that minimizes trust in third parties. We then propose a new set of security and privacy properties that anonymous blacklisting systems should possess to protect: 1) users' privacy against malicious service providers and third parties (including other malicious users), and 2) service providers against abuse by malicious users. We also propose a set of performance requirements that anonymous blacklisting systems should meet to maximize their potential for real-world adoption, and formally define some optional features in the anonymous blacklisting systems literature. We then present Nymbler, which improves on existing Nymble-like systems by reducing the level of trust placed in third parties, while simultaneously providing stronger privacy guarantees and some new functionality. It avoids dependence on trusted hardware and unreasonable assumptions about non-collusion between trusted third parties. We have implemented all key components of Nymbler, and our measurements indicate that the system is highly practical. Our system solves several open problems in the anonymous blacklisting systems literature, and makes use of some new cryptographic constructions that are likely to be of independent theoretical interest.

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.