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].