Card-based protocols for secure ranking computations
Card-based protocols for secure ranking computations
复制标题
用于安全排名计算的基于卡的协议
DOI：
10.1016/j.tcs.2020.09.008
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Sone Hideaki
中科院分区：
文献类型：
--
作者：
Takashima Ken;Abe Yuta;Sasaki Tatsuya;Miyahara Daiki;Shinagawa Kazumasa;Mizuki Takaaki;Sone Hideaki
考虑一下一群人，他们想知道其中的“富豪榜”，即他们的总资产排名，但没有透露任何关于他们资产实际价值的信息。这可以通过由酱和Gong(2006)[2]最先考虑的“安全排名计算”来实现；他们构造了一个基于公钥密码体制的安全排名计算协议。在本文中，我们不使用公钥密码系统，而是使用一副物理卡片来提供安全的排名计算协议。因此，我们的基于卡的协议不依赖于计算机，并且它们简单且易于人类实现。具体地说，我们设计了四个协议，考虑了卡的数量和执行协议所需的洗牌数量之间的权衡。我们还提出了根据参与协议的人数和输入范围的大小来选择合适的协议的指南。准确地说，我们的协议让所有玩家都知道富豪榜，而姜公方案让每个玩家只知道他/她的排名；使用一副纸牌来完成相同的任务(与姜公方案一样)是一个有趣的开放问题。
Consider a group of people who want to know the “rich list” among them, namely the ranking in terms of their total assets, without revealing any information about the actual value of their assets. This can be achieved by a “secure ranking computation,” which was first considered by Jiang and Gong (2006) [2]; they constructed a secure ranking computation protocol based on a public-key cryptosystem. In this paper, instead of using a public-key cryptosystem, we use a deck of physical cards to provide secure ranking computation protocols. Therefore, our card-based protocols do not rely on computers, and they are simple and easy for humans to implement. Specifically, we design four protocols considering tradeoffs between the number of cards and the number of shuffles required to execute the protocols. We also present a guide to choose an appropriate protocol according to the number of people participating in the protocol and the size of the input range. To be precise, whereas our protocols make all players know the rich list, the Jiang–Gong scheme makes each player know his/her rank only; to achieve the same task (as the Jiang–Gong scheme) using a deck of cards is an intriguing open problem.