Restructuring the NSA Metadata Program

During the Summer of 2013, it was revealed through the documents leaked by Edward Snowden that the NSA was collecting the metadata of every US-to-foreign, foreign-to-US and US-to-US call from the largest US telephone providers. This led to public outcry and to President Obama calling for the restructuring of this program. The options initially considered included keeping the data at the providers, entrusting the data to a private entity, entrusting the data to a non-NSA government agency or ending the program all-together. In this work, we show how cryptography can be used to design a privacy-preserving alternative to the NSA metadata program. We present a protocol based on structured encryption, in particular on graph encryption, and secure function evaluation that provides the following guarantees: (1) providers learn no information about NSA queries; (2) NSA queries can only be executed if validated by a given certification process; (3) the NSA learns nothing about the data beyond what can be inferred from the query results. In addition, these properties are achieved whether the data is stored at the providers, the NSA or on a third-party cloud.