wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Simulate coin tossing over phone.
        
(Message started by: inexorable on May 28th, 2009, 1:18pm)
Title: Simulate coin tossing over phone.
Post by inexorable on May 28th, 2009, 1:18pm
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.
Title: Re: Simulate coin tossing over phone.
Post by towr on May 28th, 2009, 1:41pm
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.
Title: Re: Simulate coin tossing over phone.
Post by R on May 31st, 2009, 2:25am

on 05/28/09 at 13:41:46, 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.
Title: Re: Simulate coin tossing over phone.
Post by towr on May 31st, 2009, 7:11am

on 05/31/09 at 02:25:57, R wrote:
I don't think so. The question involves only the phone. Nothing else should be used.
They might be using voip.


Quote:
Didn't get it at all.
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.
Title: Re: Simulate coin tossing over phone.
Post by Hippo on May 31st, 2009, 3:32pm

on 05/31/09 at 07:11:07, towr wrote:
H+H=T, H+T=T


The typo ...H+T=H already corrected.
Title: Re: Simulate coin tossing over phone.
Post by R on Jun 3rd, 2009, 9:29pm

on 05/31/09 at 07:11:07, 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.
Title: Re: Simulate coin tossing over phone.
Post by R on Jun 3rd, 2009, 9:34pm

on 05/31/09 at 07:11:07, 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.
Title: Re: Simulate coin tossing over phone.
Post by towr on Jun 4th, 2009, 12:31am

on 06/03/09 at 21:29:42, 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.
Title: Re: Simulate coin tossing over phone.
Post by R on Jun 4th, 2009, 12:44am

on 06/04/09 at 00:31:57, 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?
Title: Re: Simulate coin tossing over phone.
Post by R on Jun 4th, 2009, 12:50am

on 06/03/09 at 21:34:04, 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.
Title: Re: Simulate coin tossing over phone.
Post by towr on Jun 4th, 2009, 1:45am

on 06/04/09 at 00:44:38, 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.
Title: Re: Simulate coin tossing over phone.
Post by towr on Jun 4th, 2009, 1:58am

on 06/03/09 at 21:34:04, 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 06/04/09 at 00:50:42, 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).
Title: Re: Simulate coin tossing over phone.
Post by R on Jun 4th, 2009, 2:41am

on 06/04/09 at 01:58:51, 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.
Title: Re: Simulate coin tossing over phone.
Post by Eigenray on Jun 4th, 2009, 1:29pm

on 06/04/09 at 01:45:34, 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gif 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.
Title: Re: Simulate coin tossing over phone.
Post by towr on Jun 4th, 2009, 2:25pm

on 06/04/09 at 13:29:53, 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.
Title: Re: Simulate coin tossing over phone.
Post by Eigenray on Jun 4th, 2009, 5:53pm

on 06/04/09 at 14:25:14, 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.
Title: Re: Simulate coin tossing over phone.
Post by R on Apr 26th, 2010, 5:34am
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??
Title: Re: Simulate coin tossing over phone.
Post by towr on Apr 26th, 2010, 8:04am
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.
Title: Re: Simulate coin tossing over phone.
Post by Obob on Apr 26th, 2010, 10:01am
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.
Title: Re: Simulate coin tossing over phone.
Post by R on Apr 26th, 2010, 10:20am
Another issue is: How will A come-up with such big prime numbers, in the first place?
Title: Re: Simulate coin tossing over phone.
Post by Obob on Apr 26th, 2010, 10:34am
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:

624354772245680437071791932055059033234908944445608860488221473383700913861023826935779135190379902526986867005020786445632040108937343727334595278810782633517277305454201921459320824606056742762742291

523992454350572669033612631140023178367520283961797871365385385577288755868349380819881276857224322546372519977433477676880084529389620728706429728101582912192517551744814058985201821156410486960454589

938771599470812289606626424914731493899250325808917732381675392365505945460472073071630126972896657315207493471382306882432691483265236925708132346337829643090706148677051178518435131133223418281638379

766972958077205207669816040886336653961238791569370178058276519036492968229086794678656102044715538749164126989080325067498915038199233004719161230339592495911428740124559267578219034395752607066273801

893143110851170960609521369307392465716425505844986030230740563537523004673695709332372565563021573934385259941471784699956046007270824204744576185391922366159744081267847778475671685506497590978551157

908742681034320129882149784454716825699172060799799090604297551057601045614648522515689269061713100575323070608831288925009111876441713813567902727898213343893281599471729529754515252593536914346723931

170888987282936744332356985768255473022983298307028090940304936986319122965536136741762054468044483201800634550790435077425318066473238025164214446175283231471977812189624598072748236612688681289770139

626506232950290719299885106618635044177467440274017157900462222912102707090912971286935481241855664201259966126405003220761145771275122650766213918265369468796361177711272562376585444263094555134057089
Title: Re: Simulate coin tossing over phone.
Post by R on Apr 26th, 2010, 10:47am

on 04/26/10 at 10:34:05, 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.
Title: Re: Simulate coin tossing over phone.
Post by Obob on Apr 26th, 2010, 10:52am
Yes, of course.  You'd have to be crazy to try and show a 60-digit number is prime by hand.
Title: Re: Simulate coin tossing over phone.
Post by Grimbal on Apr 30th, 2010, 12:58am
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.  ;D


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board