Author |
Topic: Simulate coin tossing over phone. (Read 3520 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Simulate coin tossing over phone.
« on: May 28th, 2009, 1:18pm » |
 Quote  Modify
|
Two persons A and B want to simulate an unbiased coin tossing over phone, regarding a bet. How can they simulate it? Assuming there is no trust between them or a trusted third party or any other means of communication.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #1 on: May 28th, 2009, 1:41pm » |
Quote Modify
|
Do they have access to a computer to make calculations?
They could send each other a salt, toss a coin, hash salt+toss+pass, then the toss, and then the pass so they can check it was honest, and the unbiased coin toss is the XOR of both tosses (say, H+H=T, H+T=H, T+H=H, T+T=T). Everything in separate stages.
The hash ensures with a very high degree of probability that they can't lie about the toss. Because they have to declare the hash before sending eachother their toss, it means that to change their toss, they'd have to find another password that together with the other toss gives the same hash. This is very difficult to do; but it might be possible with enough time to calculate it in advance. But they also have to include the salt provided by the other person, which means they can't precompute such a thing.
|
| « Last Edit: May 28th, 2009, 1:45pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #2 on: May 31st, 2009, 2:25am » |
Quote Modify
|
on May 28th, 2009, 1:41pm, towr wrote:Do they have access to a computer to make calculations?
|
|
I don't think so. The question involves only the phone. Nothing else should be used.
Quote:
They could send each other a salt, toss a coin, hash salt+toss+pass, then the toss, and then the pass so they can check it was honest, and the unbiased coin toss is the XOR of both tosses (say, H+H=T, H+T=H, T+H=H, T+T=T). Everything in separate stages.
|
|
Didn't get it at all.
|
| « Last Edit: May 31st, 2009, 2:26am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #3 on: May 31st, 2009, 7:11am » |
Quote Modify
|
on May 31st, 2009, 2:25am, R wrote:
I don't think so. The question involves only the phone. Nothing else should be used. |
|
They might be using voip.
Quote:Not even the part where they combine two results of which they know at least one to be random, and which will therefor be random?
Suppose I throw a coin, and you lie about throwing a coin; let's say you always say you threw heads. Then if I throw heads, the end result is H+H=T, if I throw tails, the result is H+T=H [edited typo]; despite the fact you cheated it would still be random. And of course the reverse is true, if I cheated but you didn't. If neither of us cheated it is also random. And if both of us cheated, well, without first agreeing how we both cheat, it will still tell us nothing about the end result or allow us to benefit, so for all intents and purposes that's also random; there isn't a way to cheat in a way that profits you.
However, this relies on a simultaneous exchange of both coin-tosses. By breaking it down into parts, you can make a secure asynchronous exchange. As it where they first send a locked box with the result of their coin-toss, and then in the next phase they send the keys to open them.
One small final trick is needed, so that neither player can have a 'box' that has two keys, and where each key opens a different drawer (without even revealing this fact). And the obvious way to ensure this is by providing the box that the other person puts the result of his coin-toss in.
So, in this analogy you have
1) throw coins
2) exchange boxes
3) put result of cointoss in the box you got from the other player
4) lock boxes with your own lock and key
5) exchange boxes
6) exchange keys
7) open boxes
8) 'calculate' the end result according to a predetermined rule
And all these analogous steps can be done using cryptography, such that you can do the exchange of information over the phone rather than the postal service.
|
| « Last Edit: May 31st, 2009, 4:57pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Simulate coin tossing over phone.
« Reply #4 on: May 31st, 2009, 3:32pm » |
Quote Modify
|
on May 31st, 2009, 7:11am, towr wrote:
The typo ...H+T=H already corrected.
|
| « Last Edit: Jun 4th, 2009, 12:02pm by Hippo » |
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #5 on: Jun 3rd, 2009, 9:29pm » |
Quote Modify
|
on May 31st, 2009, 7:11am, towr wrote:
And all these analogous steps can be done using cryptography, such that you can do the exchange of information over the phone rather than the postal service. |
|
Nice one towr. I want you to put some light on one small point. See the hash transforms a message m, into H(m) such that no one can find out m, just from H(m) and there is no other m` for which H(m`) = H(m). Right??
Hash only digitally signs the message. If you use only digital signature, then it won't work. Because the domain of m, is too small, i.e. [H,T]. The other person can try both of them, and can easily find out for which one of them (H(H) or H(T)) he gets H(m) (received by you). And after he finds out, he can easily manipulate his reply, to win the toss.
Exactly how, in your method, have you taken care of that? I guess some keys(you've mentioned)?? This part is not clear.
|
| « Last Edit: Jun 3rd, 2009, 9:35pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #6 on: Jun 3rd, 2009, 9:34pm » |
Quote Modify
|
on May 31st, 2009, 7:11am, towr wrote:
They might be using voip.
|
|
I am not sure. I was thinking if we could do it by using only the speech and the keypad on the phone (may be by dialing some numbers).
If we could use the computer, the problem would have said, simulate a coin toss between two hosts on a network of computers.
|
| « Last Edit: Jun 3rd, 2009, 9:35pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #7 on: Jun 4th, 2009, 12:31am » |
Quote Modify
|
on Jun 3rd, 2009, 9:29pm, R wrote:| Nice one towr. I want you to put some light on one small point. See the hash transforms a message m, into H(m) such that no one can find out m, just from H(m) and there is no other m` for which H(m`) = H(m). Right?? |
|
Yes; or at least one is unlikely to find such an m' in reasonably time.
Quote:| Hash only digitally signs the message. If you use only digital signature, then it won't work. Because the domain of m, is too small, i.e. [H,T]. |
|
I think you missed the part where I included a salt and a password. The domain is quite a bit larger.
Quote:| The other person can try both of them, and can easily find out for which one of them (H(H) or H(T)) he gets H(m) (received by you). And after he finds out, he can easily manipulate his reply, to win the toss. |
|
No, he can't, because he doesn't know which password you added before you hashed your result. He get H(his_salt + m + your_password), and m + your_password is unknown to him. He can guess m, but not your password (if you have a sense of choosing a decent password).
And because you exchange the hashes before sharing the password, you avoid someone modifying his message.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #8 on: Jun 4th, 2009, 12:44am » |
Quote Modify
|
on Jun 4th, 2009, 12:31am, towr wrote:
I think you missed the part where I included a salt and a password. The domain is quite a bit larger.
|
|
Yes, I forgot to mention that I didn't get this "SALT" thing. What is it? and why is it required?
|
| « Last Edit: Jun 4th, 2009, 12:51am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #9 on: Jun 4th, 2009, 12:50am » |
Quote Modify
|
on Jun 3rd, 2009, 9:34pm, R wrote:
I am not sure. I was thinking if we could do it by using only the speech and the keypad on the phone (may be by dialing some numbers).
|
|
I wanted to say that, we just need to design such an event (usign speech and keypad) which has a probability of success = 1/2 and failure = 1/2. There need not be an actual toss of coin.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #10 on: Jun 4th, 2009, 1:45am » |
Quote Modify
|
on Jun 4th, 2009, 12:44am, R wrote:| Yes, I forgot to mention that I didn't get this "SALT" thing. What is it? and why is it required? |
|
http://en.wikipedia.org/wiki/Salt_(cryptography) (Although, I'm maybe abusing the term a little. But I've got to call it something.)
The reason I include a "salt", is so that your opponent can't calculate two passwords such that H(H+pass1)=H(T+pass2) He can't find two passwords such that H(salt+H+pass1)=H(salt+T+pass2) because he doesn't control the "salt" value, and won't have enough time to compute those two passwords (which is fairly unlikely to start with if you agree on a decent hashing function). It adds a bit of extra security.
|
| « Last Edit: Jun 4th, 2009, 1:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #11 on: Jun 4th, 2009, 1:58am » |
Quote Modify
|
on Jun 3rd, 2009, 9:34pm, R wrote:| If we could use the computer, the problem would have said, simulate a coin toss between two hosts on a network of computers. |
|
I don't think so. I've seen plenty of puzzles that basically ask for a computer algorithm, but phrase it in entirely different terms.
on Jun 4th, 2009, 12:50am, R wrote:
I wanted to say that, we just need to design such an event (usign speech and keypad) which has a probability of success = 1/2 and failure = 1/2. There need not be an actual toss of coin. |
|
Well, by all means, give it a shot. I have my doubts you can do it without any cryptographic tricks though (regardless of whether you need a computer to execute them).
Btw, my solution doesn't really need a coin toss either, both player could just pick a number in a known range, and then whoever has the highest number wins.
Perhaps you could even adapt the solution to the puzzle where two people want to find out which one is older (or has a higher salary) without either revealing the exact age (amount).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #12 on: Jun 4th, 2009, 2:41am » |
Quote Modify
|
on Jun 4th, 2009, 1:58am, towr wrote:
Btw, my solution doesn't really need a coin toss either, both player could just pick a number in a known range, and then whoever has the highest number wins.
|
|
That's exactly what I was thinking, but didn't seem to work.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Simulate coin tossing over phone.
« Reply #13 on: Jun 4th, 2009, 1:29pm » |
Quote Modify
|
on Jun 4th, 2009, 1:45am, towr wrote:
The reason I include a "salt", is so that your opponent can't calculate two passwords such that H(H+pass1)=H(T+pass2) He can't find two passwords such that H(salt+H+pass1)=H(salt+T+pass2) because he doesn't control the "salt" value, and won't have enough time to compute those two passwords (which is fairly unlikely to start with if you agree on a decent hashing function). It adds a bit of extra security.
|
|
Presumably you are restricting the pass space such that he can't just pick pass2 = pass1 + H-T. But as written he can still desalinate his hash collision by a simple subtraction.
You can avoid hash collisions entirely by making the password unique for a given output, for example using a public cryptosystem as the 'salt', sending an encrypted bit (padded to increase keyspace), and then exchanging decryption keys. (Basically, make the hash more subtly dependent on the salt.)
More generally, you should also be able to use any 'hard' problem that's in NP  co-NP (e.g., determine a given bit of plaintext, given the ciphertext) by sending an instance with the desired answer as your bit, and then revealing the proof.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #14 on: Jun 4th, 2009, 2:25pm » |
Quote Modify
|
on Jun 4th, 2009, 1:29pm, Eigenray wrote:
Presumably you are restricting the pass space such that he can't just pick pass2 = pass1 + H-T. But as written he can still desalinate his hash collision by a simple subtraction. |
|
+ stands for concatenation in my case; the salt and passwords can be any sort of string, not just a number.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Simulate coin tossing over phone.
« Reply #15 on: Jun 4th, 2009, 5:53pm » |
Quote Modify
|
on Jun 4th, 2009, 2:25pm, towr wrote:
+ stands for concatenation in my case; the salt and passwords can be any sort of string, not just a number.
|
|
Ah, yes a monoid makes much more sense here.
Anyway, all they really need is a way to hide a bit so that it can be transmitted much faster than it can be decoded. If neither has a computer, they can describe their bits simultaneously as a sequence of arithmetic operations, references to the n-th word in a common book, etc. Something as simple as the parity of (31415911 mod 17) is probably enough for most people, if you both agree to end your descriptions at roughly the same time. But that would work better if they had recording devices.
But if they don't trust each other or a third party at all, then why should the loser honor the bet? I think they would need to have something like a recording device or a public key on record somewhere so they can both sign each other's commitments and verify the signatures before revealing their bits.
|
| « Last Edit: Jun 4th, 2009, 6:06pm by Eigenray » |
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #16 on: Apr 26th, 2010, 5:34am » |
Quote Modify
|
I recently came across a solution:
Quote:
A flips a coin. If the result is heads, A multiplies 2 prime numbers containing about 90 digits; if the result is tails, A multiplies 3 prime numbers containing about 60 digits. A tells B the result of the multiplication. B now calls either heads or tails and tells A. A then supplies B with the original numbers to verify the flip. |
|
Any comments??
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simulate coin tossing over phone.
« Reply #17 on: Apr 26th, 2010, 8:04am » |
Quote Modify
|
Seems good in first instance; but how will B check that the number A tells him is not a multiplication of two 30-digit primes (p,q) and two 60 digit primes (r,s)?
If B cannot quickly confirm that the two or three numbers A gives are indeed prime, then A might get away with cheating; because he could just say the number breaks down as {p*r, q*s} or {p*q, r, s} depending on B's flip and A's desired result.
|
| « Last Edit: Apr 26th, 2010, 8:06am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Simulate coin tossing over phone.
« Reply #18 on: Apr 26th, 2010, 10:01am » |
Quote Modify
|
It shouldn't be any problem to verify primality of the factors, so long as computers are allowed. I believe 60 digits is fairly tiny for primality testing.
In fact, in addition to providing the factors, A should also have to provide a proof that they are prime.
So long as B has to respond with heads or tails within a second or two of receiving A's number, he'll have no chance of factoring it. Of course, as technology improves, it might be necessary to increase the length of A's number to increase security. But primality testing for larger numbers will also be easier then.
|
| « Last Edit: Apr 26th, 2010, 10:13am by Obob » |
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #19 on: Apr 26th, 2010, 10:20am » |
Quote Modify
|
Another issue is: How will A come-up with such big prime numbers, in the first place?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Simulate coin tossing over phone.
« Reply #20 on: Apr 26th, 2010, 10:34am » |
Quote Modify
|
Just pick random numbers. The probability that a random 60-digit number is prime is on the order of .7%. You can then test their primality nearly instantly on a computer.
Here's a bunch of 59-digit primes I constructed in under a second with mathematica: (these are the primes out of 2000 randomly selected 59-digit numbers)
880041377370330568199786638927683307542211747645070808965267
227655554752565730074660654199397617966230153059057632819349
429047078190403811351552971095300104072075135770347712710259
672413720815561871708851999670888119518611666947267822114261
187180748659786232830689144497523574640221482569494995325687
657524956521006652571825296061413105446215076970708652202721
445323201667633243181496354790350850077446244706918830183637
521237793009856635468077461693858188084081846057151160578943
827327169932940637375916148390147798059370606113819052963157
397070214674951596675835628882171461004502331958161106369619
131518839300855587279064189228548632413948423766420092357463
808505107635780612337948253081284851732707527855844137825849
883295669928029853981095059271105210089292996712322158203143
In fact, primality testing is SO fast that you could easily use much much larger primes to ensure security. I was able to generate the following 200-digit primes in ~1 second by testing 2000 random numbers:
624354772245680437071791932055059033234908944445608860488221473383700913 861023826935779135190379902526986867005020786445632040108937343727334595 278810782633517277305454201921459320824606056742762742291
523992454350572669033612631140023178367520283961797871365385385577288755 868349380819881276857224322546372519977433477676880084529389620728706429 728101582912192517551744814058985201821156410486960454589
938771599470812289606626424914731493899250325808917732381675392365505945 460472073071630126972896657315207493471382306882432691483265236925708132 346337829643090706148677051178518435131133223418281638379
766972958077205207669816040886336653961238791569370178058276519036492968 229086794678656102044715538749164126989080325067498915038199233004719161 230339592495911428740124559267578219034395752607066273801
893143110851170960609521369307392465716425505844986030230740563537523004 673695709332372565563021573934385259941471784699956046007270824204744576 185391922366159744081267847778475671685506497590978551157
908742681034320129882149784454716825699172060799799090604297551057601045 614648522515689269061713100575323070608831288925009111876441713813567902 727898213343893281599471729529754515252593536914346723931
170888987282936744332356985768255473022983298307028090940304936986319122 965536136741762054468044483201800634550790435077425318066473238025164214 446175283231471977812189624598072748236612688681289770139
626506232950290719299885106618635044177467440274017157900462222912102707 090912971286935481241855664201259966126405003220761145771275122650766213 918265369468796361177711272562376585444263094555134057089
|
| « Last Edit: Apr 26th, 2010, 10:40am by Obob » |
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Simulate coin tossing over phone.
« Reply #21 on: Apr 26th, 2010, 10:47am » |
Quote Modify
|
on Apr 26th, 2010, 10:34am, Obob wrote:
In fact, primality testing is SO fast that you could easily use much much larger primes to ensure security. I was able to generate the following 200-digit primes in ~1 second by testing 2000 random numbers:
|
|
By using computer right?? Not by hand.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Simulate coin tossing over phone.
« Reply #22 on: Apr 26th, 2010, 10:52am » |
Quote Modify
|
Yes, of course. You'd have to be crazy to try and show a 60-digit number is prime by hand.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Simulate coin tossing over phone.
« Reply #23 on: Apr 30th, 2010, 12:58am » |
Quote Modify
|
If both of you have access to the same phone book, you can do as follows.
Each of you selects a name from the phone book and, when both are ready, you both give the selected name without delay. A wins if both numbers have the same parity, B wins if not.
The time it takes to look up the name given by the other person (or even typing in the name on a computer) takes enough time to prevent that one's name is selected with the knowledge of the other name's parity.
If you don't have a common phone book, you can start the conversation with one person reading the whole phone book over the phone. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print