How to Solve Millionaires’ Problem with Two Kinds of Cards
How to Solve Millionaires’ Problem with Two Kinds of Cards
复制标题
如何用两种卡解决百万富翁的问题
DOI：
10.1007/s00354-020-00118-8
复制
发表时间：
2021
影响因子：
2.6
通讯作者：
Ohta Kazuo
中科院分区：
文献类型：
--
作者：
Nakai Takeshi;Misawa Yuto;Tokushige Yuuki;Iwamoto Mitsugu;Ohta Kazuo
由den Boer提出的基于卡片的密码学旨在通过使用物理卡片来实现多方计算（MPC）。我们通过引入一种名为“私有排列”（PP）的新操作来代替大多数现有基于卡的密码学中使用的洗牌，提出了几种有效的基于卡的协议来解决百万富翁的问题。洗牌是一种利用洗牌特性的有用的随机化技术，但从算术MPC的角度来看，它需要一个强有力的假设，因为洗牌假设公共随机化是可能的。另一方面，私有随机性可以用于PP，这使我们能够设计基于卡的协议，考虑到算术MPC的想法。实际上，我们表明，姚的百万富翁协议可以很容易地转换成一个基于卡的协议，通过使用PP，这是不简单的，因为姚的协议使用私人随机性。此外，我们提出了全新的和有效的基于卡的百万富翁协议的基础上PP的安全更新两个数字之间的逐位比较，揭示了PP的权力。作为这些协议的另一个兴趣，我们指出它们与众所周知的逻辑难题“岔路口”有着深刻的联系。
Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.”