Paper 2016/943

Stadium: A Distributed Metadata-Private Messaging System

Nirvan Tyagi and Yossi Gilad and Matei Zaharia and Nickolai Zeldovich

Abstract

Private communication over the Internet continues to be a challenging problem. Even if messages are encrypted, it is hard to deliver them without revealing metadata about which pairs of users are communicating. Scalable systems, such as Tor, are susceptible to traffic analysis. In contrast, the largest-scale systems with metadata privacy require passing all messages through each server, capping their throughput and scalability. This paper presents Stadium, the first system to provide metadata and data privacy while being able to scale its work efficiently across many servers. Much like Vuvuzela, the current largest-scale system, Stadium is based on differential privacy. However, providing privacy in Stadium is more challenging because distributing users' traffic across servers creates opportunities for adversaries to observe it in fine granularity. To solve this challenge, Stadium uses a collaborative noise generation approach combined with a novel verifiable parallel mixnet design where servers collaboratively check that others follow the protocol. We show that Stadium can scale to use hundreds of servers, support over an order of magnitude more users than Vuvuzela, and cut the costs of operating each server.