A Cryptographic Airbag for Metadata: Protecting Business Records Against Unlimited Search and Seizure

Governments around the world require that electronic service providers, including telecoms, ISP's, and even online services like Twitter and Facebook, must provide law enforcement agencies with broad access to so-called "business records" including communications metadata. Metadata is data about data; it does not include the contents of the users' communications, but it does typically show who each user communicated with, and at what times, and for how long. Metadata is actually surprisingly powerful, especially in a time when more and more messages are being encrypted from end-to-end.

In this paper, we present a new approach for protecting communications metadata and other business records against unwarranted, bulk seizure. Our approach is designed from the start to be robust against a new class of political and legal attack. To achieve this, we borrow the recent notion of cryptographic crumple zones, i.e. encryption that can be broken, but only at a substantial monetary cost. We propose that a service provider who wishes to protect their users' privacy should encrypt each business record with its own unique, crumpled, symmetric key. Then, a law enforcement agency who compels disclosure of the records learns only ciphertext until they expend the necessary resources to recover keys for the records of interest. We show how this approach can be easily applied to protect metadata in the form of network flow records. We describe how a service provider might select the work factor of the crumpling algorithm to defend against political and legal attacks by allowing legitimate investigations, while still preventing use of the same metadata for mass surveillance.