幾何学的なパズルに対する物理的ゼロ知識証明
Kyosuke Hatsugai
Abstract
ゼロ知識証明は,ある問題の解答を知る証明者が,解答そのものを教えることなく,問題に解答が存在することを検証者に納得させるプロトコルである.また,カードベース暗号は,計算機の代わりにカードや封筒といった物理的な道具を用いて秘密計算を実現する暗号プロトコルである.カードベース暗号ではゼロ知識証明を実現するプロトコルも考案されており,これらは特に物理的ゼロ知識証明と呼ばれている. 物理的ゼロ知識証明が考案されたパズルの個数について,数値が条件に含まれるパズルに比べて図形の性質が問題や解答の条件に含まれるパズルは少ない.そこで,本研究では幾何学的な特徴を持つパズルを対象に物理的ゼロ知識証明を提案する. 本研究では,二次元図形と三次元図形の双方で幾何学的な特徴をカードで表現するために,時間ロボー問題に対する物理的ゼロ知識証明の改良を行い,天体ショーに対する物理的ゼロ知識証明を新たに提案した.時間ドロボー問題はn個のキューブで構成されたパズルである.先行研究である上田・西村のプロトコルはカードのみで実装できるが,証明者が解答を知らなくても検証者が証明に納得する健全性誤りが生じる問題がある.卒業研究では,カードの他にハサミと立方体を用いることで健全性誤りのないプロトコルを考案した.そこで本研究では,上田・西村の設定と同じくカードのみで実装でき,かつ健全性誤りのないプロトコルを提案する.天体ショーは与えられたブロックを点対称な図形に分割するパズルである.天体ショーに対する物理的ゼロ知識証明では,時間ドロボー問題に対する研究で考案した,立方体を削減する操作を利用することで,解答である分割後の図形の形状を検証者に教えることなく,各図形が点対称であることを証明する.