Where's Wally? How to Privately Discover your Friends on the Internet

Abstract

Internet friends who would like to connect with each other (e.g., VoIP, chat) use point-to-point communication applications such as Skype or WhatsApp. Apart from providing the necessary communication channel, these applications also facilitate contact discovery, where users upload their address-book and learn the network address of their friends. Although handy, this discovery process comes with a significant privacy cost: users are forced to reveal to the service provider every person they are socially connected with, even if they do not ever communicate with them through the app. In this paper, we show that it is possible to implement a scalable User Discovery service, without requiring any centralized entity that users have to blindly trust. Specifically, we distribute the maintenance of the users» contact information, and allow their friends to query for it, just as they normally query the network for machine services. We implement our approach in PROUD: a distributed privacy-preserving User Discovery service, which capitalizes on DNS. The prevalence of DNS makes PROUD immediately applicable, able to scale to millions of users. Preliminary evaluation shows that PROUD provides competitive performance for all practical purposes, imposing an overhead of less than 0.3 sec per operation.