On Saturday, September 21, 2002, at 09:29 AM, Tim May wrote:
On Saturday, September 21, 2002, at 02:16 AM, Blanc wrote:
Interesting little article from http://pass.maths.org.uk/issue21/news/random_privacy/index.html:
Excerpt: How old are you? How much do you earn?
Not a new idea. Ted Nelson (IIRC) wrote about using coin flips to randomize AIDS poll questions. ("Have you engaged in unprotected sex?" Flip a coin and XOR it with your actual answer.) I remember talking to Eric Hughes, Phil Salin, and others around 1990-91 about this.
(BTW, as you probably know or can imagine, there have been crypto methods proposed for safeguarding certain kinds of data collection, e.g., schemes using "random coin flip protocols" for answering questions like "Are you homosexual?" (supposedly "useful" for public health planners trying to deal with HIV/AIDS issues. The idea is that the pollee XORs his answer with a random bit. His answer then doesn't _implicate_ him, but overall statistics can still be deduced from a large enough sample.lawmakers will try to take us down the first path. "
Cordian correctly points out that merely XORing with a random bit gives the same statistics as the random bit(s). Now that I think about it, I recollect the proposal was something along these lines: Alice is confronted with a question with a yes or no answer. She flips a coin. If the outcome is "H," she answers the question honestly. If the outcome is "T," she then flips another coin and gives that outcome as her answer. Half the population of pollees is ostensibly answering honestly, the other half is randomizing. No particular person can be linked to an answer. More sophisticated versions, as I recall, had more complicated series of coin tosses (to reduce "noise"). --Tim May