Governments increasingly store and process huge quantities of data to combat crime, fraud, and terrorism with the aim of increasing security. However, the price is a loss of privacy. Fortunately, in some cases, it is possible to build cryptographic systems that achieve the security goals and at the same time protect the privacy of “the innocent”. One such system is distributed encryption.

Distributed encryption allows observers to record parties that behave suspiciously by creating ciphertext shares of their identities. These shares by themselves give no information about the party to whom they refer. They can only be combined to recover the identity of the recorded party when sufficient shares are available. This system can, for example, be used to find high-way truck-stop robbers without affecting the privacy of regular innocent road users.

In this talk, I will introduce the problem of uniting security and privacy, and describe our 2014 distributed encryption scheme, including a batched variant that is faster for small plaintext domains – like license plates. I will also highlight some recent work that makes recovering encrypted identities several orders of magnitudes faster.