Proof of knowledge とは

暗号では、知識の証拠は、証明者が何かを知っている検証者に「確信する」ことに成功するという対話的証明である。機械が「何かを知る」ことが意味することは、計算の観点から定義されます。機械が入力として与えられると、何かを計算することができれば、機械は「何かを知っている」。証明者のプログラムが必ずしも知識自体を吐き出すわけではないので(ゼロ知識証明の場合のように)、知識抽出プログラムと呼ばれる異なるプログラムを持つマシンが導入され、このアイデアを捕捉する。私たちは、多項式の時間限定機械によって証明できるものに大部分興味を持っています。この場合、一連の知識要素は、NPのある言語の目撃者の集合に限定される。
x {\displaystyle x} をNPの言語 L {\displaystyle L} の言語要素とし、 W ( x ) {\displaystyle W(x)} xの証人を受け入れなければならない証拠とする。これは、以下の関係を定義することを可能にする: R = { ( x , w ) : x L , w W ( x ) } {\displaystyle R=\{(x,w):x\in L,w\in W(x)\}}
知識エラー κ {\displaystyle \kappa } を伴う関係 R {\displaystyle R} に関する知識の証拠は、証明者 P {\displaystyle P} と検証者 V {\displaystyle V} との2者プロトコルであり、以下の2つの特性を有する。
 完全性: ( x , w ) R {\displaystyle (x,w)\in R} ならば、証人 w {\displaystyle w} を知っている証明者Pは、検証者 V {\displaystyle V} に彼の知識を納得させることに成功する。より正式に:妥当性:妥当性は、潜在的に悪意のある証明者 P ~ {\displaystyle {\tilde {P}}} へのオラクルアクセスを与えられた証人を抽出する知識抽出者 E {\displaystyle E} の成功確率が、少なくとも証明者に納得させるための証明者 P ~ {\displaystyle {\tilde {P}}} 。このプロパティは、証人を知らない証明者が検証者を納得させることができないことを保証します。