攻撃成功確率からみたTwo Sheriffs Problem

• Item type: Symposium(1)
• 公開日: 2022-10-17
• タイトル: 攻撃成功確率からみたTwo Sheriffs Problem
• タイトル / 言語: en
• タイトル: The Two Sheriffs Problem through a Lens of Attack Success Probability
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: Two sheriffs problem, 組合せ的安全性，攻撃成功確率，二者間秘密計算
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 電気通信大学
• 著者所属: 豊橋技術科学大学
• 著者所属: 電気通信大学／産業技術総合研究所
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications,
• 著者所属(英): en
• 著者所属(英): Toyohashi University of Technology,
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications / National Institute of Advanced Industrial Science and Technology
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications,
• 著者名: 杉本, 航太; 中井, 雄士; 渡邉, 洋平; 岩本, 貢
• 著者名(英): Kota, Sugimoto; Takeshi, Nakai; Yohei, Watanabe; Mitsugu, Iwamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では Two Sheriffs Problem と呼ばれる以下の問題を考える．二人の保安官がそれぞれ容疑者のリストを持っており，両方のリストに含まれる人物が犯人である．二人は公開の通信路を用いて犯人を特定したいが，通信をすべて傍受する盗聴者には犯人が分からないようにしたい．この問題は Beaver らによって提案され，彼らによって組合せ論的解法が示された．彼らの手法は盗聴者が犯人を一意に特定できないことを安全性の根拠としているため，犯人の候補が二人まで絞れても安全であると考えており，仮に犯人がどちらか全く分からなくても，確率 1/2 で犯人を特定出来る．そこで本稿では，Two Sheriffs Problem の安全性について，Beaver らの定義を含む一般的な定式化を与え，より攻撃成功確率が小さいプロトコルを提案する．Beaver らは犯人がただ一人であることを仮定しているが，提案プロトコルは複数の犯人でも実行できるプロトコルに拡張されており，攻撃成功確率と容疑者のリストのサイズとのトレードオフがあることを明らかにする．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌情報: コンピュータセキュリティシンポジウム2022論文集; p. 1254-1261, 発行日 2022-10-17
• 出版者 / 言語: ja
• 出版者: 情報処理学会