ゼロ知識証明基礎2

ゼロ知識証明の基本は対話型である。前回も述べた暗号入門7講から私の理解を説明する。

証明者と検証者がいるとする。証明者は、$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だったら
今度は、$a=g^r$を満たす$r$を求めることができないために、11.の式を満たす$c=r$を送ることができない。

つまり、bが0か1かの予想が当たった場合はインチキができてしまうので、この$b$を送って$c$を受け取る処理を繰り返す必要がある。繰り返すことで、インチキができる可能性が1/2になっていく。

なお、0と1の両方を同時に与えることはできない。$c=r+bx$であるから、0の時は$c=r$で$r$の値がわかり、1の時は$c=r+x$で$r+x$の値がわかる。その結果、$x$の値も引き算で出せてしまう。

以下の本でもゼロ知識証明についての触れられている。暗号技術についてわかりやすく書かれた本なので、ゼロ知識に限らず幅広く知りたい場合はお勧めできる。