Stadium: A Distributed Metadata-Private Messaging System

By Nirvan Tyagi, Yossi Gilad, Matei A. Zaharia, Nickolai Zeldovich. 2017

164 citations recorded by the source corpus.

Private communication over the Internet remains 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 anonymity systems, such as Tor, are susceptible to traffic analysis attacks that leak metadata. In contrast, the largest-scale systems with metadata privacy require passing all messages through a small number of providers, requiring a high operational cost for each provider and limiting their deployability in practice. This paper presents Stadium, a point-to-point messaging system that provides metadata and data privacy while scaling its work efficiently across hundreds of low-cost providers operated by different organizations. Much like Vuvuzela, the current largest-scale metadata-private system, Stadium achieves its provable guarantees through differential privacy and the addition of noisy cover traffic. The key challenge in Stadium is limiting the information revealed from the many observable traffic links of a highly distributed system, without requiring an overwhelming amount of noise. To solve this challenge, Stadium introduces techniques for distributed noise generation and differentially private routing as well as a verifiable parallel mixnet design where the servers collaboratively check that others follow the protocol. We show that Stadium can scale to support 4x more users than Vuvuzela using servers that cost an order of magnitude less to operate than Vuvuzela nodes.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Jonathan Ullman
2. Jian Tang
3. Philip S. Yu
4. Albert Cheu
5. Adam D. Smith
6. Daphne Ippolito
7. Meng Qu
8. Irina Rish

Citations in the corpus

• Distributed Differential Privacy via Shuffling (2018, background): “Another line of work [32, 29] shows how to use differential privacy in addition to mixnets to make communication patterns differentially private for the purposes of anonymous computation.”
• COVI White Paper (2020, background): “In order to enable the privacy guarantees for core functionality, we have to build a private messaging system [67, 68, 69] that ensures that no information about”
• Contact Tracing Mobile Apps for COVID-19: Privacy Considerations and Related Trade-offs (2020, background): “In particular, private messaging systems [27; 28; 29] and private set intersection (cardinality) [30; 31; 32; 33] protocols seem especially relevant.”
• Karaoke: Distributed Private Messaging Immune to Passive Traffic Analysis (2018, methodology): “Karaoke achieves differential privacy for metadataprivate messaging, much like Vuvuzela [26], Alpenhorn [15], and Stadium [25].”
• SGX-LKL: Securing the Host OS Interface for Trusted Execution (2019, background): “More recently, Private Information Retrieval (PIR) [5,22,25] and differential privacy techniques [9,96,99] add noise to hide the metadata.”