0
応用数学解説
文献あり

離散対数の不一致を証明するゼロ知識証明

165
1
$$$$

はじめに

本記事を読むために必要な知識:ゼロ知識証明の基礎

本記事では、『離散対数の不一致を証明するゼロ知識証明』[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$番目に失効された署名の一部。ランダムに生成される。

前提知識:2つの離散対数に対するゼロ知識証明

前提知識として、『2つの離散対数に対するゼロ知識証明』[1]について紹介する。

2つの離散対数に対するゼロ知識証明

$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'$をラップしている。

証明

証明者は以下の手順で検証者に、『離散対数の不一致を証明するゼロ知識証明』を証明する。

  1. 証明者はランダムに$\beta \xleftarrow{\$} \mathbb{Z}_p$を選ぶ。

  2. 証明者は$\alpha = s \cdot \beta$をそ計算する。

  3. 証明者は$C = (h ^ s / z) ^ \beta$ ※を計算し、検証者に送信する。

  4. 証明者は以下のゼロ知識証明を検証者に証明する。
    $$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'$を定義する。
    • 2つのステップを実現できれば、離散対数が一致しないことを証明できる
      1. $C' \neq 1$であること
      2. $C'$が正しく生成されたこと
    • 課題:$C'$を提供するとゼロ知識性が満たせなくなる。
      • $C'$が$s$、$z$、$h$から決定的に求められるため。
  • b. $C'$をラップした$C'$の提供
    • $C'$を乱数$\beta$でラップした$C$を計算する。
    • 課題:
      • よく知られた&&効率的なゼロ知識証明の形になっていない。
  • c. Cが正しく計算されていることのゼロ知識証明
    • ゼロ知識証明を用いて、$\alpha$と$\beta$を隠しながら、$C$を証明する。
    • 『2つの離散対数に対するゼロ知識証明』を利用。
    • 課題
      • ラップにつかった値が正しいのかわからない
  • d. ラップにつかった値の正しさを証明する
    • $\alpha$と$\beta$が正しく生成されたことを証明する。
  • e. ここまでのゼロ知識証明まとめ

各コンセプトの詳細

a. 離散対数が一致しなければ、必ず$C' \neq 1$になる$C'$の定義

離散対数が一致しなければ、必ず$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'$ラップする。

$C'$のラップ

このようなラップされた値は、以下の計算から$\displaystyle C = (\frac{h ^ {s}}{z})^\beta$ となる.

  1. $$C = C'^\beta \neq 1$$
    • $\beta$で累乗(ラップ)する
  2. $$C = (\frac{h ^ {s}}{z})^\beta \neq 1$$
    • $C'$を展開する
課題

上記の式をゼロ知識証明するためには、次のような課題がある。

  • よく知られた&&効率的なゼロ知識証明の形になっていない。
    • 正直できるのかもわかっていない(著者)

c. $C$が正しく計算されているゼロ知識証明

上の式を式変形することで、『2つの離散対数に対するゼロ知識証明』の形にする。

2つの離散対数に対するゼロ知識証明の形に変形

以下の計算から$\displaystyle C = h ^ \alpha (\frac{1}{z})^\beta$ となる。

  1. $$C = (\frac{h ^ {s}}{z})^\beta \neq 1$$
    • 元の値
  2. $$C = (h ^ {s} \frac{1}{z})^\beta \neq 1$$
    • 左辺の分子と分母を分解する
  3. $$C = \displaystyle (h ^ {\beta \cdot s}) (\frac{1}{z})^\beta \neq 1$$
    • 両辺を$\beta$をそれぞれカッコの中にもってくる
  4. $$C = \displaystyle h ^ \alpha (\frac{1}{z})^\beta \neq 1$$
    • $\alpha = \beta \cdot s$によって、累乗をまとめる
    • 2つの離散対数に対するゼロ知識証明と同じ形である。

よって以下のようなゼロ知識証明が導き出される。

$C$の値に対するゼロ知識証明

$C$が正しく生成されたことのゼロ知識証明は、
これは『2つの離散対数に対するゼロ知識証明』を用いて、
以下のように行われる。

$$PK\{(\alpha, \beta): C = h^\alpha (\frac{1}{z})^\beta\}$$

課題

以下のゼロ知識証明には以下の課題がある。

  • ラップにつかった値が正しいのかわからない。
    • $\alpha$と$\beta$が正しく計算されているのかわからない。

d. ラップにつかった値の正しさを証明する

ラップにつかった値$\alpha, \beta$の関係が正しいことを証明する。
ここで証明する関係とは、$\alpha = \beta \cdot s$である。

このような証明は、『2つの離散対数に対するゼロ知識証明』を用いて、以下のように行われる。

$\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$に、変形できるためである。

  1. $a = \beta \cdot s$
    • 証明したい関係
  2. $g^a = g^{b\cdot s}$
    • 両辺を対数として累乗する
  3. $g^a = y^{b}$
    • $y = g^s$に置き換える
  4. $\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]について紹介した。

参考文献

[1]
Camenisch, Jan, and Victor Shoup., Practical verifiable encryption and decryption of discrete logarithms., Annual International Cryptology Conference. Springer, 2003
[2]
Chaum, David, and Torben Pryds Pedersen., Wallet databases with observers., Annual international cryptology conference. Springer, 1992
[3]
Brickell, Ernie, and Jiangtao Li., Enhanced privacy ID from bilinear pairing, Cryptology ePrint Archive , 2009
投稿日:20221221
更新日:20231211
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

akakou
akakou
16
15969
数学が…わかりません……ダレカタスケテー

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中