Random Privacy

Tim May tcmay at got.net
Sat Sep 21 10:44:56 PDT 2002


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





More information about the cypherpunks-legacy mailing list