The Living Thing / Notebooks : Differential privacy

Another thing I won’t have time to blog or fully understand, but will collect a few explanatory blog posts about for emergency cribbing.

Learning Statistics with Privacy, aided by the Flip of a Coin:

Let’s say you wanted to count how many of your online friends were dogs, while respecting the maxim that, on the Internet, nobody should know you’re a dog. To do this, you could ask each friend to answer the question “Are you a dog?” in the following way. Each friend should flip a coin in secret, and answer the question truthfully if the coin came up heads; but, if the coin came up tails, that friend should always say “Yes” regardless. Then you could get a good estimate of the true count from the greater-than-half fraction of your friends that answered “Yes”. However, you still wouldn’t know which of your friends was a dog: each answer “Yes” would most likely be due to that friend’s coin flip coming up tails.


Dwork, C. (2006) Differential Privacy. (Vol. 4052).
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., & Roth, A. (2015) The reusable holdout: Preserving validity in adaptive data analysis. Science, 349(6248), 636–638. DOI.
Fanti, G., Pihur, V., & Erlingsson, Ú. (2015) Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries. arXiv:1503.01214 [Cs].