ゼロ知識証明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$をチェックする。

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