たまには古い話を。そして学問は、役に立つと言われていたものが何の役にも立たなかったりその逆があったりして研究の価値は後代にならないとわからないものですよねという教訓も。
「知っているという事実」を内容は告げずに証明する
いかがわしい話ですが「情報商材」ってありますね。大儲けできるお得な情報、○○万円っての。インチキでないか心配だから買う前に内容を知りたいけど、売る側は買ってもらう前に内容を知られるわけにはいかない。内容を伝えることなく、知識が正しいことだけを証明できないか、なんて課題は情報商材みたいなインチキ商売に限らずいたるところにあります。
代表的なのがパスワード認証です。パスワードは相手に教えずに、正しいパスワードを知っているということだけを証明できないか。これをやろうという手法がゼロ知識証明(ZKP: Zero-Knowledge Proof)です。実際に実現された方式では証明者と質問者が複数回のやりとりをするのでゼロ知識対話証明（ZKIP:Zero-Knowledge Interactive Proof)とも呼ばれます。
問題の正解を知っていること
ZKIPが対象とするのは、ある種の問題の正解を知っていることの証明です。
どういう問題かというと
- 作問は容易で、作問者には正解がわかる
- 正解を知っていれば答合わせも容易
- 力任せに解くのは計算量が爆発するため事実上不可能
なもの。なるほど、問題を公開情報、正解を秘密のパスワードのように扱う枠組みです。
そういう問題の中で
- 別の形の問題への変形が容易で、正解を知っていれば変形した問題の正解もわかる
- 変形した問題と元の問題を見比べても変形規則は容易にはわからない
- 変形した問題の正解がわかっても変形規則を知らないことには元の問題の正解はわからない
まで満たすとZKIPが可能になります。
2択を迫る
質問者は証明者にこう聞きます
「問題をランダムに変形して、変形した問題を教えてくれ」
そして変形後の問題を見て、次のどちらかを質問するのです
- 「変形規則を教えてくれ」
- 「変形した問題の正解を教えてくれ」
両方聞いてはいけません。両方教えてもらったら元の正解がわかってしまいます。
証明者はどちらを聞かれてももちろん答えられますし、質問者は
- 「ああ、たしかにこの変形規則でこう変形されるね」
- 「ああ、たしかにこれは変形した問題の正解だね」
と検証できます。
もし証明者が本当は正解を知らないとしたらどうでしょう。
- ランダムな問題をその場ででっち上げて教えたのなら「変形した問題の正解」は答えられます。しかし変形規則を答えられません。
- 変形規則を作って元の問題を変形したのなら変形規則は答えられますが、「変形した問題の正解」は答えられません。
正解を知らない証明者は、質問者を騙そうとしたら2択にヤマを張る必要があるのです。1/2で失敗してしまう証明ならば、10回やれば千分の一、40回やれば一兆分の一の成功率になり、これは強力な証明となるわけです。
そんな都合の良い問題あるの？
そんな都合の良い問題、あるんです。NP完全問題がすべてそうです。中でもよく例に示されるのがハミルトン閉路問題。点がたくさんとそれらを結ぶ線がたくさんあるから、その中からループになっているところを見つけなさいという問題。条件に合っていることを確認してみてください。
で、どうしてこれが古い技術なの？
実際これがあるCATVのセットトップボックスで認証に使われていたという話は聞いたことがあるのですが、今となってはまったく耳にしなくなりました。明確に役に立ちそうな目的があって研究された技術なのに使われていないんですね。
だってそうなりますよ、パスワードを平文で流したくないだけならチャレンジ文字列加えてハッシュ化するという手順で十分なんですもの…。いや、それどころかSSLで安全な通信路を確立して平文送信、こちらが本命ですか。サーバ側がパスワードを平文で保持しなくてよくなるので。