7ZD-05
不等号ナンプレに対する物理的ゼロ知識証明
○田中滉大,黒田真那,志摩邑那,水木敬明(東北大)
パズルに対するゼロ知識証明とは,パズルの解を知る証明者がその解についての情報を一切明かすことなく,「解が存在し,証明者が解を知っていること」を検証者に納得させるというものである.中でも,カード組のような物理的な道具を用い,人間の手でゼロ知識証明を実行する物理的ゼロ知識証明は,これまで数独をはじめとする,様々なパズルに対するプロトコルが構築されている.本稿では不等号ナンプレ(Futoshiki,不等式)に対する初の物理的ゼロ知識証明プロトコルを提案する.不等号を満たすように数字をマスに埋めることが不等号ナンプレの特徴的なルールであり,この検証がプロトコル構築のポイントである.