Unobservable communication over untrusted infrastructure
MetadataShow full item record
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.