385:
achieves significantly higher performance by exploiting the properties of the poker game to move away from the encrypt-shuffle model. Rather than shuffle the cards and then deal as needed, with the new approach, the players generate (encrypted) random numbers on the fly, which are used to select the next card. Every new card needs to be checked against all the cards that have already been dealt to detect duplicates. As a result, this method is uniquely useful in poker-style games, in which the number of cards dealt is very small compared to the size of the whole deck. However, the method needs all cards that have already been dealt to be known to all, which in most poker-style games would beat its very purpose.
22:
730:
Otherwise, if any agent doesn't participate in the encryption, then that agent is susceptible to being cheated by a coalition of the remaining players. Unknown to the non-encrypting agent, the other agents may share the keys to enable them all to know the values of all the cards. Thus, any approach relying on the agents to perform the encryption must focus on schemes that minimize the effect of collisions if they are to achieve better performance.
781:. The scheme may be extended to allow more servers, (and thus, increased security), simply by including the additional servers in the initial encryption. Finally, step one in the protocol may be done offline, allowing for large numbers of shuffled, encrypted "decks" to be pre-computed and cached, resulting in excellent in-game performance.
738:
Any mental poker protocol that relies on the players to perform the encryption is bound by the requirement that every player encrypt every card that is dealt. However, by making limited assumptions about the trustworthiness of third parties, significantly more efficient protocols may be realized. The
356:
Christian
Schindelhauer describes sophisticated protocols to both perform and verify a large number of useful operations on cards and stacks of cards in his 1998 paper "A Toolbox for Mental Card Games" . The work is concerned with general-purpose operations (masking and unmasking cards, shuffling and
115:
The problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?" (Eliminating the trusted third-party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the
729:
Measured in terms of the number of single-agent encryptions, the algorithm in is optimal when no collisions occur, in the sense that any protocol that is fair to every player must perform at least as many encryption operations. At minimum, every agent must encrypt every card that is actually used.
119:
In poker, this could translate to: "How can we make sure no player is stacking the deck or peeking at other players' cards when we are shuffling the deck ourselves?". In a physical card game, this would be relatively simple if the players were sitting face to face and observing each other, at least
637:
In this way, the players need only to compute encryption for the cards that are actually used in the game, plus some overhead for the collisions that is small as long as the number of cards needed is much less than the size of the deck. As a result, this scheme turns out to be 2-4 times faster (as
295:
During the game, Alice and Bob will pick cards from the deck, identified in which order they are placed in the shuffled deck. When either player wants to see their cards, they will request the corresponding keys from the other player. That player, upon checking that the requesting player is indeed
347:
Depending on the deck agreed upon, this algorithm may be weak. When encrypting data, certain properties of this data may be preserved from the plaintext to the ciphertext. This may be used to "tag" certain cards. Therefore, the parties must agree on a deck where no cards have properties that are
384:
To date, mental poker approaches based on the standard Alice-Bob protocol (above) do not offer high enough performance for real-time online play. The requirement that each player encrypts each card imposes a substantial overhead. A recent paper by Golle describes a mental poker protocol that
336:: Bob must not be able to determine Alice's original key A (or enough of it to allow him to decrypt any cards he does not hold) based on his knowledge of the unencrypted values of the cards he has drawn. This rules out some obvious commutative encryption schemes, such as simply
147:-encryption protocol). This protocol was the first example of two parties conducting secure computation rather than secure message transmission, employing cryptography; later on due to leaking partial information in the original protocol, this led to the definition of
376:, achieving modest real-world performance. The game Skat is played by three players with a 32-card deck, and so is substantially less computationally intensive than a poker game in which anywhere from five to eight players use a full 52-card deck.
776:
must collude if either is to learn the values of any cards. Furthermore, because players ultimately decide which cards are dealt, non-trustworthy servers are unable to influence the game to the extent that is possible in traditional
299:
Example: Alice has picked cards 1 to 5 in the shuffled deck. Bob has picked cards 6 to 10. Bob requests to look at his allotted cards. Alice agrees that Bob is entitled to look at cards 6 to 10 and gives him her individual card keys
120:
if the possibility of conventional cheating can be ruled out. However, if the players are not sitting at the same location but instead are at widely separate locations and pass the entire deck between them (using the postal
128:, where the mechanics of the game are hidden from the user, this is impossible unless the method used is such that it cannot allow any party to cheat by manipulating or inappropriately observing the electronic "deck".
296:
entitled to look at the cards, passes the individual keys for those cards to the other player. The check is to ensure that the player does not try to request keys for cards that do not belong to that player.
739:
protocol for choosing cards without shuffling may be adapted so that the encryption is handled by two or more servers. Under the assumption that the servers are non-colluding, such a protocol is secure.
764:
The random number is used as an index into the random permutation, the appropriate player gains "ownership" of the specified card, and the servers send that player the keys to read the card's value.
570:
613:
724:
222:
Alice and Bob agree on a certain "deck" of cards. In practice, this means they agree on a set of numbers or other data such that each element of the set represents a card.
684:
372:
The C++ library libtmcg provides an implementation of the
Schindelhauer toolbox. It has been used to implement a secure version of the German card game
187:
encryption scheme. A commutative scheme means that if some data is encrypted more than once, the order in which one decrypts this data will not matter.
812:: Cryptoprotocols: Subscription to a Public Key, the Secret Blocking and the Multi-Player Mental Poker Game (Extended Abstract). CRYPTO 1984: 439-453.
260:
Bob decrypts each card using his key B. This still leaves Alice's individual encryption in place though so he cannot know which card is which.
43:
896:
797:
A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Memo LCS/TM-125, Massachusetts
Institute of Technology, April 1979.
243:
Alice decrypts each card using her key A. This still leaves Bob's encryption in place though so she cannot know which card is which.
65:
105:
210:. When decrypting this double encrypted message, if the encryption scheme is commutative, it will not matter who decrypts first.
761:
Players compute independent random numbers in {0,...,51}, which are combined to generate a random number in {0,..., 51}, as in
164:
365:, and the general scheme is similar in spirit to the above protocol. The correctness of operations can be checked by using
100:
which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum's
231:
Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
638:
measured by the total number of modular exponentiations) than the best-known protocol that does full shuffling using
36:
30:
842:
388:
The card-generation algorithm requires a cryptosystem with two key properties. The encryption E must be additively
316:. Bob can now see the cards. Alice cannot know which cards Bob has because she does not have access to Bob's keys B
511:
758:
of encrypted cards to the players. This can be done with any of several well-understood cryptographic protocols.
340:
each card with the key. (Using a separate key for each card even in the initial exchange, which would otherwise
47:
277:
Alice publishes the deck for everyone playing (in this case only Alice and Bob, see below on expansion though).
457:
scheme is just one example of a well-known system with these properties. The algorithm operates as follows:
357:
re-shuffling, inserting a card into a stack, etc.) that make the protocols applicable to any card game. The
333:
852:. In Proceedings of the International Conference on Information Technology: Coding and Computing, (2005)
579:
366:
234:
Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
86:
454:
207:
109:
412:. Second, collisions must be detectable, without revealing the plaintext. In other words, given
862:
836:
Efficient
Electronic Gambling: An Extended Implementation of the Toolbox for Mental Card Games
829:
Probabilistic encryption & how to play mental poker keeping secret all partial information
484:
362:
148:
124:, for instance), this suddenly becomes very difficult. And for electronic card games, such as
689:
820:
646:
373:
152:
144:
369:, so that players do not need to reveal their strategy to verify the game's correctness.
798:
664:
849:
439:, without the players learning any other information (specifically, the identities of
890:
824:
289:
285:
206:. Bob encrypts the ciphertext again, using the same scheme as Alice but with another
203:
191:
156:
101:
82:
835:
754:
encrypt and shuffle a deck of cards, and publish a non-malleable commitment to some
778:
358:
341:
218:
An algorithm for shuffling cards using commutative encryption would be as follows:
125:
308:. Bob decrypts his cards by using both Alice's keys and his own for these cards, B
93:
surrounding these problems and their possible solutions. The name comes from the
876:
755:
649:
is secure as long as any one player is generating valid random numbers. Even if
639:
389:
184:
140:
85:
problems that concerns playing a fair game over distance without the need for a
831:. In Proceedings of the Fourteenth Annual ACM Symposium on theory of Computing.
828:
225:
Alice picks an encryption key A and uses this to encrypt each card of the deck.
163:'s 1984 book Cryptoprotocols. The area has later evolved into what is known as
880:
872:
199:
136:
132:
809:
195:
176:
160:
94:
284:
This algorithm may be expanded for an arbitrary number of players. Players
90:
180:
344:, doesn't work since the cards are shuffled before they're returned.)
868:
LibTMCG - C++ library for creating secure and fair online card games
131:
Several protocols for doing this have been suggested, the first by
97:
867:
633:. When cards need to be revealed, they can be jointly decrypted.
240:
Bob passes the double encrypted and shuffled deck back to Alice.
121:
337:
15:
159:. The concept of multi-player mental poker was introduced in
183:
cards without the use of a trusted third party is to use a
505:, and can verify that every player honors its commitment
352:"A Toolbox for Mental Card Games" and its implementation
167:
protocols (for two parties, and multi parties as well).
883:
explaining the intuition behind the Mental Poker paper.
799:
https://apps.dtic.mil/dtic/tr/fulltext/u2/a066331.pdf
692:
667:
582:
514:
468:
To deal a card, each player computes a random number
742:
The basic protocol using two servers is as follows:
718:
678:
607:
564:
332:The encryption scheme used must be secure against
292:and so forth need only repeat steps 2-4 and 8-10.
629:is dealt to the appropriate player, and added to
845:. Tech. Rep. of Medizinische Universitat Lubeck.
198:message. She encrypts this, producing a garbled
246:Alice picks one encryption key for each card (A
263:Bob picks one encryption key for each card (B
8:
565:{\displaystyle \Pi E(r_{i})=E(\Sigma r_{i})}
171:Shuffling cards using commutative encryption
734:Better performance through increased trust
691:
666:
599:
581:
553:
528:
513:
324:which are required to decrypt the cards.
66:Learn how and when to remove this message
661:th player truthfully generates a random
428:, it must be possible to answer whether
29:This article includes a list of general
790:
653:players collude to generate the number
271:, etc.) and encrypts them individually.
254:, etc.) and encrypts them individually.
726:is still uniformly random in {0, 51}.
572:, which produces a new encrypted card
7:
465:that records cards that are in use.
361:used by Schindelhauer are based on
838:. WEWoRC 2005, LN P-74, 1-12, 2005
592:
546:
515:
497:Players then publish their actual
274:Bob passes the deck back to Alice.
89:. The term is also applied to the
35:it lacks sufficient corresponding
14:
461:Players initialize an empty list
483:, and publishes a non-malleable
81:is the common name for a set of
20:
873:Dealing Cards with Cryptography
843:A Toolbox for Mental Card Games
608:{\displaystyle r*=\Sigma r_{i}}
102:flipping a coin over a distance
863:A bibliography on mental poker
559:
543:
534:
521:
380:A non-shuffling poker protocol
165:secure multi-party computation
1:
348:preserved during encryption.
257:Alice passes the deck to Bob.
850:Dealing Cards in Poker Games
106:Yao's Millionaires' Problem
913:
768:In this protocol, servers
281:The deck is now shuffled.
228:Alice shuffles the cards.
897:Cryptographic algorithms
647:random number generation
475:in {0,...,51}, computes
202:which she gives then to
719:{\displaystyle r=r*+r'}
359:cryptographic protocols
342:make this scheme secure
334:known-plaintext attacks
50:more precise citations.
720:
680:
609:
566:
237:Bob shuffles the deck.
721:
681:
610:
567:
367:zero-knowledge proofs
363:quadratic residuosity
143:(the creators of the
116:resources required.)
690:
665:
580:
512:
87:trusted third party
841:Schindelhauer, C.
716:
679:{\displaystyle r'}
676:
605:
562:
455:Elgamal encryption
110:oblivious transfer
657:, as long as the
617:Players check if
149:semantic security
76:
75:
68:
904:
813:
807:
801:
795:
725:
723:
722:
717:
715:
685:
683:
682:
677:
675:
614:
612:
611:
606:
604:
603:
571:
569:
568:
563:
558:
557:
533:
532:
508:Players compute
153:Shafi Goldwasser
71:
64:
60:
57:
51:
46:this article by
37:inline citations
24:
23:
16:
912:
911:
907:
906:
905:
903:
902:
901:
887:
886:
859:
817:
816:
808:
804:
796:
792:
787:
736:
708:
688:
687:
668:
663:
662:
595:
578:
577:
549:
524:
510:
509:
502:
492:
480:
473:
451:
444:
437:
433:
425:
417:
409:
405:
401:
397:
382:
354:
330:
323:
319:
315:
311:
307:
303:
270:
266:
253:
249:
216:
173:
72:
61:
55:
52:
42:Please help to
41:
25:
21:
12:
11:
5:
910:
908:
900:
899:
889:
888:
885:
884:
870:
865:
858:
857:External links
855:
854:
853:
846:
839:
832:
821:Goldwasser, S.
815:
814:
802:
789:
788:
786:
783:
766:
765:
762:
759:
735:
732:
714:
711:
707:
704:
701:
698:
695:
674:
671:
645:Note that the
635:
634:
621:is already in
615:
602:
598:
594:
591:
588:
585:
561:
556:
552:
548:
545:
542:
539:
536:
531:
527:
523:
520:
517:
506:
500:
495:
490:
478:
471:
466:
449:
442:
435:
431:
423:
415:
407:
403:
399:
395:
381:
378:
353:
350:
329:
326:
321:
317:
313:
309:
305:
301:
279:
278:
275:
272:
268:
264:
261:
258:
255:
251:
247:
244:
241:
238:
235:
232:
229:
226:
223:
215:
212:
172:
169:
108:, and Rabin's
74:
73:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
909:
898:
895:
894:
892:
882:
878:
874:
871:
869:
866:
864:
861:
860:
856:
851:
847:
844:
840:
837:
833:
830:
826:
822:
819:
818:
811:
806:
803:
800:
794:
791:
784:
782:
780:
775:
771:
763:
760:
757:
753:
749:
745:
744:
743:
740:
733:
731:
727:
712:
709:
705:
702:
699:
696:
693:
672:
669:
660:
656:
652:
648:
643:
641:
632:
628:
624:
620:
616:
600:
596:
589:
586:
583:
575:
554:
550:
540:
537:
529:
525:
518:
507:
504:
496:
494:
486:
482:
474:
467:
464:
460:
459:
458:
456:
452:
445:
438:
427:
419:
411:
391:
386:
379:
377:
375:
370:
368:
364:
360:
351:
349:
345:
343:
339:
335:
327:
325:
297:
293:
291:
287:
282:
276:
273:
262:
259:
256:
245:
242:
239:
236:
233:
230:
227:
224:
221:
220:
219:
214:The algorithm
213:
211:
209:
205:
201:
197:
193:
188:
186:
182:
178:
175:One possible
170:
168:
166:
162:
158:
157:Silvio Micali
154:
150:
146:
142:
138:
134:
129:
127:
123:
117:
113:
111:
107:
103:
99:
96:
92:
88:
84:
83:cryptographic
80:
70:
67:
59:
49:
45:
39:
38:
32:
27:
18:
17:
805:
793:
779:online poker
773:
769:
767:
751:
747:
741:
737:
728:
658:
654:
650:
644:
640:mix-networks
636:
630:
626:
622:
618:
573:
498:
488:
476:
469:
462:
447:
440:
429:
421:
413:
393:
387:
383:
371:
355:
346:
331:
298:
294:
283:
280:
217:
189:
174:
130:
126:online poker
118:
114:
79:Mental poker
78:
77:
62:
53:
34:
879:video with
877:Numberphile
834:Stamer, H.
756:permutation
390:homomorphic
185:commutative
141:Len Adleman
48:introducing
881:Ron Rivest
848:Golle, P.
825:Micali, S.
785:References
686:, the sum
625:. If not,
485:commitment
392:, so that
200:ciphertext
137:Ron Rivest
133:Adi Shamir
56:April 2019
31:references
810:Moti Yung
703:∗
593:Σ
587:∗
547:Σ
516:Π
196:plaintext
190:Example:
181:shuffling
177:algorithm
161:Moti Yung
95:card game
891:Category
746:Servers
713:′
673:′
328:Weakness
91:theories
576:, with
453:). The
402:) = E(c
44:improve
827:1982.
338:XORing
194:has a
33:, but
627:E(r*)
619:E(r*)
574:E(r*)
398:)*E(c
286:Carol
192:Alice
98:poker
875:- A
823:and
772:and
750:and
446:and
420:and
374:Skat
320:to B
312:to B
304:to A
290:Dave
179:for
155:and
139:and
122:mail
651:k-1
499:E(r
489:E(r
487:to
477:E(r
422:E(c
414:E(c
406:+ c
394:E(c
267:, B
250:, A
208:key
204:Bob
151:by
145:RSA
104:,
893::
774:S2
770:S1
752:S2
748:S1
655:r*
642:.
434:=c
322:10
314:10
306:10
288:,
135:,
112:.
710:r
706:+
700:r
697:=
694:r
670:r
659:k
631:L
623:L
601:i
597:r
590:=
584:r
560:)
555:i
551:r
544:(
541:E
538:=
535:)
530:i
526:r
522:(
519:E
503:)
501:i
493:)
491:i
481:)
479:i
472:i
470:r
463:L
450:2
448:c
443:1
441:c
436:2
432:1
430:c
426:)
424:2
418:)
416:1
410:)
408:2
404:1
400:2
396:1
318:6
310:6
302:6
300:A
269:2
265:1
252:2
248:1
69:)
63:(
58:)
54:(
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.