ゼロ知識証明
ゼロ知識証明は次の3条件を満たしていないといけない。
完全性(completeness): 真であることを確認する側(検証者)は、証明する側(証明者)の持っている命題が真であるならば、真であることが必ずわかること。
健全性(soundness): 証明者の持つ命題が偽であるなら、検証者は高い確率でそれが偽であると見抜けること。
ゼロ知識性(zero-knowledge): 証明者の持つ命題が真であるなら、検証者が不正して証明者から知識を盗もうとしても「命題が真である」以外の何の知識も得られないこと。このゼロ知識性は、どんな検証者(知識を持たない)であっても、正しい証明者と対話したかのような対話記録を生成できることだと記述することもできる。
前二者の性質は、ゼロ知識証明に限らず対話型証明システムに共通のものである。最後の性質があってはじめてゼロ知識証明となる。
なお健全性よりも強い知識健全性(knowledge soundness)とよばれる性質が用いられる場合もあり、この性質は「検証者が証明を受理したならば、証明者にオラクルアクセスすることで高確率で命題に対応する証拠を抽出できる(つまり証明者の秘密を取り出せる)効率的なアルゴリズムが存在する」ことを保証する。健全性を知識健全性に置き換えた場合は知識のゼロ知識証明(zero-knowledge proof of knowledge)と呼ばれる。