Secure Computation for Threshold Functions with Physical Cards: Power of Private Permutations
Secure Computation for Threshold Functions with Physical Cards: Power of Private Permutations
复制标题
使用物理卡进行阈值函数的安全计算：私有排列的力量
DOI：
10.1007/s00354-022-00153-7
复制
发表时间：
2022
影响因子：
2.6
通讯作者：
Ohta Kazuo
中科院分区：
文献类型：
--
作者：
Nakai Takeshi;Shirouchi Satoshi;Tokushige Yuuki;Iwamoto Mitsugu;Ohta Kazuo
基于卡片的密码学是使用物理卡片（如扑克牌）进行多方计算的变体。基于卡的密码学有两种模型，称为公共模型和私有模型。公共模型假设所有操作都是公开执行的，而私有模型允许参与者进行私有操作，称为私有排列（PP，简称）。许多现有的基于卡的协议都是在公共模型下开发的。在公共模型下，每个具有n位输入的协议需要2n个卡，因为至少需要两个卡来表示一个位。在本文中，我们提出了位输入协议的少于2n卡利用PP，这表明PP的强大功能。特别是，我们表明，（n位输入）阈值函数的协议可以实现与onlycards通过减少阈值函数的多数表决。为此，我们首先提出，逻辑门的两位输入协议可以用少于四个卡来实现。此外，我们构造了一个新的协议，三个输入的多数表决只有四张卡，通过观察与/或操作之间的关系。该协议可以很容易地扩展到更多的参与者，并为阈值函数的协议。
Card-based cryptography is a variant of multi-party computation using physical cards like playing cards. There are two models on card-based cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing card-based protocols were developed under the public model. Under the public model, 2ncards are necessary for every protocol withn-bit input since at least two cards are required to express a bit. In this paper, we proposen-bit input protocols with fewer than 2ncards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit input) threshold function can be realized with onlycards by reducing the threshold function to the majority voting. Toward this end, we first offer that two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions.