Secure and practical constant round mental poker

Tze-Jen Wei*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We present a new mental poker protocol, which achieves negligible probability of cheating in constant round. All of previous secure mental poker protocol use L-round zero-knowledge protocols to ensure the probability of successful active cheating to be O(2-L). Our protocol uses a different way to verify the integrity of the shuffle. The cryptosystem and the basic structure of our protocol is based on Castellà-Roca's mental protocol, which is very efficient and secure. The L-round zero-knowledge shuffle verification is replaced by a checksum-like framework. There are two kinds of checksums used in our shuffle: linear checksum and double exponentiation. The "linear checksum" is used to make sure that every card in the deck is distinct. The "double exponentiation checksum" is used to make sure that every card has a legitimate face value. The security can be proved under DDH assumption. The probability of successful cheating is negligible, even if the adversary can actively corrupt the majority of players. It is also very fast. For a 9 player game, the computation cost of our shuffle is comparable to the L-round verification with L=4. The time complexity of our shuffle is Θ(MN+N2)E (compares to Θ(MN2L)E for a L-round shuffle), where N is the number of players, M is the number of cards, and E is the computation cost of one modular exponentiation. The communication cost is also reduced. Compares to the L-round protocol we based on, number of messages is reduced from Θ(N3L) to Θ(N2), and the total length of messages is reduced from Θ(N2L(M+N))η to Θ(MN2)η, where η is the length of an encryption key. For a 9-player game, our shuffle requires only 53% messages, and total length of messages is only 7%(compares to the case L=30 and all L rounds of shuffle verification are allowed to run in parallel). It is the first constant round mental poker protocol that is provably secure and efficient enough to satisfy the practical needs. The probability of successful cheating is negligible.

Original languageEnglish
Pages (from-to)352-386
Number of pages35
JournalInformation sciences
Volume273
DOIs
StatePublished - 20 Jul 2014

Keywords

  • DDH assumption
  • Mental poker
  • Zero-knowledge

Fingerprint Dive into the research topics of 'Secure and practical constant round mental poker'. Together they form a unique fingerprint.

Cite this