[FoRK] Crypto protocol for only good news?

mattj at newsblip.com < mattj at newsblip.com > on > Thu Aug 17 15:04:37 PDT 2006

Reza had some helpful comments offline which raised the useful idea of  
adding another actor or step.  Thanks!

> Reza wrote:
>
> In other words, what you've outlined is a system that has three black-boxes:
> parents, child, and the sonographer... If you introduce a forth, say a little
> bird flying around counting quantum spins... and say that:
>
> GenderOfBabyToBeToldToTheParents = RealGender [OPERATOR] Randomizer
>
> Where Randomizer is the news that the bird tells the sonographer at the time
> and under the terms of its own choosing.

So here's my current thinking...

First, to sidestep the geopolitical issues of gender selection, I'll  
use a new example: you've taped the big game, and you don't want your  
friend to tell you who won before you've had a chance to watch it...  
unless your team won, in which case you're glad to hear about it.  I'm  
going to temporarily call this the Fair-Weather Bit problem, because  
you only want to hear the bit value in one case; I'm hoping someone  
can clue me in to any existing terminology.  (The approach below has a  
Monty Hall Problem flavor, in a sense.)

You cannot have a 100% chance of learning they won without setting up  
a 100% chance of learning that they lost. So, this becomes a question  
of how risk averse you are in this situation.  If you mostly want to  
know about a win, we can structure things to give you a good chance of  
hearing that news. If you mostly want to avoid hearing about a loss,  
we can arrange that, too.

But to start, let's just get a basic answer.  Here's my protocol:

1. Friend watches the game live.
    If your team wins, he writes "Win" on a piece of paper.
    If your team loses, he writes "Null" (no answer) on a piece of paper.

2. Friend seals the paper inside an envelope, and hands it to a  
trusted third party (say, the bartender at your local pub). Your  
friend does *not* tell the bartender what the (single bit) message is  
about, and the bartender does not know about the big game. (I know,  
"you call that a bartender?", but let's assume it.)

3. You show up, and per the protocol, trusted bartender flips a coin  
out of your view.  Then the bartender opens the envelope (also out of  
view).
    If it's heads, the bartender reads you the message your friend wrote.
    If it's tails, the bartender says "Null", pretending he's reading  
the message.

Assuming your team has a 50-50 chance of winning, we expect to hear  
"Win" 25% of the time, and "Null" 75% of the time.  But we needn't be  
too sad if we hear "Null", because 2/3 of the time the "Null" will be  
a result of the bartender's coin toss.  Hearing "Null" means there's  
still a 1/3 chance they really won.

We do ask the bartender to be deceptive here (pretending all "Nulls"  
are equal). However, he can't have a motive to tell you good or bad  
info, because unlike your friend he has no idea what this particular  
message means.

Now, if you're not so risk averse, and you want a greater chance of  
hearing about a win, you replace the coin toss with some random number  
generator. Have the bartender read you the friend's message 90% of the  
time, and tell you "Null" for the other 10%.  This way, you have a 45%  
chance of hearing "Win", and if you hear "Null", there's still an 18%  
chance that your team won.

Conversely, if you're highly risk averse, you can reverse the 90-10  
rule, which will give you a 5% chance of learning of a win, and a 45%  
chance that a "Null" is really a win.  Of course, you can pick any  
point you prefer on that spectrum.

-Matt Jensen
  http://mattjensen.com
  Seattle

> Quoting Matt Jensen <mattj at newsblip.com>:
>
>> I'm looking for a technique for revealing info, but only if the info
>> has one particular value.
>>
>> For example: Suppose a couple is pregnant with their second child. The
>> first kid is a girl, and though the couple will love the second kid
>> regardless of gender, they'd be extra excited if it turned out to be a
>> boy.  (Plus, they could start outfitting the nursery.)
>>
>> So, we now want to know if there's some procedure whereby they can
>> have the sonographer tell them if it's a boy, but not tell them
>> anything if it's a girl.  Obviously, not telling them anything tells
>> them it's a girl.  Anyway around this?
>>
>> Ideally, you'd like a 100% chance of learning that it's a boy.
>> However, in order trust an answer like "I can't tell you the result
>> because our protocol forbids it", it seems you have to accept a lower
>> chance of getting the good news.
>>
>> I suppose you could have the sonographer secretly flip a coin, and if
>> it's heads, she tells the parents the gender.  But if it's a girl you
>> actually have the sonographer lie to you, and tell you she got tails,
>> so she can't tell you the gender.  But even that tells you something:
>> there are two "tails" outcomes for  a girl and only one "tails"
>> outcome for a boy.
>>
>> I feel like there's a better answer to this question, but I'm missing
>> it.  Ideas?
>>
>> -Matt Jensen
>>   http://mattjensen.com
>>   Seattle
>>
>> _______________________________________________
>> FoRK mailing list
>> http://xent.com/mailman/listinfo/fork
>>
>
>
>
>
>
>




More information about the FoRK mailing list