@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00223228,
 author = {杉本, 航太 and 中井, 雄士 and 渡邉, 洋平 and 岩本, 貢 and Kota, Sugimoto and Takeshi, Nakai and Yohei, Watanabe and Mitsugu, Iwamoto},
 book = {コンピュータセキュリティシンポジウム2022論文集},
 month = {Oct},
 note = {本稿では Two Sheriffs Problem と呼ばれる以下の問題を考える．二人の保安官がそれぞれ容疑者のリストを持っており，両方のリストに含まれる人物が犯人である．二人は公開の通信路を用いて犯人を特定したいが，通信をすべて傍受する盗聴者には犯人が分からないようにしたい．この問題は Beaver らによって提案され，彼らによって組合せ論的解法が示された．彼らの手法は盗聴者が犯人を一意に特定できないことを安全性の根拠としているため，犯人の候補が二人まで絞れても安全であると考えており，仮に犯人がどちらか全く分からなくても，確率 1/2 で犯人を特定出来る．そこで本稿では，Two Sheriffs Problem の安全性について，Beaver らの定義を含む一般的な定式化を与え，より攻撃成功確率が小さいプロトコルを提案する．Beaver らは犯人がただ一人であることを仮定しているが，提案プロトコルは複数の犯人でも実行できるプロトコルに拡張されており，攻撃成功確率と容疑者のリストのサイズとのトレードオフがあることを明らかにする．, In this paper, we consider the following problem, called the Two Sheriffs Problem. Two sheriffs each have a list of suspects in a murder case, and the person on both lists is the killer. The sheriffs wish to identify the killer using open communication channels, but they do not want an eavesdropper who intercepts all communications to know who the killer is. This problem was proposed by Beaver et al., and they presented a combinatorial solution. In their protocol, the protocol is considered secure if the eavesdropper cannot uniquely identify the killer; thus, it is secure even if the number of the possible killer is reduced to two. In this paper, we formalize the security of the Two Sheriffs Problem, including Beaver et al.'s definition, and propose a protocol with a smaller probability of successful attack. Furthermore, the proposed protocol applies to the case of multiple killers, whereas Beaver et al. assumed only one killer. Our proposed protocol has a tradeoff between the probability of a successful attack and the size of the suspect list.},
 pages = {1254--1261},
 publisher = {情報処理学会},
 title = {攻撃成功確率からみたTwo Sheriffs Problem},
 year = {2022}
}