Talk:Mental poker

Mistake in the first shuffling algorithm?

Hello, I've noticed something that looks like an omission by the author of the section. If Bob gets the deck from Alice in point 4, he truly does not know which card is which. But Alice does. If they're to provide keys for decrypting, say, card 10 later, how would a player know that the card they're holding is #10 (if the deck is encrypted mutliple times)? And if so, can't Alice simply map the number-card relations and cheat since she is the only person to see the unencrypted deck? — Preceding unsigned comment added by 207.189.30.104 (talk) 22:41, 21 March 2019 (UTC)

Collusion

Hi - is it possible to design a system where, to help prevent cheating, some centralised agency (e.g. the Poker Room) gets sent all the encryption keys after the hand is dealt, so that it can investigate any possible collusion? Would this be possible? Evercat 11:46, 27 August 2005 (UTC)

Doesn't that defeat the point? If there is a trusted centralised agency, couldn't it do the shuffling and dealing of cards. 157.161.173.24

I don't think a central agency could prevent all forms of collusion, since players can communicate with each other by different means and e.g. show each other their hands and work together to defeat another. — Preceding unsigned comment added by 2A02:A457:9497:1:3022:EC23:A7E7:F446 (talk) 11:46, 9 April 2020 (UTC)

Where's Shafi?

The whole concept of "mental poker" was invented by Goldwasser and Micali. I'm surprised she isn't credited in the text. I'd also expect to see at least some mention of Oded Goldreich (Weizmann Kavod).

69.250.225.1 (talk) 03:31, 12 June 2019 (UTC) No, Mental Poker was invented by Shamir, Rivest and Adleman.

Commutative encryption?

Which encryption schemes are commutative, besides RSA with identical moduli? Because I heard there was an attack against using RSA to encrypt two messages with two different moduli. --Zemyla^t 16:04, 31 May 2006 (UTC)

2 possible cards (heck why not 52) packaged as 1 card, when 'A' key is sent it unencrypts the card of choice from the host who initialy encrypted... Same thought occurred to me, anyone have any references on such code? —Preceding unsigned comment added by 96.2.147.222 (talk) 06:01, 23 December 2007 (UTC)

Question

Doesn't this algorithm have the weakness that Bob has no way of knowing if Alice replaced the deck with one that contains duplicate cards, say to increase the odds of picture cards etc. There would need to be a step at the end that decrypted all of the cards to ensure that no alterations had been made to the freqencies of the cards in the deck by the first encryptor. Another possible problem would be for the final shuffler to replace the cards that would be dealt to him with plain text cards, since he has the right to see them from the beginning, he can request the keys to decrypt them, but throw them away. I suppose again this would be solved by insisting that every card in the game is decrypted at the end so that everyone can check that the deck wasn't modified. This way, at least you'd be sure of knowing if someone cheated.Kybernetikos 09:37, 25 October 2006 (UTC)

Duplicate plain-text cards would result in duplicate encypted cards. Easilly detectable.

Replacing cards would result in Bob getting big errors when trying to decrypt his dealt cards. Also I think I remember that there are ways of checking cards with zero-knowledge proofs... but of that I'm not certain... crypto experts will have to answer that one. --J-Star 10:30, 25 October 2006 (UTC)

Not impressed with the Golle paper

Very hand-wavy about actual performance. It gives the time for setting up Millimix (the comparison baseline) as 6300 modular exponentiations. On modern hardware, Intel boasts of a Fast and Constant-Time Implementation of Modular Exponentiation that achieves a 512 bit modular exponentiation in 500,000 processor cycles, giving a Millimix latency of 3 billion processor cycles (circa 1 second) running on a single Nehalem core. The Golle paper improves the setup time by a factor of six.

The setup latency is an issue only when the players first join. Setup for a subsequent deal involving the same players can run in parallel with game play. Reading between the lines, the Golle result presumes a very high level of player thrash. When I've played online poker, often there is a mandatory one minute wait after the game is joined before the first deal. Only very modest hardware would struggle with this. One hesitates to imagine what a modern video card could achieve.

I don't think the article provides a proper frame of reference / perspective on actual cost in the real world. — MaxEnt 00:10, 10 December 2010 (UTC)

Actual performance

As above, I don't think the article provides a proper frame of reference as to real-world costs. In particular, this sentence: "To date, mental poker approaches based on the standard Alice-Bob protocol (above) don't offer high enough performance for real-time online play." doesn't seem very correct. I've done a simple test available at github using a shuffling protocol from libTMCG, and for 2 player Texas Hold'em it takes about 3.5 seconds on a modern processor while transmitting 160kB of data each way - so that's DEFINITELY high enough performance - I don't think anyone would mind 3.5 seconds for a shuffle. Uukgoblin (talk) 12:14, 24 June 2012 (UTC)

Indeed. Shuffling the deck by hand, riffling and cutting several times, usually takes me a minute or two and even that is acceptable since an actual card game tends to take much longer. So if libTMCG's implementation is correct, performance is no problem. — Preceding unsigned comment added by 2A02:A457:9497:1:3022:EC23:A7E7:F446 (talk) 11:27, 9 April 2020 (UTC)

Questions

‘Alice picks one encryption key for each card (A1, A2, etc.) and encrypts them individually.’

To me as a layman it isn't clear why this is done. This may be because I'm unfamiliar with the precise properties of the encryption algorithm used.

I think there's also a problem that cannot be solved, but that still deserves a mention: in a four player game, three players could secretly team up against one. I know it seems a bit obvious, but I think it must be stated explicitly.

This system as described in the article can deal open cards and closed cards that are visible to only one player. I haven't looked into this thoroughly but I imagine it might also be capable of dealing with exchanges and discards. Are there any standard card game actions that the system cannot cope with?

The article mentions that each card gets an individual encryption key from each player. So when a card is dealt and Alice needs to decrypt it so Bob can view it, how does Alice know which key to use given that it looks like indecipherable gibberish to her?

If a card needs to be discarded in a game variant and other players have no knowledge at all about each other's cards, from my cursory reading of the article it seems this is possible. But what if a game variant is played where sometimes a card has to be shown to another player? Is it possible for a player to discard a card without other players being sure if it's the known card or not?

In a game played with two decks, if Bob takes a card from Alice and then several turns later Alice takes a card from Bob, how can we prevent Alice from knowing whether it was the particular card she lost earlier and not its duplicate given that Alice uses a different encryption key for each card? — Preceding unsigned comment added by 2A02:A457:9497:1:3022:EC23:A7E7:F446 (talk) 11:40, 9 April 2020 (UTC)