Vuvuzela: scalable private messaging resistant to traffic analysis

By Jelle van den Hooff, David Lazar, Matei A. Zaharia, Nickolai Zeldovich. 2015

333 citations recorded by the source corpus.

Private messaging over the Internet has proven challenging to implement, because even if message data is encrypted, it is difficult to hide metadata about who is communicating in the face of traffic analysis. Systems that offer strong privacy guarantees, such as Dissent [36], scale to only several thousand clients, because they use techniques with superlinear cost in the number of clients (e.g., each client broadcasts their message to all other clients). On the other hand, scalable systems, such as Tor, do not protect against traffic analysis, making them ineffective in an era of pervasive network monitoring. Vuvuzela is a new scalable messaging system that offers strong privacy guarantees, hiding both message data and metadata. Vuvuzela is secure against adversaries that observe and tamper with all network traffic, and that control all nodes except for one server. Vuvuzela's key insight is to minimize the number of variables observable by an attacker, and to use differential privacy techniques to add noise to all observable variables in a way that provably hides information about which users are communicating. Vuvuzela has a linear cost in the number of clients, and experiments show that it can achieve a throughput of 68,000 messages per second for 1 million users with a 37-second end-to-end latency on commodity servers.

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

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.”
Karaoke: Distributed Private Messaging Immune to Passive Traffic Analysis (2018, background): “Karaoke achieves differential privacy for metadataprivate messaging, much like Vuvuzela [26], Alpenhorn [15], and Stadium [25].”
This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Unobservable Communication over Fully Untrusted Infrastructure Unobservable Communication over Fully Untrusted Infrastructure (positive): “Pung's " mailbox " architecture is borrowed from prior systems [25] [40] [75] [79] [119] [130].”
Contact Tracing Mobile Apps for COVID-19: Privacy Considerations and Related Trade-offs (2020, background): “Though many techniques [36; 27; 29] have been proposed to address this challenge, further discussion among the stakeholders is needed to determine the suitable trade-off between the level of latency that can be tolerated and the level of privacy guarantees desired by the users.”
Scalable Bias-Resistant Distributed Randomness (2017, background): “Anytrustbased systems, such as Herbivore [32], Dissent [60], and Vuvuzela [59], as well as sharded blockchains [23], use biasresistant public randomness for scalability by sharding participants into smaller groups.”
COVI White Paper (2020, background): “NHS Bluetooth protocol [51] + mix-nets for message exchange [67]”
PROCHLO: Strong Privacy for Analytics in the Crowd (2017, background): “Those cryptographic mechanisms—detailed in the remainder of this paper—differ from the cryptography typically used to protect privacy for aggregated analysis (or for different purposes, like Vuvuzela or Riposte private messaging [19, 72]).”
Spying on the Smart Home: Privacy Attacks and Defenses on Encrypted IoT Traffic (2017, background): “Independent link padding algorithms, which force traffic to match a predefined schedule or distribution, are well-studied [16, 40].”
Distributed Measurement with Private Set-Union Cardinality (2017, background): “Mixnets and shuffling schemes have found a variety of applications, particularly anonymous communication [8, 11, 39, 49] and electronic voting [4, 29, 40].”
Towards Probabilistic Verification of Machine Unlearning (2020, background): “This can be achieved using of-the-shelf anonymous communication schemes like [37, 38].”
SGX-LKL: Securing the Host OS Interface for Trusted Execution (2019, background): “To hide access patterns in network traffic, noise in the form of dummy network packets can be added to generate a constant stream of fixed size packets sent between participating trusted nodes [96, 99].”
Practical and Robust Privacy Amplification with Multi-Party Differential Privacy (2019, background): “, e-voting [5], private messaging [44]), to provide a better trust model.”
Stadium: A Distributed Metadata-Private Messaging System (2017, background): “• The design for a horizontally scaling metadata-private • An implementation and experimental evaluation of”