Vuvuzela: A Scalable Private Messaging System
This is part of a week(-ish) blog series where I deep-dive on a cool technology. I am an investor at Dell Technologies Capital in Silicon Valley, and occasionally reminisce about my previous life in academia. Follow me on Twitter and LinkedIn.
In this post, I will discuss some cool work done by a good friend and former labmate David Lazar. For context, during our PhD, David was always the most privacy conscious person in our group, thinking that we were leaking too much data to big tech companies like Google and Facebook. At the time, I, along with many others, thought that David was being a bit too conservative, but with the recent data leaks at place like Equifax, Google+, and Facebook, David was really the right amount of cautious.
This post is about one of his projects on anonymous communication. With the number of people trying to hide their identity online through tools like Tor and DuckDuckGo, I thought this would be an interesting and relevant topic.
Say Alice wants to communicate with Bob, her oncologist, and hide this communication. Of course, she can encrypt her messages to Bob. However, this isn’t sufficient because both parties still leak metadata through other channels. For example, Alice might communicate with the White House, NSA, and NYT, and Bob might talk to insurance and pharma companies. This metadata can reveal Alice’s and Bob’s identities. Here are some relevant but scary quotes:
Metadata absolutely tells you everything about somebody’s life — Stewart Baker, former General Counsel of the NSA
We kill people based on metadata — Michael Hayden, former Director of the NSA
To solve this problem, David built Vuvuzela, a messaging system that protects the privacy of message contents and message metadata. Users communicating through Vuvuzela do not reveal who they are talking to, even in the presence of powerful nation-state adversaries.
Of course, one can also use Tor, but past research shows that Tor isn’t that secure despite being very scalable. The goal of Vuvuzela is to be both secure and scalable.
Here is an overview of Vuvuzela:
To achieve scalable privacy, they use the following techniques:
- Use efficient cryptography to encrypt as much metadata as possible.
- Add noise to metadata that we can’t “encrypt.”
- Use differential privacy to reason about how much privacy the noise gives us.
Below is a diagram of the Vuvuzela system. Alice, Bob, and Charlie are users of this system.
In Vuvuzela, users don’t communicate directly. Instead, they leave messages in “dead drops,” shown by the mailboxes on the right, intended for other users to pick up. The middle computer/servers represent a mix network that hides the origins of the messages, i.e. which user put or got a message.
However, we aren’t fully done yet. There is still some information we need to hide. The problem is that the number of items in the dead drop reveals access patterns. To solve this, Vuvuzela adds fake exchanges in the network, i.e. fake/dummy messages. To determine the amount of fake exchanges to add, they use this technique called differential privacy.
I won’t go into detail about differential privacy, but this is a good summary by Matt Green. Interesting fact is that Apple uses differential privacy to hide individual users when they collect analytics from phones and devices.
Vuvuzela uses differential privacy to determine the number of fake exchanges that need to be done on the network. The goal is to make it very difficult to guess whether a certain user has talked with another user.
Now, I’ll provide some basic performance results, but for more details, I refer you to David’s paper, where you can also learn more technical details around Vuvuzela. The system linearly scales with the number of users. It has around 37 seconds of end-to-end messages latency, and it can handle 60,000 messages per second.
David has done an interesting amount of work around anonymous communication, and I encourage that you check it out if you’re interested. As technology continues to degrade our privacy in many ways, tools to combat that trend, like anonymous communication, are definitely a necessity.
If you have questions, comments, future topic suggestions, or just want to say hi, please send me a note at frank.y.wang@dell.com.