|
生物学翻訳、学術論文翻訳、環境翻訳担当の平井です｡
暗号プロトコル(cryptographic protocol)では規定の計算が正しく行われたことを、入力を秘密にしたままで証明するという状況がよく現れます。それには証明車と検証者が情報のやり取りを繰り返すことによって、最終的に検証者が命題の正しさを納得する対話証明(interactive proof)という方法を使います。対話はいわゆるチャレンジ-レスポンス型になっていて、命題が正しいなら証明者は検証者が選んだチャレンジに一定の確率で正しく答えられます。対話を繰り返すことで、一度目は偶然、二度目は必然、三度目は…と確信度をどこまでも高められます。
命題が正しいかどうかを知らなくても、対話に「待った」をかけながらシミュレーションすることで実際の対話と識別不可能な対話の記録を作り出せる場合があります。シミュレーションが可能な対話証明をゼロ知識対話証明(zero knowledge interactive proof)と言います。待ったなしで直接対話した検証者は、命題の正しさを納得できますが、やり取りされた情報はシミュレーションと区別できないので、結局、命題が正しいという事実以外には何の情報も得られないことになります。
実用上起こりうるどのような命題に対しても、ゼロ知識対話証明を構成することができますが、1回の証明には少なくとも3回の交信が必要です。対話が納得を生むのは、理論でも現実でも変わりないようです。 |
