Private Communication

Keeping communication private has become increasingly important in an era of mass surveillance and state-sponsored attacks. While hiding the contents of a conversation has well-known solutions, hiding the associated metadata (participants, duration, etc.) remains a challenge, especially if one cannot trust ISPs or proxy servers. This research project investigates systems that can provably hide all content and metadata while withstanding global adversaries.

Our results
We have built a communication system called Pung that provably hides all content and metadata while withstanding global adversaries. Pung is a key-value store where clients deposit and retrieve messages without anyone—including Pung’s servers—learning of the existence of a conversation. Pung is based on private information retrieval, which we make more practical for our setting with new techniques. These include a private multi-retrieval scheme, an application of the power of two choices, and batch codes. These extensions allow Pung to handle 1000× more users than prior systems with a similar threat model. In particular, We find that a 4-server deployment of Pung sup ports 135K messages/minute with 32K active users: 100,000× more messages and 1000× more users than any prior system that withstands a similar adversary. When we extend this comparison to systems under weaker threat models we find that Pung is promising but is not yet a replacement: Pung handles 85× fewer users.

To support tens of thousands of users at modest costs, Pung addresses two challenges. The first is architectural: devising a way for users to send and receive messages without a trusted proxy. Our proposal is simple, and consists of combining untrusted servers and powerful cryptography through a synthesis of known ideas. The second, and more salient aspect of Pung is reducing the costs of its cryptographic machinery. Our contributions here include algorithms that amortize expensive operations when users send and receive multiple messages.

Our publication below provides additional details.