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.
- DDH assumption
- Mental poker