The Two Sheriffs Problem: Cryptographic Formalization and Generalization

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.