Differential privacy guarantees that a given database query protects individuals’ information even when the adversary possesses perfect information about everyone else in the database. This guarantee is convenient, but we believe stronger than is necessary in many circumstances. We introduce a new framework, coupled-worlds privacy, that generalizes differential privacy. This framework allows explicit bounds to be placed on how much the adversary knows about the database, and this uncertainty can be used to reduce or eliminate the noise needed to make a given query private.In this talk I will motivate the definition, which compares the information an adversary could gain in the real world to what could be gained from a “scrubbed” version of the database in which an individual’s information has been removed. I will also discuss various properties of the definition and compare it to other definitions that were motivated in similar ways. Finally, I will discuss several mechanisms that we have proven to be private under this definition.

Joint work with Raef Bassily, Jonathan Katz, and Adam Smith.