応用数学解説

文献あり

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

暗号技術,ゼロ知識証明,ブラックリスト

173

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

はじめに

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

本記事では、『離散対数の不一致を証明するゼロ知識証明』[3]についてのべる。
『離散対数の不一致を証明するゼロ知識証明』とは、離散多数が一致しないことの、ゼロ知識証明である。

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

『離散対数の不一致を証明するゼロ知識証明』は次の式を証明する。

$g \in G$ 、 $s, t \in Z_{p}$ 、 $h = g^{t}$ のとき、
（ $G$ は巡回群。 $g$ は生成元。）

$P K {(s) : g^{s} \neq h}$

を『離散対数の不一致を証明するゼロ知識証明』と呼ぶ。

ユースケース：ブラックリスト

このようなゼロ知識証明は、署名ベースのブラックリスト[2]に用いられる。署名ベースのブラックリスト（signature based revocation）とは、特定の署名をブラックリストに置くことで、その署名者（i.e., 署名者の持つ秘密鍵）を失効する方式である。このような失効方法は、匿名認証など署名者を特定できない場合などに、有効なである。例えば、匿名認証方式の一つであるEPID[2]ではこのような失効能力を持つ。これによりEPIDでは署名者の匿名性を担保したまま、署名者を失効することができる。

署名ベースのブラックリストで用いるゼロ知識証明

署名ベースのブラックリストでは、ブラックリストに登録されていないことをゼロ知識証明する。つまり過去に秘密鍵を用いて生成した署名が、ブラックリストに追加されてないことを証明する。具体的には以下の表の値のもと、次の式を証明する。

$P K {(s) : δ^{s} = σ \land {δ_{1}^{'}}^{s_{1}^{'}} \neq σ_{1}^{'} \land \dots \land {δ_{R}^{'}}^{s_{R}^{'}} \neq σ_{R}^{'}}$

表記	式	意味
$s$	$s \overset{$}{\leftarrow} Z_{p}$	署名者の持つ秘密鍵
$R$	-	失効リストの長さ
$s_{i}^{'}$	-	$i$ 番目に失効された秘密鍵
$δ$	$δ \overset{$}{\leftarrow} G$	署名の一部。ランダムに生成される。
$δ_{i}^{'}$	$δ_{i}^{'} \overset{$}{\leftarrow} G$	$i$ 番目に失効された署名の一部。ランダムに生成される。
$σ$	$σ = δ^{s}$	署名の一部。 $s$ と $δ$ から生成される。
$σ_{i}^{'}$	$σ_{i}^{'} = δ_{i}^{' s_{i}^{'}}$	$i$ 番目に失効された署名の一部。ランダムに生成される。

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

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

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

$c, g, h \in G$ 、 $s, t \in Z_{p}$ のとき、
（ $G$ は巡回群。 $c, g, h$ は $G$ の元。）

$P K {(a, b) : c = g^{a} h^{b}}$

を『離散対数の不一致を証明するゼロ知識証明』と呼ぶ。

このゼロ知識証明は効率的かつ、よく知られたゼロ知識証明方式である。
なおこのゼロ知識証明の詳細については、本稿では説明しない。
詳細は[1]を参照してほしい。

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

『離散対数の不一致を証明するゼロ知識証明』の手続きについてのべる。

前提

『離散対数の不一致を証明するゼロ知識証明』を説明する上で、以下の表記を扱う。

表記	式	意味
$s$	$s \in Z_{p}$	離散対数1。証明者が保有。
$t$	$t \in Z_{p}$	離散対数2。証明者が保有しない。
$g$	$g \in G$	生成元1。公開情報。
$h$	$t \in G$	生成元2。公開情報。
$y$	$y = g^{s}$	累乗した値1。公開情報。
$z$	$z = h^{t}$	累乗した値2。公開情報。
$β$	$β \overset{$}{\leftarrow} Z_{p}$	ラップする値。乱数。
$α$	$α = β \cdot s$	ラップする値。
$C^{'}$	$C^{'} = (h^{s} / z)$	$C = 1$ なら離散対数が一致するといえる値。
$C$	$C = C^{β} = (h^{s} / z)^{β}$	$C = 1$ なら離散対数が一致するといえる値。 $C^{'}$ をラップしている。

証明

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

証明者はランダムに $β \overset{$}{\leftarrow} Z_{p}$ を選ぶ。
証明者は $α = s \cdot β$ をそ計算する。
証明者は $C = (h^{s} / z)^{β}$ ※を計算し、検証者に送信する。
証明者は以下のゼロ知識証明を検証者に証明する。
$P K {(a, b) : C = h^{α} (\frac{1}{z})^{β} \land 1 = g^{a} (\frac{1}{y})^{b}}$

※ $C = (h^{s} / z)^{β} = (h^{s \cdot β} / z^{β}) = h^{α} (\frac{1}{z})^{β}$

検証

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

検証者は $C \neq 1$ を検証する。
検証者はゼロ知識証明を検証する。

すべて検証できれば証明を受理し、検証できなければ証明を棄却する。

仕組み

『離散対数の不一致を証明するゼロ知識証明』は、
主に以下のコンセプトから構成される。

a. 離散対数が一致しない証明
- 離散対数が一致しなければ、 $C^{'} \neq 1$ になる $C^{'}$ を定義する。
- ２つのステップを実現できれば、離散対数が一致しないことを証明できる
  1. $C^{'} \neq 1$ であること
  2. $C^{'}$ が正しく生成されたこと
- 課題： $C^{'}$ を提供するとゼロ知識性が満たせなくなる。
  - $C^{'}$ が $s$ 、 $z$ 、 $h$ から決定的に求められるため。
b. $C^{'}$ をラップした $C^{'}$ の提供
- $C^{'}$ を乱数 $β$ でラップした $C$ を計算する。
- 課題：
  - よく知られた＆＆効率的なゼロ知識証明の形になっていない。
c. Cが正しく計算されていることのゼロ知識証明
- ゼロ知識証明を用いて、 $α$ と $β$ を隠しながら、 $C$ を証明する。
- 『２つの離散対数に対するゼロ知識証明』を利用。
- 課題
  - ラップにつかった値が正しいのかわからない
d. ラップにつかった値の正しさを証明する
- $α$ と $β$ が正しく生成されたことを証明する。
e. ここまでのゼロ知識証明まとめ

各コンセプトの詳細

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

離散対数が一致しなければ、必ず

C^{'} \neq 1

になる

C^{'}

$C^{'} \in G$ が存在し、 $C^{'} \neq 1$ のとき、
次の式を証明することで離散対数が一致しないと言える。

$C^{'} \cdot z = h^{s}$

また上式を変形し、

$C^{'} = \frac{h^{s}}{z}$

と表現できる。

この $C^{'}$ を検証者に送信し、その正当性（上記の式）を証明すれば、
離散対数が一致しないことを証明できる。

課題

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

$C^{'}$ を提供するとゼロ知識性が満たせなくなる。
- $C^{'} = \frac{h^{s}}{z}$ は秘密鍵 $s$ を含む決定的な値（i.e., $s, h, z$ ）によって計算されてしまうため。
ゼロ知識性を満たすためには、乱数などで $C^{'}$ をラップする必要がある。

b. $C^{'}$ をラップした $C$ の提供

ゼロ知識性を満たすため、 $C^{'}$ をラップした $C$ を計算する。
具体的には、乱数 $β$ を用いて $C^{'}$ ラップする。

C^{'}

のラップ

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

$C = C^{' β} \neq 1$
- $β$ で累乗（ラップ）する
$C = (\frac{h^{s}}{z})^{β} \neq 1$
- $C^{'}$ を展開する

課題

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

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

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

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

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

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

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

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

C

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

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

$P K {(α, β) : C = h^{α} (\frac{1}{z})^{β}}$

課題

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

ラップにつかった値が正しいのかわからない。
- $α$ と $β$ が正しく計算されているのかわからない。

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

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

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

α = β \cdot s

のゼロ知識証明

$α = β \cdot s$ のゼロ知識証明は、
$P K {(a, b) : 1 = g^{a} (\frac{1}{y})^{b}}$
によってできる。

これは $a = β \cdot s$ が、以下の式のように $1 = g^{a} (\frac{1}{y})^{b}$ に、変形できるためである。

$a = β \cdot s$
- 証明したい関係
$g^{a} = g^{b \cdot s}$
- 両辺を対数として累乗する
$g^{a} = y^{b}$
- $y = g^{s}$ に置き換える
$1 = g^{a} (\frac{1}{y})^{b}$
- 両辺を $y^{b}$ で割る

（e. ゼロ知識証明をまとめる）

まとめたゼロ知識証明

上記に述べた、ゼロ知識証明をまとめると、以下のようになる。

$P K {(α, β) : C = h^{α} (\frac{1}{z})^{β} \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

投稿日：2022年12月21日

更新日：2023年12月11日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

akakou

17319

数学が…わかりません……ﾀﾞﾚｶﾀｽｹﾃｰ

他の人のコメント

コメントはありません。

読み込み中

akakou

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

はじめに
ユースケース：ブラックリスト
前提知識：２つの離散対数に対するゼロ知識証明
離散対数の不一致を証明するゼロ知識証明
前提
証明
検証
仕組み
各コンセプトの詳細
まとめ
参考文献

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

はじめに

ユースケース： ブラックリスト

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

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

前提

証明

検証

仕組み

各コンセプトの詳細

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

課題

b. C′をラップしたCの提供

課題

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

課題

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

（e. ゼロ知識証明をまとめる）

まとめ

参考文献

この記事を高評価した人

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

投稿者

コメント

他の人のコメント

ユースケース：ブラックリスト

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

b. $C^{'}$ をラップした $C$ の提供

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