Re:2020 Knuth Prize is awarded to Cynthia Dwork [pdf]
by papeda on Tuesday May 12, 2020 @06:16PM
(#23160712)
Not only is this differentially private, it's locally differentially private, which is an even stronger privacy definition. It's "local" because the user adds randomness themselves. Generic differential privacy is a weaker definition because it lets whoever's running the algorithm collect raw data and then add randomness somewhere in the computation pipeline to produce privatized outputs.
This kind of example also predates the definition of differential privacy by about 40 years [1], although the motivation is pretty much the same.
"A simple example, especially developed in the social sciences,[15] is to ask a person to answer the question "Do you own the attribute A?", according to the following procedure:
1. Toss a coin.
2. If heads, then toss the coin again (ignoring the outcome), and answer the question honestly.
3. If tails, then toss the coin again and answer "Yes" if heads, "No" if tails.
(The seemingly redundant extra toss in the first case is needed in situations where just the act of tossing a coin may be observed by others, even if the actual result stays hidden.) The confidentiality then arises from the refutability of the individual responses.
But, overall, these data with many responses are significant, since positive responses are given to a quarter by people who do not have the attribute A and three-quarters by people who actually possess it. Thus, if p is the true proportion of people with A, then we expect to obtain (1/4)(1-p) + (3/4)p = (1/4) + p/2 positive responses. Hence it is possible to estimate p.
In particular, if the attribute A is synonymous with illegal behavior, then answering "Yes" is not incriminating, insofar as the person has a probability of a "Yes" response, whatever it may be."