Card-Based Secure Sorting Protocol
Card-Based Secure Sorting Protocol
复制标题
基于卡片的安全排序协议
DOI：
10.1007/978-3-031-15255-9_12
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mizuki Takaaki
中科院分区：
文献类型：
--
作者：
Haga Rikuo;Toyoda Kodai;Shinoda Yuto;Miyahara Daiki;Shinagawa Kazumasa;Hayashi Yuichi;Mizuki Takaaki
近年来，基于卡的密码学的研究领域一直在发展，它依靠一副物理卡来执行密码功能，从基本的安全计算（例如安全 AND 和 XOR 评估）到更复杂的任务（例如姚氏百万富翁问题和零知识证明）。在本文中，我们提出了一种基于卡片的“安全排序”协议；尽管排序可能是计算机科学中最基本的问题，但基于卡的密码学领域尚未解决安全排序问题。给定一系列面朝下的卡片，代表带有值（待排序）的键的集合，我们提出的协议对它们进行排序，而不会泄漏任何信息。正如想象的那样，安全分拣提供了许多应用；例如，我们展示了如何应用我们的协议来实施拍卖。由于许多计算问题的算法（例如图算法）使用排序作为子例程，因此我们期望我们的安全排序协议在构建有关计算问题的基于卡的安全计算时将很有用。
The research area of card-based cryptography, which relies on a deck of physical cards to perform cryptographic functionalities, has been growing in recent years, ranging from basic secure computations, such as secure AND and XOR evaluations, to more complex tasks, such as Yao’s Millionaires’ problem and zero-knowledge proof. In this paper, we propose a card-based “secure sorting” protocol; although sorting is probably the most fundamental problem in computer science, secure sorting has not been addressed in the field of card-based cryptography yet. Given a sequence of face-down cards representing a collection of keys with values (to be sorted), our proposed protocol sorts them without leaking any information. As imagined, secure sorting provides many applications; for instance, we show how to apply our protocol to implementing an auction. Since many algorithms for computational problems (say, graph algorithms) use sorting as subroutines, we expect that our secure sorting protocol will be useful when constructing card-based secure computations regarding computational problems.