UNOを用いた数独に対するゼロ知識証明について

• Item type: SIG Technical Reports(1)
• 公開日: 2022-09-08
• タイトル: UNOを用いた数独に対するゼロ知識証明について
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学
• 著者所属: 東北大学
• 著者所属(英): en
• 著者所属(英): Tohoku Uniersity
• 著者所属(英): en
• 著者所属(英): Tohoku Uniersity
• 著者名: 田中, 滉大; 水木, 敬明
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 数独に対するゼロ知識証明とは，数独の解を知る証明者がその解についての情報を一切明かすことなく，「解が存在し，証明者が解を知っていること」を検証者に納得させるというものである．2009 年に Gradwhol らは数独に対する初の物理的なゼロ知識証明プロトコルをカード組を用いて構築した．しかしこのプロトコルは健全性エラーが発生する問題がある．その後 2020 年に Sasaki らは健全性エラーがなく，36 回のシャッフルで実現できる改良型のゼロ知識証明プロトコルを提案した．このプロトコルでは 1 から 9 の数字が書かれた同一カードが 18 セット必要であり，より日常的に用意できる道具を用いることが望ましい．そこで，2022 年に Ruangwises は，標準的なトランプ 2 セットを用いたプロトコルを提案した．しかし，このプロトコルは 322 回のシャッフルが必要であり，実用的に利用するのは難しい．そこで本稿では，日常的に用意可能である UNO を 2 セット用い，新しいプロトコルを構築し，シャッフル回数の削減を実現する．具体的には，16 回のシャッフルで数独に対するゼロ知識証明を実現する．従って，提案プロトコルは前述の Sasaki らのプロトコルよりもシャッフル回数が半分以下で済む，非常に効率的なものである．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-189, 号 5, p. 1-8, 発行日 2022-09-08
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会