対話証明系
対話証明系(interactive proof systems)は、強力な証明者と確率的多項式時間検証者の間の相互作用によって、言語のメンバーシップを検証する計算複雑性理論の重要な概念です。
概要
対話証明系は、NPの概念を拡張したもので、短い証明を持つ言語のクラスとして捉えたNPを、証明者と検証者の間の対話に拡張したものです。
主要なトピック
- 対話証明系の定義: 対話チューリング機械と対話証明系の形式的定義
- ゼロ知識証明: 証明の有効性以外の情報を漏らさない証明系
- グラフ同型性問題: 対話証明系の代表的な例
- NPに対するゼロ知識対話証明: 安全な暗号化関数を用いた一般的な構築
応用分野
- 暗号学
- 計算複雑性理論
- プロトコル設計
- プライバシー保護技術