Scrambling Bob & Alice, encryption for board game play across the net

[xilman]

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

Originally Posted by ewmayer

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.

[Nick]

Originally Posted by xilman

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".

[retina]

Originally Posted by xilman

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.

[axn]

Originally Posted by retina

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?

[retina]

Originally Posted by axn

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=m₀^AB, and send the result to her. Bob knows only B so Alice gets m₀^A and she can then decode using her key A to reveal the card m₀. Alice can't decode the rest of the pack, m_1..51^AB, since she doesn't know B. And Bob doesn't know what card 0 is since he doesn't know A.

[xilman]

Originally Posted by retina

Alice asks Bob to decode card x, where x=m₀^AB, and send the result to her. Bob knows only B so Alice gets m₀^A and she can then decode using her key A to reveal the card m₀. Alice can't decode the rest of the pack, m_1..51^AB, 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?

[retina]

Originally Posted by xilman

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.

[LaurV]

Originally Posted by retina

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.

[retina]

Originally Posted by LaurV

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 = m₀^A..Z. To select a card for Alice we have Zelda decode card 0 to m₀^A..Y and pass to Yolanda. Then Yolanda decodes to m₀^A..X and passes to Xavier ... <snip 22 steps> ... Bob decodes to m₀^A and passes to Alice. Lastly Alice decodes to m₀ and reveals the card to herself.

What am I not seeing?

[retina]

Originally Posted by retina

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.