離散対数の不一致を証明するゼロ知識証明
はじめに
本記事を読むために必要な知識：ゼロ知識証明の基礎
本記事では、『離散対数の不一致を証明するゼロ知識証明』[3]についてのべる。
『離散対数の不一致を証明するゼロ知識証明』とは、離散多数が一致しないことの、ゼロ知識証明である。
『離散対数の不一致を証明するゼロ知識証明』は次の式を証明する。
$g\in \mathbb{G}$、 $s, t \in \mathbb{Z}_p$、$h = g^t$のとき、
（$\mathbb{G}$は巡回群。$g$は生成元。）
\begin{equation} PK\{(s): g^s \neq h\} \end{equation}
を『離散対数の不一致を証明するゼロ知識証明』と呼ぶ。
ユースケース： ブラックリスト
このようなゼロ知識証明は、署名ベースのブラックリスト[2]に用いられる。署名ベースのブラックリスト（signature based revocation）とは、特定の署名をブラックリストに置くことで、その署名者（i.e., 署名者の持つ秘密鍵）を失効する方式である。このような失効方法は、匿名認証など署名者を特定できない場合などに、有効なである。例えば、匿名認証方式の一つであるEPID[2]ではこのような失効能力を持つ。これによりEPIDでは署名者の匿名性を担保したまま、署名者を失効することができる。
署名ベースのブラックリストでは、ブラックリストに登録されていないことをゼロ知識証明する。つまり過去に秘密鍵を用いて生成した署名が、ブラックリストに追加されてないことを証明する。具体的には以下の表の値のもと、次の式を証明する。
\begin{equation} PK\{(s): {\delta}^{s} = \sigma \land {\delta_1'}^{s_1'} \neq \sigma_1' \land \cdots \land {\delta_R'} ^{s_R'} \neq \sigma'_R \} \end{equation}
| 表記 | 式 | 意味 |
|---|---|---|
| $s$ | $s \xleftarrow{\$} \mathbb{Z}_p$ | 署名者の持つ秘密鍵 |
| $R$ | - | 失効リストの長さ |
| $s'_i$ | - | $i$番目に失効された秘密鍵 |
| $\delta$ | $\delta \xleftarrow{\$} \mathbb{G}$ | 署名の一部。ランダムに生成される。 |
| $\delta'_i$ | $\delta'_i \xleftarrow{\$} \mathbb{G}$ | $i$番目に失効された署名の一部。ランダムに生成される。 |
| $\sigma$ | $\sigma = \delta ^ s$ | 署名の一部。$s$と$\delta$から生成される。 |
| $\sigma'_i$ | $\sigma'_i = \delta_i'^{s_i'}$ | $i$番目に失効された署名の一部。ランダムに生成される。 |
前提知識：２つの離散対数に対するゼロ知識証明
前提知識として、『２つの離散対数に対するゼロ知識証明』[1]について紹介する。
$c, g, h \in \mathbb{G}$、 $s, t \in \mathbb{Z}_p$のとき、
（$\mathbb{G}$は巡回群。$c, g, h$は $\mathbb{G}$ の元。）
\begin{equation} PK\{(a, b): c = g^a h^b \} \end{equation}
を『離散対数の不一致を証明するゼロ知識証明』と呼ぶ。
このゼロ知識証明は効率的かつ、よく知られたゼロ知識証明方式である。
なおこのゼロ知識証明の詳細については、本稿では説明しない。
詳細は[1]を参照してほしい。
離散対数の不一致を証明するゼロ知識証明
『離散対数の不一致を証明するゼロ知識証明』の手続きについてのべる。
前提
『離散対数の不一致を証明するゼロ知識証明』を説明する上で、以下の表記を扱う。
| 表記 | 式 | 意味 |
|---|---|---|
| $s$ | $s \in \mathbb{Z}_p$ | 離散対数1。証明者が保有。 |
| $t$ | $t \in \mathbb{Z}_p$ | 離散対数2。証明者が保有しない。 |
| $g$ | $g \in \mathbb{G}$ | 生成元1。公開情報。 |
| $h$ | $t \in \mathbb{G}$ | 生成元2。公開情報。 |
| $y$ | $y = g^s$ | 累乗した値1。公開情報。 |
| $z$ | $z = h^t$ | 累乗した値2。公開情報。 |
| $\beta$ | $\beta \xleftarrow{\$} \mathbb{Z}_p$ | ラップする値。乱数。 |
| $\alpha$ | $\alpha = \beta \cdot s$ | ラップする値。 |
| $C'$ | $C' = (h ^ s / z)$ | $C = 1$なら離散対数が一致するといえる値。 |
| $C$ | $C = C ^\beta = (h ^ s / z) ^ \beta$ | $C = 1$なら離散対数が一致するといえる値。$C'$をラップしている。 |
証明
証明者は以下の手順で検証者に、『離散対数の不一致を証明するゼロ知識証明』を証明する。
証明者はランダムに$\beta \xleftarrow{\$} \mathbb{Z}_p$を選ぶ。
証明者は$\alpha = s \cdot \beta$をそ計算する。
証明者は$C = (h ^ s / z) ^ \beta$ ※を計算し、検証者に送信する。
証明者は以下のゼロ知識証明を検証者に証明する。
$$PK\{(a, b): C = h^\alpha (\frac{1}{z})^\beta \land 1 = g^a (\frac{1}{y})^b\}$$
※$\displaystyle C = (h ^ s / z) ^ \beta = (h ^ {s \cdot \beta} / z^{\beta})= h^\alpha (\frac{1}{z})^\beta $
検証
検証者は以下の手順で証明者の、『離散対数の不一致を証明するゼロ知識証明』を検証する。
- 検証者は$C \neq 1$を検証する。
- 検証者はゼロ知識証明を検証する。
すべて検証できれば証明を受理し、検証できなければ証明を棄却する。
仕組み
『離散対数の不一致を証明するゼロ知識証明』は、
主に以下のコンセプトから構成される。
- a. 離散対数が一致しない証明
- 離散対数が一致しなければ、$C' \neq 1$になる$C'$を定義する。
- ２つのステップを実現できれば、離散対数が一致しないことを証明できる
- $C' \neq 1$であること
- $C'$が正しく生成されたこと
- 課題：$C'$を提供するとゼロ知識性が満たせなくなる。
- $C'$が$s$、$z$、$h$から決定的に求められるため。
- b. $C'$をラップした$C'$の提供
- $C'$を乱数$\beta$でラップした$C$を計算する。
- 課題：
- よく知られた＆＆効率的なゼロ知識証明の形になっていない。
- c. Cが正しく計算されていることのゼロ知識証明
- ゼロ知識証明を用いて、$\alpha$と$\beta$を隠しながら、$C$を証明する。
- 『２つの離散対数に対するゼロ知識証明』を利用。
- 課題
- ラップにつかった値が正しいのかわからない
- d. ラップにつかった値の正しさを証明する
- $\alpha$と$\beta$が正しく生成されたことを証明する。
- e. ここまでのゼロ知識証明まとめ
各コンセプトの詳細
a. 離散対数が一致しなければ、必ず$C' \neq 1$になる$C'$の定義
$C' \in \mathbb{G}$が存在し、$C' \neq 1$のとき、
次の式を証明することで離散対数が一致しないと言える。
\begin{equation} C' \cdot z = h^s \end{equation}
また上式を変形し、
\begin{equation} C' = \frac{h^s}{z} \end{equation}
と表現できる。
この$C'$を検証者に送信し、その正当性（上記の式）を証明すれば、
離散対数が一致しないことを証明できる。
課題
上記の式をゼロ知識証明するためには、次のような課題がある。
- $C'$ を提供するとゼロ知識性が満たせなくなる。
- $\displaystyle C' = \frac{h ^ {s}}{z}$ は 秘密鍵$s$を含む決定的な値（i.e., $s, h, z$）によって計算されてしまうため。
- ゼロ知識性を満たすためには、乱数などで$C'$をラップする必要がある。
b. $C'$をラップした$C$の提供
ゼロ知識性を満たすため、$C'$をラップした$C$を計算する。
具体的には、乱数$\beta$を用いて$C'$ラップする。
このようなラップされた値は、以下の計算から$\displaystyle C = (\frac{h ^ {s}}{z})^\beta$ となる.
- $$C = C'^\beta \neq 1$$
- $\beta$で累乗（ラップ）する
- $$C = (\frac{h ^ {s}}{z})^\beta \neq 1$$
- $C'$を展開する
課題
上記の式をゼロ知識証明するためには、次のような課題がある。
- よく知られた＆＆効率的なゼロ知識証明の形になっていない。
- 正直できるのかもわかっていない（著者）
c. $C$が正しく計算されているゼロ知識証明
上の式を式変形することで、『２つの離散対数に対するゼロ知識証明』の形にする。
以下の計算から$\displaystyle C = h ^ \alpha (\frac{1}{z})^\beta$ となる。
- $$C = (\frac{h ^ {s}}{z})^\beta \neq 1$$
- 元の値
- $$C = (h ^ {s} \frac{1}{z})^\beta \neq 1$$
- 左辺の分子と分母を分解する
- $$C = \displaystyle (h ^ {\beta \cdot s}) (\frac{1}{z})^\beta \neq 1$$
- 両辺を$\beta$をそれぞれカッコの中にもってくる
- $$C = \displaystyle h ^ \alpha (\frac{1}{z})^\beta \neq 1$$
- $\alpha = \beta \cdot s$によって、累乗をまとめる
- ２つの離散対数に対するゼロ知識証明と同じ形である。
よって以下のようなゼロ知識証明が導き出される。
$C$が正しく生成されたことのゼロ知識証明は、
これは『２つの離散対数に対するゼロ知識証明』を用いて、
以下のように行われる。
$$PK\{(\alpha, \beta): C = h^\alpha (\frac{1}{z})^\beta\}$$
課題
以下のゼロ知識証明には以下の課題がある。
- ラップにつかった値が正しいのかわからない。
- $\alpha$と$\beta$が正しく計算されているのかわからない。
d. ラップにつかった値の正しさを証明する
ラップにつかった値$\alpha, \beta$の関係が正しいことを証明する。
ここで証明する関係とは、$\alpha = \beta \cdot s$である。
このような証明は、『２つの離散対数に対するゼロ知識証明』を用いて、以下のように行われる。
$\alpha = \beta \cdot s$ のゼロ知識証明は、
$$PK\{(a, b): 1 = g^a (\frac{1}{y})^b\}$$
によってできる。
これは$a = \beta \cdot s$が、以下の式のように$\displaystyle 1 = g^a (\frac{1}{y})^b$に、変形できるためである。
- $a = \beta \cdot s$
- 証明したい関係
- $g^a = g^{b\cdot s}$
- 両辺を対数として累乗する
- $g^a = y^{b}$
- $y = g^s$に置き換える
- $\displaystyle 1 = g^a (\frac{1}{y})^b$
- 両辺を$y^b$で割る
（e. ゼロ知識証明をまとめる）
上記に述べた、ゼロ知識証明をまとめると、以下のようになる。
$$PK\{(\alpha, \beta): C = h^\alpha (\frac{1}{z})^\beta \land 1 = g^a (\frac{1}{y})^b\}$$
まとめ
本記事では、『離散対数の不一致を証明するゼロ知識証明』[3]について紹介した。