Unobservable communication over untrusted infrastructure

Abstract

In the past decade there has been a significant increase in the collection of personal information and communication metadata (with whom users communicate, when, how often) by governments, Internet providers, companies, and universities. While there are many ongoing efforts to secure users’ communications, namely end-to-end encryption messaging apps and email services, safeguarding metadata remains elusive. This dissertation discusses the design, implementation, and evaluation of a system called Pung that makes progress on this front. Pung lets users exchange messages over the Internet without revealing any information in the process. Perhaps surprisingly, Pung achieves this strong privacy property even when all providers (ISPs, companies, servers, etc.) are arbitrarily malicious.

As part of realizing Pung, this dissertation introduces two orthogonal but

complementary techniques: SealPIR and probabilistic batch codes (PBCs). SealPIR is

a new private information retrieval (PIR) library that reduces the communication

costs of the most computationally efficient PIR protocol by over two orders of magnitude.

SealPIR can also be used in other contexts to instantiate private services (for

example, private variants of media streaming services). PBCs are a new data encoding

that amortizes the computational costs associated with PIR, and are significantly

more network-efficient than prior encodings. Thanks to these two techniques, our

small deployment of Pung can scale out to support hundreds of thousands of users.