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.