Communication efficient shuffle for mental poker protocols

Mental poker protocols are considered to be computationally and communicationally consuming. A secure and fast mental poker protocol was proposed by Wang and Wei (2009) [26]. The cost of communication (total length of message) can be considered as feasible, but is still relatively expensive for networks with lower bandwidths. A shuffle requires 64 MB of data transmission for a typical setting (9 players, 52 cards, 1024 bit keys, and security parameter L = 100). The most communicationally consuming part of Wang and Wei's protocol is the shuffle verification protocol SV. In this paper, we propose a new method to verify the integrity of the shuffle, namely, NewSV which can be used as a drop-in replacement for SV. NewSV is slower than SV. The benefit of using NewSV is that the communication cost can be greatly reduced. Using the same settings, if NewSV is used instead of SV, then 70% of the communication cost can be saved. A shuffle requires only 20 MB of data transmission for L = 100. The computational overhead is 7-2% for security parameter L = 30-100. This technique can be applied to a similar mental poker protocol proposed by Castella-Roca (2004) [7]. The Castella-Roca's shuffle requires 154 MB of data transmission for L = 100. By using NewSV, 87% of the communication cost can be reduced so that only 20 MB of data transmission is required. The computational overhead is also 7-2% for L = 30-100.