暗号応用技術
ゼロ知識証明
ゼロ知識対話証明
1985年にGoldwasser,Micali,Rackoffによりゼロ知識証明の概念が発表された. 証明者 $P$ (Prover)と検証者 $V$ (Verifier) が対話しながら,証明者 $P$
が秘密情報を漏らすことなく,その情報を知っていることを検証者 $V$ に納得させる方式である.
- 対話証明
証明者 $P$ はある命題を検証者 $V$ に証明する.この命題は必ず「Yes」か「No」で答えられるものとする. 例えば,「与えられた地図は3色で塗り分けられる」という命題は「Yes」,「No」で答えられる.
その問題に対話証明が存在するというのを,
- 答えが「Yes」であれば,検証者 $V$ は納得できる(完全性).
- 答えが「No」であれば,検証者 $V$ はそれなりに高い確率で納得しない(健全性).
と定義する.
具体例として,地図の3彩色問題に関する対話証明をあげる.
- 証明者 $P$ は塗り分けられた地図 $M$ を検証者 $V$ に見せる.
- 検証者 $V$ はもらった地図 $M$ を見て,塗り分けられているかどうか確認する.
証拠 $M$ が存在すれば検証者 $V$ は納得できる.また答えが「No」である場合には,塗り分けられた地図 $M$ は存在しないので,検証者 $V$ は必ず納得しない.
どんな地図を与えられても,上のように対話することができる.
- ゼロ知識証明
ゼロ知識証明は,対話証明の部分集合である.
地図の3彩色問題の例では塗り分けられた地図 $M$ を検証者 $V$ に見せていた. これに対し,塗り分けられた地図 $M$ を見せることなく,
- 地図が塗り分けられることを検証者 $V$ に納得させる.
- 塗り分けられた地図 $M$ を持っていることを検証者 $V$ に納得させる.
のがゼロ知識証明である.
地図の3彩色問題に関するゼロ知識対話証明を構成例を示す.
- 証明者 $P$ は地図を塗り分け,塗りわけ方を $w$ とする.例えば赤青黄で塗り分けておく.
- 証明者 $P$ は地図上の領域の上に箱を置き,領域の色が見えないようにする.
次に,白黒灰のカードを用意し,地図を塗り分けた色(赤青黄)にランダムに対応させる.
- 白黒灰のカードを対応する色(赤or青or黄)の領域の箱に入れ,鍵を掛ける.
- $(P \rightarrow V)$ 証明者 $P$ は検証者 $V$ に箱ごと地図を見せる(検証者 $V$ は箱と地図しか見ていないので塗り分け方は分からない).
- $(V \rightarrow P)$ 検証者 $V$ はランダムに "接している領域を2つ" 指定する.
- $(P \rightarrow V)$ 証明者 $P$ はその領域の上に乗っている箱の鍵を開き,中の色(白or黒or灰)を見せる.
- 検証者 $V$ が納得するまで 1.から繰り返す.
この対話では,答えが「Yes」(接している2つの領域の色が異なる)なら検証者は必ず納得する. 一方,答えが「No」であれば,必ず塗り分けられていない場所が存在する. 従って,検証者 V
は1/(境界線の個数) よりは高い確率で塗り分けられていない場所を指定するので,納得しない.これにより,対話証明になっていることが分かる.
また,この対話証明はゼロ知識証明になっている. 検証者 $V$ は毎回,2つの領域しか見ていない.さらに,その塗りわけ方は本来の塗り方ではなく,毎回ランダムに入れ替えられている.
上の対話で検証者 $V$ が得られた知識というのは,
- 検証者 $V$ はランダムに接している領域を2つ選び,それを適当な色で塗り分ける.
と自分で計算して得られる知識と同じである.よって,対話後に増えた知識の量はゼロである. これをゼロ知識性と呼ぶ.
ある対話証明がゼロ知識証明であることを定式化すると,以下のようになる.
- 完全性
証明が正しければ,検証者は1または1に限りなく近い確率(圧倒的確率)で受理する.
- 健全性
証明が誤ってれば,証明者がどのように振舞っても,検証者は圧倒的確率で棄却する.
- ゼロ知識性
証明が正しければ,検証者がどのように振舞っても,証明の正しさ以外の情報は一切分からない.
- ゼロ知識証明の応用
$P$ と $V$ の間の対話を盗聴していても $P$ が持っている知識が漏れないので,認証技術に利用することができる. また,対話が $(P \rightarrow V)$,$(V \rightarrow
P)$,$(P \rightarrow V)$ と3回の場合には,ハッシュ関数を利用して,$(P \rightarrow V)$ と対話の回数を減らすことができる.この場合,ゼロ知識証明を電子署名に利用することができる.
ゼロ知識対話証明の例
- 対話証明の例
与えられた大きな合成数 $n$ と $\bmod n$ での平方剰余に対し,証明者 $P$ が $Z = T^2 \bmod n$ なる $T$ を知っていることを検証者 $V$ に証明する.
$P$ と $V$ の間で以下を $k$ 回繰り返す.
- Step1:
$P$ は乱数 $R$ を選び,$X = R^2 \bmod n$ を計算し $V$ に $X$ を送る.
- Step2:
$V$ は $b \in \{0, 1\}$ をランダムに選び,$b$ を $P$ に送る.
- Step3:
$P$ は次の $Y$ を $V$ に送る.
$b = 0$ の場合 $Y = R$,$b = 1$ の場合 $Y = TR \bmod n$
- Step4:
$V$ は次式が成立するかを検査する.
$b = 0$ の場合 $X = Y^2 \bmod n$,$b = 1$ の場合 $ZX =Y^2 \bmod n$
- 認証への応用例
上記を認証へ応用する例を示す.
ゼロ知識証明を利用するために,信頼できるセンターを設け,センターは2つの素数 $p$, $q$ を用意する.この2つの素数 $p$,$q$ は,センターの秘密情報とする.これらの2つの素数の積を $n =
pq$ とし,$n$ を全ユーザに公開する.
次に,ユーザの $ID$ をセンターに登録する.$ID$ はユーザそれぞれを特定できるもの,例えば電話番号などを $ID$ として考える.ここでユーザ $A$ の $ID$ を $ID_A$
とする.センターは各ユーザから $ID$ を登録されるとその $ID$ の平方根 $\sqrt{ID_A} \bmod n$を計算する.
この $ID$ の平方根がユーザ $A$ の秘密情報 $S_A$ であり,この情報が秘密にユーザ $A$ に配布される.他のユーザに対しても同様である.
ゼロ知識証明を用いて認証を行う手順は次のようになる.
ユーザ $A$ がユーザ $B$ に対して自分が $A$ であることことを証明したいとする.
- ユーザ $A$ は適当な乱数 $R$ を選び,これを2乗して $n$ で割った余り $X = R^2 \bmod n$ をユーザ $B$ に送る.
- ユーザ $B$ は,チャレンジビット $b = 0$ 或いは $b = 1$ をユーザ $A$ に送る.
- ユーザ $A$ は,このチャレンジビットの値に応じて $b = 1$ ならば $Y = S_A R \bmod n$ を,$b = 0$ ならば $Y = R$ をユーザ $B$ に送る.
ここでチャレンジビットを何度もユーザ $A$ に 送ることにより送信者がなりすましでないことを確認することができる.
- ユーザ $B$ は,$b = 1$ のとき,$Y^2 = (S_A R)^2 = ID_A・X \pmod{n}$ より送信者の $ID$ を得ることができ,ユーザ $B$ がユーザ $A$ の $ID$
を認証することが可能となる.
知識の署名 (SPK)
- SPK とは
知識の署名 (SPK: Signature based on a Proof of Knowledge) とは,統計的ゼロ知識証明から導かれる署名であり,ある命題を満たす $α_1, \ldots, α_n$
を知っていることを $α_1, \ldots, α_n$ に関する情報を漏らすことなく証明する方法である. SPK は,任意のメッセージ $m$ に対して作成することができ,これを
$\mathrm{SPK} \{(α_1, \ldots, α_n)\ |\ 命題\} (m)$
で表す.
ある離散対数を知っていることを証明する SPK を示す.
$ε$ を偽造を許す確率を示す定数,
$\mathrm{H}:\{0,1\}^* \rightarrow \{0, 1\}^k$ を汎用一方向性関数とする.
$g$ を生成元とする乗法群を $G$ とし,$g$ の位数を $n$ とする.
$g$ と $y \in G$ に対して,$y = g^x$ となる $x \in \{0, 1\}^{|n|}$ を知っていることをあるメッセージ $m$ に依存して証明する SPK
$\mathrm{SPK} \{(α)\ |\ y = g^α\} (m)$
は,$e = \mathrm{H}(g\ ||\ y\ ||\ g^v y^e\ ||\ m)$ を満たす $(e, v) \in \{0, 1\}^k \times [{-2}^{|n|+k}, 2^{ε(|n|+k)}]$
で与えられる.
正当性証明情報の生成と検証は,以下のようになる.
- 正当性証明情報の生成
証明者は以下に従って $(e, v)$ を求め,検証者に送信する.
- 乱数 $r \in \{0, 1\}^{ε(|n|+k)}$ を生成する.
- $u = g^r$ を計算する.
- $e = \mathrm{H}(g\ ||\ y\ ||\ u\ ||\ m)$ を計算する.
- $v = r - ex$ を計算する.
- 検証処理
検証者は証明者から $(e, v)$ を受信し,以下の処理を行う.
- $u' = g^v y^e$ を計算する.
- $e = \mathrm{H}(g\ ||\ y\ ||\ u'\ ||\ m)$ が成立つか否かを検証し,成立つ場合当該証明事項を受理する.
- SPK の例
SPK の例としては,他に以下のようなものがある.
- $\mathrm{SPK} \{(α)\ |\ y_1 = g^α \land y_2 = g^α\} (m)$
2つの離散対数が一致していることの証明
- $\mathrm{SPK} \{(α,β)\ |\ y_1 = g^α \lor y_2 = h^β\} (m)$
2つの離散対数のどちらかを知っていることの証明
- $\mathrm{SPK} \{(α)\ |\ y = g^α \land α \in A\} (m)$
与えられた範囲 $A$ に含まれる離散対数を知っていることの証明