How to Implement a Non-uniform or Non-closed Shuffle

Card-based protocols allow to perform secure multiparty computations using a deck of physical cards, and rely on shuffle actions such as the (normal) shuffle, the random cut, and the random bisection cut. A shuffle action is mathematically defined by a pair of a permutation set (which is a subset of the symmetric group) and a probability distribution on it; while one can theoretically consider any shuffle action in mind, he or she may be unable to determine whether it can be easily implemented by human hands. As one of the most general results, Koch and Walzer showed that any uniform closed shuffle (meaning that its permutation set is a subgroup and its distribution is uniform) can be implemented by human hands with the help of additional cards. However, there are several existing protocols which use non-uniform and/or non-closed shuffles. To implement these specific shuffles, Nishimura et al. proposed an idea of using (special) physical cases that can store piles of cards as well as Koch and Walzer proposed an implementation of a specific non-closed shuffle with additional cards. Because their implementations handle a limited class of non-uniform and/or non-closed shuffles, it is still open to find a general method for implementing any shuffle. In this paper, we solve the above problem; we implement “any” shuffle with only additional cards, provided that every probability of its distribution is a rational number. Therefore, our implementation works for any non-closed or non-uniform shuffle (if the distribution is rational as above).