NEHE 2008

kim · 敬拜者

Imagine a scenario, you and your friend in Vancouver would like to take a trip together this xmas. You want to go to Tokyo, while he/she wants to go to London, let's say. Nobody wants to give up his/her ground. so the best resolution is to simply flip a coin and see who wins right? (by guessing the head or tail)
But the problem is that one of you is in Ottawa while the other is in Vancouver!! and you have to make a decision before xmas so you can book your air tickets in advance.. what can u do ?

Mikka · 天使長

kim · 敬拜者

haha, even webcam can be compromised if the guy is a geek

um.. there's something called "remote coin tossing protocol" in the field of cryptocraphy. I will explain it in a later post ba.. busy these days

kim · 敬拜者

oh the good thing about "remote coin tossing protocol" is that u can even do it with someone u dont trust completely

kim · 敬拜者

Ok, just to explain it a bit for now
assuming there exist a canada-wide phone book directory which list every peron's phone number in Canada, and the book is organized by people's name alphabetically.
let's say both you and your friend have a copy of this phone book each. What you can do is the following , say your friend randomly pick a person's phone number from that book and read it out to you on the phone, and you have to guess whether the owner of that phone number is male or female immediately (say within 3 seconds).

can you see how it's actually a fair analogy of coin tossing?

kim · 敬拜者

ok, so let me explain further how the phone book scenario can actually be analogous to an actual coin tossing.

First, let's analyze what steps are involved in a typical coin tossing.
step 1. one of the two people is assigned to do the tossing.
step 2. the other person has to guess either the head or tails will be facing up
step 3. first guy tosses the coin
step 4. everybody sees the result right away

so let's see how it works with the other case
step 1. one person is assigned to randomly pick a phone number out of that
phone book
step 2. The person picks the a number and read it to the other guy
step 3. the other guy make the guess whether the phone number belong to
a guy or gal.
step 4. The first person tells the second guy the owner's name of that
phone number, so the second guy can look it up in the phone book
himself and verify whether he guessed right

as u can see, one guy does something, while the other guy makes the guess. Once the first guy did something, he can never cheat !! If your friend tell u a guy's number, and u guess it's a guy. Then u win. because ur friend cant give a girl's name and expect u to find that the number match that name in the phone book u hold.

rainingsky · 天使長

I dont get it

kim · 敬拜者

Imagine the following case
Alice and Bob each has a phone book.
and you can find anyone's phone number easily if you search by their name
say Bob wants to find Eve Wong's phone number. He goes to section W, then look for Eve (of course, let's assume there's just one Eve Wong in whole Canada). Now, you find Eve's phone number to be 613-124-5647. It's easy right? If I ask u to do it, you can probably find eve wong's phone number in 5 minutes at most, right? dont tell me otherwise

that will make me doubt ur intelligence

ok, but what about the following situation? I give you 613-124-5647? How fast do you think you can go through the phone book and give me a name of a person who own that phone number? Well, the book contains at least 100,000 names, let's say. Definitely , not in 5 minutes.. it will be lucky if you can do it in a few days..
This is something we called "one-way" function in Mathematics.
Ok, now, try to go back to the previous posts, and see whether this little bit of information helps u understand more about the situation.

Mikka · 天使長

kim · 敬拜者

alright, it's not a real coin tossing in anyway

but the beauty of abstraction in mathematics allows us to take out the "essence of coin tossing" and duplicate it in some other form.

The key is one person do the "tossing" - picking a phone number
and another person do the "guessing" - male or female
and in both case of phone book and real coin tossing, the result is "fair". NObody can cheat , of course, if we exclude all the obvious obstacles such as 1. the name might be ambiguous, hard to tell whether it's a guy or gal. 2. the guy guessing might recognize the phone number being picked because he/she knows the owner of that phone number beforehand etc etc.

In reality, of course, you dont use a phone book to do such a thing. You use some real math.. but I guess the closest analogy I can provide without referring to the real math is probably this phone book scenario.