mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2020-03-14, 19:23   #1
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·61·83 Posts
Default Scrambling Bob & Alice, encryption for board game play across the net

Mod Note:This thread was split from the thread quoted in this post.

Quote:
Originally Posted by ewmayer View Post
Sis just e-mailed me, we enjoy getting together for classic hard-fought bouts of Family Death Scrabble especially around holidays and long rainy weekends. She suggested some kind of online Scrabble app allowing us to play remotely could be a fun thing to do in coming everything-shut-down months. I don't do smartphones (well, aside from repurposing select bet-up used ones to run Mlucas under a freeware linux environment, that is :), but that poses an interesting DIY problem. My reply:
Cryptographic protocols for such problems were invented decades ago. Most were described in terms of card games such as poker so that is perhaps where you should direct your attention. https://en.wikipedia.org/wiki/Mental_poker might get you started.

TL;DR --- it is possible to implement a system where it is possible to detect when someone is cheating.

Last fiddled with by Uncwilly on 2020-03-16 at 14:13
xilman is offline   Reply With Quote
Old 2020-03-14, 21:25   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·727 Posts
Default

Quote:
Originally Posted by xilman View Post
TL;DR --- it is possible to implement a system where it is possible to detect when someone is cheating.
For a fun to read but serious introduction to such protocols, try Bruce Schneier's book
"Applied Cryptography".
Nick is online now   Reply With Quote
Old 2020-03-15, 08:56   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23×727 Posts
Default

Quote:
Originally Posted by xilman View Post
Cryptographic protocols for such problems were invented decades ago. Most were described in terms of card games such as poker so that is perhaps where you should direct your attention. https://en.wikipedia.org/wiki/Mental_poker might get you started.
I've always wondered why the second stage of applying individual keys is necessary. From the WP page steps 8 through 14 seem to be redundant. Alice and Bob can simply decode each card with their initial key and send the card, instead of sending the individual key, for the other party to decode. Then each party only has to manage a single key. If Bob could learn something from the decoded cards about Alice's key then then step 4 is insecure and the whole protocol fails.
retina is online now   Reply With Quote
Old 2020-03-15, 10:43   #4
axn
 
axn's Avatar
 
Jun 2003

22×32×131 Posts
Default

Quote:
Originally Posted by retina View Post
I've always wondered why the second stage of applying individual keys is necessary.
At the end of step 8, alice has a shuffled deck encrypted by only bob's key (and vice versa). Now alice wants to draw a specific card (say card 26). What information should alice request from bob such that:
a) alice can decode the specific card ...
b) ... without bob knowing what card it is ...
c) ... and furthermore, without alice being able to decode the whole deck?
axn is offline   Reply With Quote
Old 2020-03-15, 11:18   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23×727 Posts
Default

Quote:
Originally Posted by axn View Post
At the end of step 8, alice has a shuffled deck encrypted by only bob's key (and vice versa). Now alice wants to draw a specific card (say card 26). What information should alice request from bob such that:
a) alice can decode the specific card ...
b) ... without bob knowing what card it is ...
c) ... and furthermore, without alice being able to decode the whole deck?
Alice asks Bob to decode card x, where x=m0AB, and send the result to her. Bob knows only B so Alice gets m0A and she can then decode using her key A to reveal the card m0. Alice can't decode the rest of the pack, m1..51AB, since she doesn't know B. And Bob doesn't know what card 0 is since he doesn't know A.

Last fiddled with by retina on 2020-03-15 at 11:20
retina is online now   Reply With Quote
Old 2020-03-15, 12:34   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×61×83 Posts
Default

Quote:
Originally Posted by retina View Post
Alice asks Bob to decode card x, where x=m0AB, and send the result to her. Bob knows only B so Alice gets m0A and she can then decode using her key A to reveal the card m0. Alice can't decode the rest of the pack, m1..51AB, since she doesn't know B. And Bob doesn't know what card 0 is since he doesn't know A.
And how do you detect that Bob is telling the truth and not cheating by sending a card of his choice?
xilman is offline   Reply With Quote
Old 2020-03-15, 13:13   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

16B816 Posts
Default

Quote:
Originally Posted by xilman View Post
And how do you detect that Bob is telling the truth and not cheating by sending a card of his choice?
Firstly, it wouldn't matter since Bob has no way to choose a particular card of his choice, because Alice already shuffled them. So the best Bob can do is simply choose a different card at random, and Alice still gets a random card. And also then Bob and Alice will have mismatching records of the remaining cards.

And secondly the protocol still needs to be verified at the finish of the hand to verify there were no anomalies, so the final transfer of keys and seeds etc. will reveal any and all previous attempts to cheat. So it is of no advantage to Bob to select a different card, because if he does he gets caught when the hand is over.

ETA: Actually Alice can also ask Bob to select a card or her. There really isn't a need for Alice to select the card. Just let Bob select it, decode his part, and send it. Or even always select the first card from the pack. No random choice is needed since they are already shuffled.

Last fiddled with by retina on 2020-03-15 at 13:22
retina is online now   Reply With Quote
Old 2020-03-16, 08:10   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19·467 Posts
Default

Quote:
Originally Posted by retina View Post
I've always wondered why the second stage of applying individual keys is necessary. From the WP page steps 8 through 14 seem to be redundant. Alice and Bob can simply decode each card with their initial key and send the card, instead of sending the individual key, for the other party to decode. Then each party only has to manage a single key. If Bob could learn something from the decoded cards about Alice's key then then step 4 is insecure and the whole protocol fails.
It may seem like any of the halves could be enough (for example, you could directly start by individually encrypting each card), but it is not so. Both halves are necessary. Think about the case when more than two players play. They can't send "the card", because they don't know it. "The card" they know is the encrypted (how many times??) string they got when they applied their "general" key. When only 2 players play, "the card" is just one. When N players play, there are binomial number (N,2) possibilities. Therefore, individual keys for each card from each partner in the game is mandatory. But those can be applied only after cards were shuffled, and no shuffles could be done after (otherwise you don't know which individual key corresponds to what). However, starting directly with individual keys is not possible (as Alice would know all the cards, they can't be shuffled after individual keys were applied). So, you need a general key for shuffling, then individual keys to ensure normal progress of the game.

Interesting enough, there is also at least one patent for it.

Fun story: the "millionaire" problem also has a "socialist" version, in the past I struggled for weeks to understand why they made it so complicate, when a simple combination of SHA256 or so, of the info should be enough. But actually, it is not. And I am not talking about "fill the last 5 bytes of the block with your wealth, as none of us is richer than a trillion dollars, then apply SHA to it, and we can compare the result", that would be indeed stupid, as the search space is very low and it can be bruteforced. I am talking about the most general case when two people want to decide if they have the same information without revealing it, when a "full block" of SHA is filled with random data, and that can't be bruteforced.

Last fiddled with by LaurV on 2020-03-16 at 08:16
LaurV is offline   Reply With Quote
Old 2020-03-16, 09:31   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23·727 Posts
Default

Quote:
Originally Posted by LaurV View Post
It may seem like any of the halves could be enough (for example, you could directly start by individually encrypting each card), but it is not so. Both halves are necessary. Think about the case when more than two players play. They can't send "the card", because they don't know it. "The card" they know is the encrypted (how many times??) string they got when they applied their "general" key. When only 2 players play, "the card" is just one. When N players play, there are binomial number (N,2) possibilities. Therefore, individual keys for each card from each partner in the game is mandatory. But those can be applied only after cards were shuffled, and no shuffles could be done after (otherwise you don't know which individual key corresponds to what). However, starting directly with individual keys is not possible (as Alice would know all the cards, they can't be shuffled after individual keys were applied). So, you need a general key for shuffling, then individual keys to ensure normal progress of the game.
I still don't see the need for the second half.

26 players A..Z: After the initial round of shuffling we have card 0 = m0A..Z. To select a card for Alice we have Zelda decode card 0 to m0A..Y and pass to Yolanda. Then Yolanda decodes to m0A..X and passes to Xavier ... <snip 22 steps> ... Bob decodes to m0A and passes to Alice. Lastly Alice decodes to m0 and reveals the card to herself.

What am I not seeing?
retina is online now   Reply With Quote
Old 2020-03-21, 16:38   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

16B816 Posts
Default

Quote:
Originally Posted by retina View Post
What am I not seeing?
It isn't mentioned anywhere that I can see but might it be because of efficiency concerns?

It would be more efficient to have Alice receive all the keys B-Z and then she can simply compute A*B*C*..*Z mod phi(p) to get the decode key. But that would seem to be specific to the usage of primitive roots modulo p for the commutative encryption scheme. Other schemes might not exhibit this advantage.

retina is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Holy New Board Game MattcAnderson Puzzles 2 2015-10-18 09:40
If you won't play online I won't play with your stuff at all jasong jasong 1 2014-06-30 02:23
Alice in Wonderland ZFR Puzzles 36 2013-10-23 16:16
Encryption and governments retina Soap Box 119 2012-02-28 05:00
American Mcgee's Alice Margaret3000 Computer Games 3 2004-10-16 16:14

All times are UTC. The time now is 12:08.

Wed Oct 28 12:08:37 UTC 2020 up 48 days, 9:19, 1 user, load averages: 1.74, 1.54, 1.69

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.