L'explosion de la bulle internet au début des années 2000 a eu d'énormes impacts sociaux et économiques. Aujourd'hui, le nombre d'internautes approche les quatre milliards et internet s'est ancré dans notre vie quotidienne. De plus en plus d'informations circulent dans ce réseau et depuis les révélations d'Edward Snowden, le public a pris conscience du besoin de protéger sa vie privée. Ce mémoire présente dans un premier temps les concepts généraux de l'anonymat et de la protection de la vie privée sur internet. Ensuite, les réseaux anonymes les plus populaires y sont étudiés : JAP, Mixmaster, TOR et I2P. Nous verrons que la meilleure protection de ces réseaux est leur taille. [1] a élaboré un système de paiement pour rémunérer les relais de TOR dans le but d'encourager les internautes à participer sur le réseau anonyme. Nous verrons comment adapter ce système au réseau anonyme I2P. / Since the beginning of this century, the explosion of the internet has had an important social and economic impact. Today, the number of internet users has approached four billion and it has become a part of our daily lives. More and more information circulates on the internet and since Edward Snowden's global surveillance disclosure in 2013, the public is now aware about the necessity to protect their private lives. In a rst time, this thesis introduces anonymity and privacy general concepts'. Then, the following popular anonymous networks are studied: JAP, Mixmaster, TOR and I2P. We will see that the best protection for these network is their size. [1] has elaborates a payment system for remunerates the TOR relays in order to encourage Internet users to participate in the anonymous network. We will see how adapt this system on the I2P anonymous network.

Dans cette thèse nous considérons une plate-forme de filtrage collaboratif distribué dans laquelle chaque pair héberge ses informations personnelles, comme les URL qu'il a aimé, les pages d'information qui ont attiré son intérêt ou les vidéos qu'il a regardé, sur sa propre machine. Ensuite, sans reposer sur un tiers fiable, le pair s'engage dans un protocole distribué combinant ses données personnelles avec celles d'autres pairs afin d'exécuter un filtrage collaboratif. L'objectif principal est d'être capable de recevoir des recommandations personnalisées ou d'autres services comme un moteur de recherche distribué et personnalisé. Les protocoles de filtrage collaboratif basés sur les utilisateurs, qui demandent de calculer des similarités entre les utilisateurs, ont été appliqués aux systèmes distribués. Comme le calcul de similarité entre les utilisateurs nécessite d'utiliser leurs profils privés personnels, cela lève de sérieuses inquiétudes quant à la vie privée. Dans cette thèse nous adressons le problème du calcul de similarités entre les pairs sur une plate forme collaborative. Notre travail fournit une primitive préservant la vie privée pour le calcul de similarité qui peut rendre les protocoles collaboratifs respectueux de la vie privée. Nous adressons le challenge unique qui est d'appliquer des techniques de préservation de la vie privée pour le calcul de similarité aux systèmes dynamiques à large échelle. En particulier, nous introduisons un protocole cryptographique bipartite qui assure la differential privacy, une notion forte de préservation de la vie privée. De plus, nous résolvons le problème du budget de vie privée qui empêcherait les pairs de calculer leur similarité plus d'un nombre fixe de fois en introduisant la notion de canaux anonymes bidirectionnels. Nous développons aussi une variante hétérogène de la differential privacy qui peut apporter différent niveaux de confidentialité pour différent utilisateurs, et même différent niveaux de confidentialité pour différents items du profile d'un même utilisateur, prenant ainsi en compte différentes attentes en terme de préservation de la vie privée. De plus, nous proposons un protocole non interactif qui est très efficace pour publier une représentation compacte et préservant la vie privée des profiles des utilisateurs qui peut être utilisée pour estimer la similarité. Enfin, nous étudions le problème de choisir un paramètre de vie privée à la fois théoriquement et empiriquement en créant plusieurs attaques par inférence qui démontrent pour quelles valeurs du paramètre de vie privée le niveau de vie privée fournis est acceptable. / In this thesis, we consider a distributed collaborative platform in which each peer hosts his private information, such as the URLs he liked or the news articles that grabbed his interest or videos he watched, on his own machine. Then, without relying on a trusted third party, the peer engages in a distributed protocol, combining his private data with other peers' private data to perform collaborative filtering. The main objective is to be able to receive personalized recommendations or other services such as a personalized distributed search engine. User-based collaborative filtering protocols, which depend on computing user-to-user similarity, have been applied to distributed systems. As computing the similarity between users requires the use of their private profiles, this raises serious privacy concerns. In this thesis, we address the problem of privately computing similarities between peers in collaborative platforms. Our work provides a private primitive for similarity computation that can make collaborative protocols privacy-friendly. We address the unique challenges associated with applying privacy-preserving techniques for similarity computation to dynamic large scale systems. In particular, we introduce a two-party cryptographic protocol that ensures differential privacy, a strong notion of privacy. Moreover, we solve the privacy budget issue that would prevent peers from computing their similarities more than a fixed number of times by introducing the notion of bidirectional anonymous channel. We also develop a heterogeneous variant of differential privacy that can provide different level of privacy to different users, and even different level of privacy to different items within a single user's profile, thus taking into account different privacy expectations. Moreover, we propose a non-interactive protocol that is very efficient for releasing a small and private representation of peers' profiles that can be used to estimate similarity. Finally, we study the problem of choosing an appropriate privacy parameter both theoretically and empirically by creating several inference attacks that demonstrate for which values of the privacy parameter the privacy level provided is acceptable.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA.