Secure and practical constant round mental poker ?
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) 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-Rocas 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 L = 4 . The time complexity of our shuffle is ?(MN+N2)E ? ( MN + N 2 ) E (compares to ?(MN2L)E ? ( MN 2 L ) 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) ? ( N 3 L ) to ?(N2) ? ( N 2 ) , and the total length of messages is reduced from ?(N2L(M+N))? ? ( N 2 L ( M + N ) ) ? to ?(MN2)? ? ( MN 2 ) ? , 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 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,
mental poker zero-knowledge ddh assumption