一様ランダムな不動点のない置換を生成する新しいプロトコル

• Item type: Symposium(1)
• 公開日: 2020-10-19
• タイトル: 一様ランダムな不動点のない置換を生成する新しいプロトコル
• タイトル / 言語: en
• タイトル: A New Protocol for Generating a Uniformly Distributed Random Permutation without Fixed Points
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: カードベース暗号，不動点のない置換，プレゼント交換
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科/産業技術総合研究所
• 著者所属: 東北大学サイバーサイエンスセンター
• 著者所属: 東北大学サイバーサイエンスセンター
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University/AIST
• 著者所属(英): en
• 著者所属(英): Cyberscience Center, Tohoku University
• 著者所属(英): en
• 著者所属(英): Cyberscience Center, Tohoku University
• 著者名: 村田, 総馬; 宮原, 大輝; 水木, 敬明; 曽根, 秀昭
• 著者名(英): Soma, Murata; Daiki, Miyahara; Takaaki, Mizuki; Hideaki, Sone
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: プレゼント交換をn人のプレイヤーで行う場面を考えよう．各プレイヤーは（自分以外の）誰にプレゼントを贈れば良いかだけを事前に知りたい．すなわち，一様ランダムな不動点を持たない置換を秘匿した状態で生成したい．この問題に対する物理的なカード組を用いた解決方法として，最も実用的なプロトコルは2015年にIshikawaらが提案したものである．そのプロトコルでは，各プレイヤーに対応したn個のカード束を用意し，それらの束をシャッフルし，不動点の有無を確認した後，不動点が存在しなければそのままn個のカード束を出力とし，存在すればシャッフル操作からやり直す．本稿では，この既存手法を基に，シャッフル操作をやり直す確率を低くする手法を考える．具体的には，プレイヤー数nより大きい数のカード束を用意することで，不動点が存在してもその不動点を除去することでシャッフルのやり直しを防ぐアイデアを導入する．このようにして得られる提案プロトコルは，不動点を持たない置換を一様ランダムに生成し，追加するカード束の数tの値を大きくすることでシャッフル操作をやり直す確率が改善される．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider the situation where n players exchange gifts. Each player only wants to know in advance who (other than himself/herself) he/she should give a gift. That is, they want to uniformly generate a hidden random permutation without fixed points. In the practical protocol proposed by Ishikawa et al. in 2015, players prepare n piles of physical cards, each of which corresponds to a player, and shuffle the piles. Then, the players verify whether or not the resulting piles have fixed points, and if they have no fixed point, the players output them; otherwise, the players restart the shuffle process. In this paper, based on their protocol, we consider how to decrease the probability of restarting. That is, we introduce an idea of preparing piles of cards more than the number of n players, and removing fixed points if there are fixed points to prevent repeating the shuffle again.
• 書誌情報: コンピュータセキュリティシンポジウム2020論文集; p. 1267-1274, 発行日 2020-10-19
• 出版者 / 言語: ja
• 出版者: 情報処理学会