1
$\begingroup$

I had an idea for a Mental Poker algorithm. Since I'm a n00b, there is likely to be things wrong with it. But since I'm a n00b, I am not able to detect the problems yet. Would this algorithm ensure a fair game?

Imagine a point in the middle of the game where Alice and Bob each have 5 cards in their hand and Bob wants to draw a new one from the deck.

Imagine the cards are numbered 1-52. Alice creates a "codebook" assigning each card to a random number. According to the codebook, $\{(1, a_1), (2, a_2), ...\}$. Alice sends Bob the random numbers, in a shuffled order. She also publishes a hash of the entire codebook.

Bob picks a card from the shuffled deck. Say he picks $a_{14}$. He doesn't know what this number means.

The first thing to do is make sure this card isn't in Alice's hand. Since Alice has five cards in her hand, they do five rounds of Socialist Millionaires. They want to find out if Bob's $a_{14}$ is equal to any of the cards in Alice's hand. Alice knows the codebook, so she knows that the encoded version of each of the cards in her hand. One by one, they test Bob's card against the encoded version of each card in Alice's hand.

Since they're doing Socialist Millionaires, they can do this test without Alice discovering what card Bob is considering, and without Bob discovering what's in Alice's hand.

Say it turns out that Bob has picked a card that Alice does not have. Alice now reveals the entire codebook. This lets Bob look up the card he just drew ($a_{14}$), and find that he's just picked up card #14. Because Alice sent the entire codebook, she does not leak information about what's in her hand, and Bob can look up his card without leaking any information about what card he just drew. Since Alice published a hash of the codebook before, she can't cheat and force Bob to take a bad card. If she posts a codebook that doesn't match the hash she published earlier, Bob knows she's up to something. Even if she wanted to, she wouldn't know what slot to put the bad card into because she doesn't know what card Bob picked.

Now Bob tests to see if the card he's just drawn is already in his hand. If it is, he reports this to Alice. "Oops, my bad, I need to redraw", he says. Alice produces a new codebook and starts again. She never found out what it was that Bob drew, so the fact that the card is in Bob's hand doesn't tell her anything new.

Okay, but what if, in their earlier comparison, it turned out that the card Bob just drew, $a_{14}$, was in Alice's hand already?

In this case, Alice and Bob would both be aware of this, because of the Socialist Millionaires protocol. At this point, Bob only knows that Alice has card $a_{14}$ in her hand. He does not know what card $a_{14}$ is, though. So what they do is just throw away the codebook. Bob never learns what card $a_{14}$ was. Alice makes a new codebook and they start over.

Does this work? I think so.

The procedure works the same on the first draw. Bob just has to compare his pick against all 0 of the cards in Alice's hand. And when he knows what it is, he has to compare it against all 0 of the cards in his hand.

If this is a game where cards are revealed to everybody throughout the course of the game, those can be removed from the codebooks to reduce the chances of picking an already-picked card.

You might end up just thrashing around picking the same cards over and over again, only to find that they are already in somebody's hand. But at least nobody knows what those cards are!

EDIT: Could Bob draw a card legitimately, but then ignore it when Alice sends the codebook and instead pick his favorite card? If he did that, he has no information about if Alice has the card, so there might be a collision. That might not be a problem if it's the first draw of the game, or if Bob just gets lucky. However, we can do things like, when Bob picks his card $a_{14}$, but before the codebook is revealed, he has to post a hash of $(a_{14}, \text{nonce})$, and then reveal the nonce at the end of the game, to prove he picked his card fairly. Or maybe, at the end of the game, he has to reveal the random numbers he picked for Socialist Millionaires so Alice can see what card he was considering at the time.

$\endgroup$
2
$\begingroup$

Three issues:

  1. It is super slow.
  2. The "Oops, my bad, I need to redraw" is not correct because he can always say that when he gets anything but a king or a queen.
  3. Alice could also probably pretend she has a better deck than she has (with a nice probability of not getting caught).
$\endgroup$
  • $\begingroup$ 1. Yes, it is. 2. Bob has to call for a redraw before Alice reveals the codebook, so by the time Bob knows that what he has is a king or queen, it's too late to redraw. 3. How? $\endgroup$ – Ryan Hughes Oct 23 '18 at 10:22
  • $\begingroup$ Oh, oops. You're right. When Bob checks if the card is already in his hand, he can cheat. (He'll get caught at the end of the game when all the secrets are revealed, though). $\endgroup$ – Ryan Hughes Oct 23 '18 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.