証明者と検証者がいるとする。証明者は、y=g^xを満たすxを知っていて、検証者にxそのものを伝えずに、xを知っていることを伝えたいとする。それを証明するには、以下のプロトコルを実行する。
[証明者]
1. rをランダムで生成する。
2. a = g^r を計算する。
3. y, a, gを検証者に伝える。
[検証者]
4. y, a, gを証明者から受け取る。
5. 0か1をランダムに選択する(その値をbとする)。
6. bを証明者に伝える。
[証明者]
7. 検証者からbを受け取る。
8. c=r+bxを計算する。
9. cを検証者に伝える。
[検証者]
10. cを証明者から受け取る。
11. g^c=ay^bあることを検証する。
12. 1.に戻って繰り返す(繰り返し回数が多いほどxを知っていることをより確信する。)
11.の式について説明する。
y, a, gは4.、cは10.で受け取っている。そして、bは自身が生成したので、計算が可能であることがわかる。そして、
g^c = g^{r+bx} = g^r \times g^{bx} = a \times g^{b^x} = a \times g^{x^b} = a \times y^b = ay^b
なので、この式が正しいことはわかる。
でも、これを読んでも、なるほど、とは思わないだろう。どうしてこれで証明したことになるのか。
まず、yとgの値がわかっていれば、xが求められるのではないか、という疑問。これは、その通りである。単純な式y=g^xであれば、簡単にxが計算できる。上記は、省略して書いたが、本当は、離散対数問題というのを扱う。y=g^x mod pのように全てのg^aの形になっているところをg^a mod p(pは非常に大きな素数)という形に置き換える。modは"余り"を計算する記号である。C言語などなら%で表現する。modは面白い特徴を持ち、このように置き換えてもそのまま計算式が成り立つのだ。そして、yからxを求めるのは計算量的に困難になる。なので、暗号学的にはyからxを求めることはできないということ、yを伝えてもxの知識を伝えていないこと(ゼロ知識)にする。
次の疑問は、xをなぜ知っていることが証明できているのか、である。では、証明者がxを知らない場合にどうなるかを考えてみる。xを知らないということはy=g^xは計算できないので、ランダムな数値にすることになる。さらに、c=r+bxも計算できないので、ランダムな数値にすることになる。すると、11.の式の左辺のcと右辺のyが対応する値が入らないことになるので、この式は等しくならないことになる。
その次の疑問は、そんなこと言っても、対応するようなxを作れるのではないか、ということだ。実は、bの値として0か1のどちらが応答されるのかが、わかっていれば、インチキできる。
bが0であるとわかっている場合
c=rである。したがって、11.の式の左辺はg^rで、右辺はaである。つまり、2.で正しく、a=g^rを計算して、その値を3.で渡していれば騙すことができる。
bが1であるとわかっている場合しかし、知らなかった場合はどうなるだろうか。
c=r+xである。が、xは知らないので、cは計算できない。しかし、11.の式を満たすcを伝えればいい。bが1とすると、11.の式の右辺はay^b = ayになる。したがって、2.の式でaを計算するときに、a=g^rを計算する代わりに、a=g^c / yを計算すればよい。cはランダム値で構わない。これにより、11.の式を満たすことが可能である。
a=g^rにしている場合にbが1だったら
c=r+xが計算できないので11.の式を満たすcを送れない。
a=g^c/yにしている場合にbが0だったらつまり、bが0か1かの予想が当たった場合はインチキができてしまうので、このbを送ってcを受け取る処理を繰り返す必要がある。繰り返すことで、インチキができる可能性が1/2になっていく。
今度は、a=g^rを満たすrを求めることができないために、11.の式を満たすc=rを送ることができない。
なお、0と1の両方を同時に与えることはできない。c=r+bxであるから、0の時はc=rでrの値がわかり、1の時はc=r+xでr+xの値がわかる。その結果、xの値も引き算で出せてしまう。
以下の本でもゼロ知識証明についての触れられている。暗号技術についてわかりやすく書かれた本なので、ゼロ知識に限らず幅広く知りたい場合はお勧めできる。
0 件のコメント:
コメントを投稿