How to Implement a Non-uniform or Non-closed Shuffle
How to Implement a Non-uniform or Non-closed Shuffle
复制标题
如何实现非均匀或非封闭的洗牌
DOI：
10.1007/978-3-030-63000-3_9
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shizuya Hiroki
中科院分区：
文献类型：
--
作者：
Saito Takahiro;Miyahara Daiki;Abe Yuta;Mizuki Takaaki;Shizuya Hiroki
基于卡片的协议允许使用一副物理卡片执行安全的多方计算，并依赖于洗牌动作，如(正常)洗牌、随机剪切和随机对分剪切。洗牌动作是由一对排列集(它是对称群的子集)和其上的概率分布在数学上定义的；虽然人们在理论上可以考虑脑海中的任何洗牌动作，但他或她可能无法确定它是否可以很容易地由人手实现。作为最一般的结果之一，Koch和Walzer证明了任何一致的闭洗牌(即它的排列集是一个子群，它的分布是均匀的)都可以在附加卡片的帮助下由人手实现。然而，存在几个使用非均匀和/或非封闭混洗的现有协议。为了实现这些具体的洗牌，Nishimura等人。提出了使用可以存储成堆纸牌的(特殊)物理情况的想法，以及Koch和Walzer提出了用额外的纸牌实现特定的非封闭洗牌。因为它们的实现只处理有限类的非统一和/或非闭合的随机洗牌，所以仍然可以找到实现任意随机洗牌的通用方法。在这篇文章中，我们解决了上述问题；我们实现了“任意”洗牌，只要它的分布的每个概率都是有理数。因此，我们的实现适用于任何非封闭或非均匀的混洗(如果分布如上所述是合理的)。
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).