ゼロ知識証明
ゼロ知識証明の研究は、ある人が,秘密の知識(パスワードなど)を所持していることをもって,本人であることを他の人に示したいが,この秘密自体は誰にも開示しなくてよい認証方式を実現することが動機である。もっとも、パスワード認証というのはゼロ知識証明で扱う一般的な例ではない。ゼロ知識証明によるパスワード認証は特殊な応用例である。
ゼロ知識証明で証明される命題には、巨大な合成数の素因子(素因数分解の解)を知っている、離散対数問題(DLP)の解を知っているなどの公開鍵暗号でよく利用されるものがある。また、任意のNP完全問題の証拠を持っていることをゼロ知識証明で示せることが知られている。
ゼロ知識証明の応用例には、公開鍵暗号、デジタル署名、ユーザ認証などがある。その他、マルチパーティ計算への適用など多くの応用がある。例えば、個人情報を用いてユーザ認証を行う場合、ユーザはゼロ知識証明のプロトコルに従い、個人情報を入力する。
GoldreichとOrenの研究により、ゼロ知識証明を対話をせずに実行すること、すなわち、証明したい人が「証明」を作成して一方的に送りつけるだけで完了するような証明は作れないことが示されている。 しかし特殊な条件下では、対話が不要なゼロ知識証明が作れることが知られており、非対話ゼロ知識証明(non-interactive zero-knowledge proof; NIZK) と呼ばれている。NIZKの実用的な応用としては、デジタル署名や、プライバシーに配慮した暗号通貨がある。後者では、コインの取引者のアドレスや取引量などを隠したまま、取引が正当であることを証明するのにNIZKが利用できる。