統計的ゼロ知識証明の関係について

概要

論文の詳細を見る
1985年にGoldwasser, Micali, Rackoffにより"ゼロ知識対話証明" (zero-knowledge interactive proof) という概念が示された. これは, "ゼロ知識"という概念と"対話証明"という概念の複合であり, いずれも彼らにより初めて示されたものである. "対話証明"とは, 確率 (さいころをふる) と対話 (質疑応答を繰り返す) を導入することにより (確定的で非対話的な) 従来の計算量のクラスを自然に拡張したものと考えることができる. また, "ゼロ知識"は, 暗号 (プロトコル) の要請から導入されたものであり, ある情報を隠してある目的を実行したいという暗号の世界における自然な要求からきている. 例えば, 自分の秘密情報 (パスワード) を隠して, その秘密を持っていることを示したいなどという要求に答えるものである. "ゼロ知識対話証明"では, ある情報 (入力) がある性質を持っているという1ビットの情報 (ある言語に属すという情報) をそれ以外の余分な情報を一切漏らさずに対話的に証明する. 例えば, あるグラフが入力として与えられたとき, そのグラフがハミルトン閉路を持つということのみ (1ビットの情報) を (証明者は検証者に) 対話的に証明するが, ハミルトン閉路がそのグラフのどこにあるかについては一切漏らさない. ゼロ知識対話証明が提案されて以降, 理論的に最も大きな問題の一つはどのような言語に対してゼロ知識対話証明が存在するかを明らかにすることであった. この問題に関しては, 計算量的ゼロ知識対話証明については, 1987年頃までにほとんど解決されたが, 統計的ゼロ知識対話証明 (さらに完全ゼロ知識証明) については, 1987年頃までにいくつかの問題が解かれたものの, 多くの重要な問題が未解決のまま最近まで残されていた. 1996年, 著者はこのうちのいくつかの未解決問題を解決した. 本稿では, 最初に, ゼロ知識対話証明の概念を簡単に述べた後, 上記の結果について説明する.
社団法人電子情報通信学会の論文
1997-03-06

統計的ゼロ知識証明の関係について

スポンサーリンク

概要

著者

関連論文

スポンサーリンク