Journal Articles
-
時間ドロボー問題に対する健全性誤りのない物理的ゼロ知識証明
- Author(s)
- 初貝 恭祐, 安部 芳紀, 中井 雄士, 品川 和雅, 渡邉 洋平, 岩本 貢
- Journal
- 電子情報通信学会 論文誌 A
- Vol.
- J107-A
- No.
- 11
- Publisher
- 電子情報通信学会和文論文誌A
- Publication Year
- 2024
To appear.概要
時間ドロボー問題とは，各面がn色のいずれかで塗られたn個のキューブが与えられ，それらを一列に積み上げて各側面にn色を揃えるパズルである．2013 年に上田と西村は時間ドロボー問題に対するカードを用いたゼロ知識証明プロトコルを提案した．このプロトコルは，時間ドロボー問題の解答（キューブの積み上げ方）を知る証明者が，解答を公開せずに解答が存在することを検証者に納得させるプロトコルである．しかし，彼らのプロトコルは，問題となるキューブが差し替えられてないことと解答が存在することをそれぞれ1/2の確率で検証するため，健全性誤りが1/2の確率で生じる問題がある．本研究では，上田と西村のプロトコルを改良し，健全性誤り確率0を実現するプロトコルを提案する．提案プロトコルでは，問題となるキューブが差し替えられてないことと解答が存在することの検証を同時に行うために2つの同時検証から生じる情報漏洩を防ぐため，キューブの構造を保持しつつカード列をランダム化する立方体シャッフルを新たに導入する．