国際会議

The Two Sheriffs Problem: Cryptographic Formalization and Generalization
 著者
 K. Sugimoto, T. Nakai, Y. Watanabe, and M. Iwamoto
 会議名
 COCOA 2023
 巻
 LNCS 14461
 ページ
 512–523
 出版社
 Springer
 発行年
 2023
 発表日
 2023/12/17
Abstract
The two sheriffs problem is the following problem. There are two sheriffs, and each of them has their own list of suspects. Assuming that these lists are the result of a proper investigation, we can say that a culprit is the intersection of them even if the sheriffs do not know who the culprit is. Now, they wish to identify the culprit through an open channel, i.e., to compute the intersection of two lists, without letting an eavesdropper know the culprit who observed all communications. This cryptographic problem was proposed by Beaver et al., and a combinatorial solution using a bipartite graph was proposed. In this paper, we propose a formulation of the two sheriffs problem by introducing a secrecy evaluation based on the eavesdropper’s attack success probability. Furthermore, we propose an improved version of Beaver et al.’s protocol that an arbitrary number of players can execute and has less attack success probability.