ゼロ知識証明CL署名2

CL署名の特徴は、コミットメントに署名することができるところである。実際の値を明かす代わりに、コミットメントを署名者に明かして、署名を作成し、そして、署名の要求者が元の値の署名として使えるようにする。コミットメントについては、Wikipediaのビットコミットメントの項目が参考になる。
コミットメントは、嘘をつかないように、事前にその証拠を伝えることである。ゼロ知識証明基礎2で述べた$a$がコミットメントに当たる。ランダム値である$b$が検証者から証明者に伝えられる前に、$a$をコミットをしておくことで、$c$を応答することが証明になるようになっている。$b$を検証者から証明者に伝えた後で、$a$と$c$を伝えるのであれば、容易にインチキができる。 CL署名では、Damgård Fujisakiのコミットメントを使う。

ゼロ知識証明CL署名1

ゼロ知識証明の基礎を説明した。基礎でできることは、$y=g^x$を満たす$x$の値を伝えずに、$x$を知っていることを証明する、ということにすぎない。この証明が何の役に立つのか、が疑問になるだろう。実際のところ、役に立つようにするには、工夫が必要になる。その工夫の一つは、CL署名スキームである。これは、「私は署名を持っている」というようなステートメントを証明し、コミットされた値に対する署名を作成するための署名スキームである。なお、日本語で書かれているページでは、Ontologyテクニカルホワイトペーパーが参考になる。

CL署名の基本スキームは、鍵生成とメッセージ空間、署名アルゴリズム、検証アルゴリズムの4つから成り立つ。まず、それを述べる。

鍵生成

$p=2p'+1, q=2q'+1$で$p$, $q$, $p'$, $q'$が素数であるものを算出する。そして、$n=pq$を計算する(長さは$l_n$)。さらに、乱数$a$, $b$, $c$を生成する。そして、公開鍵$PK=(n, a, b, c)$、秘密鍵$SK=p$とする。
※なお、$p$, $q$は安全素数と呼ばれる。 ※$a, b, c \in QR_n$(平方剰余の集合)に限定。$QR_n \subseteq {\mathbb{Z}_n}^*$、${\mathbb{Z}_n}^*$は、{1, 2, ..., n-1}を意味する。$b^2 \equiv a \bmod n$を満たす$\exists b \in {\mathbb{Z}_n}^*$を満たす$a \in {\mathbb{Z}_n}^*$。

メッセージ空間

メッセージ空間$m$は長さ$l_m$のバイナリストリングである。つまり、0以上$2^{l_m}$未満の値であるということ。

署名アルゴリズム

$e > 2^{l_m+1}$で長さ$l_e=l_m+2$を満たす素数$e$を算出する。また、長さが$l_s=l_n+l_m+l$であるランダム数$s$を生成する。$l$はセキュリティパラメータである。そして、以下を満たす$v$を計算する。 \begin{align} v^e \equiv a^mb^sc \bmod n \end{align}

検証アルゴリズム

$(e, s, v)$がメッセージ$m$の署名である。そして、$v^e \equiv a^mb^sc \bmod n$と$2^{l_c} > e > 2^{l_c}-1$をチェックする。

なぜ、これで検証ができているのか、それを次に説明する。

ゼロ知識証明基礎3

ゼロ知識証明2では、攻撃の成功確率1/2で証明することができ、繰り返すことで0に近づけることが可能になる方法を説明した。これについては、繰り返しを減らす方法やさらになくす方法も提案されている。

減らすには、検証者が$b$を0以上$q$未満の値からランダムに選択して証明者に伝え、証明者は$c=r+bx \bmod q$を計算して検証者に返答する方法がある。このようにおいても、$g^c=ay^b$は成り立つ。これは1度で、攻撃の成功確率$1/q$で証明することができる。

なくす方法では、ハッシュ関数を使う。$p$, $q$, $g$, $y$, $a$を連結したものから証明者はハッシュを計算。さらにハッシュ値を$b$として、証明者は$c=r+bx \bmod q$を計算して、$a$, $b$, $c$を検証者に伝える。検証者は、同様の検証を行う。これにより、やはり、攻撃の成功確率$1/q$で証明することができる。

ゼロ知識証明基礎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$の値も引き算で出せてしまう。

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

ゼロ知識証明基礎1

ビットコインからブロックチェーンが流行り、その状況でセキュリティ業界でホットになっている暗号技術がゼロ知識証明である。ゼロ知識証明は、情報そのものを伝えずに、その情報を知っていることを、証明する方法である。与える情報がゼロ、つまりゼロ知識、ということ。で、そんなことできるわけない。なので、本当に何も伝えないわけではなく、情報を加工したものを伝えて、加工前の情報に戻すことが難しいだけ。それを数学的に実現する。しかし、数学をきっちり勉強してこなかったエンジニアにはなかなか理解しがたい。わかりやすく書かれているのは、「情報セキュリティ大学院大学公開講座『暗号入門７講』ゼロ知識証明入門」だと思うが、これでも難しい。でも、もっとわかりやすく、となると、Wikipediaのゼロ知識証明の項目にあるように、洞窟の比喩などになってしまう。比喩を考えるのは楽しいかもしれないが、本当に理解しようと思っている人の助けにはまったくならない。他の人の理解になればと、僕の理解を明日から書いていく。 きっちり本を読んで理解したいのなら、以下の本が役立つ。

ブログ再開

前は突然やる気がなくなったのか、記事の書きかけが下書きとして残ったままやめたようだ。新たにブログを開設するか迷ったが再開することにする。しかし、もう競馬ソフトは作ってないので、その話題は終わりだ。5年も経ってるしな。何となく記憶を思い起こして見ると、結局、ある程度調整しても利益が出るようにならなくて、考え方が間違ってるわ、と思ってやめた気がする。