ZKAttest: 具体的なプロトコルについて

Table of Contents

はじめに

この記事では前回の記事 [12] に続いてECDSA署名を行うシグマプロトコルであるZKAttest([1]ZKAttest: Ring and Group Signatures for Existing ECDSA Keys)について解説します。

楕円曲線とその群

楕円曲線とは $y^2=x^3+ax+b$ と表される曲線のことです。
楕円曲線上の点は楕円加算と呼ばれる加算によって体を成します。

楕円加算。[7]より引用。

楕円加算の図。[7]より引用。

ZKAttestではまず素数

p

の剰余体

\mathbb{F}_p

上で定義される標準的な楕円曲線

E/\mathbb{F}_p : y^2=x^3-3x+b

　に対応する群を

G_{NIST} = E(\mathbb{F}_p )

と表し、この群をECDSA署名に利用します。
しかし群の位数

\#G_{NIST}

は素数

p

とは異なるため、

\mathbb{F}_p

上では演算を行うことができず、

G_{NIST}

上の座標のコミットメント同士の関係を調べることはできません。そのため任意の位数の群に対応する楕円曲線を計算するBröker[4]の方法を用いて位数が

p

となるような楕円曲線

E'/\mathbb{F}_q

　を求め、対応する群

G_{Tom}

を定めます。これらの群

G_{NIST},G_{Tom}

で定義されるPedersen commitment[2]

Com_{NIST},Com_{Tom}

を証明に利用します。生成元

g

、ランダムに生成した値

r

による

x

のPedersen commitmentを

Com(x;r) = xg+rh

と表します。

ZKAttestの知識証明の手順

ここではZKAttestの知識証明の手順について解説します。加算、スカラー乗算についての知識証明について述べそれらを用いてECDSA署名の知識証明の手順を示します。スカラー乗算の知識証明が最も本質的です。

加算の知識証明

ここでは群 $G_{NIST}$ 上の無限遠点以外の元 $a,b,t$ についてそれらの座標を $a_x,a_y,b_x, b_y, t_x, t_y$ とし、これらの値を明かさずにこれらの値が $a+b=t$ を満たすことを示すことが目標です。 $a_x,a_y,b_x, b_y, t_x, t_y$ のコミットメントをそれぞれ $C_1,...,C_6$ とします。 $a_x,a_y,b_x, b_y, t_x, t_y$ は $G_{NIST}$ の座標の値なのでこのコミットメントは $Com_{Tom}$ を用いることに注意して下さい。

$a+b=t$ の証明には $a,b,t$ が無限遠点でないことに注意すると $(a_x−b_x\neq 0∧t = a+b)∨(a_x = b_x∧a_y = b_y∧t = 2a)$ を示せば十分です。ここで

シグマプロトコルで行える知識証明は $∧,∨$ の演算について閉じていること
同一の体上の加算や乗算の知識証明は既存の方法[10]によって証明できるので逆元を用いることで加算乗除の演算が証明できること
$\neq 0$ の証明は逆元を求めてその積が $1$ になることを示し、逆元の存在を証明することによって行えること

に注意すると $a_x = b_x∧a_y = b_y∧t = 2a$ と $a_x−b_x\neq 0$ は証明可能です。したがってあとは $a+b=t$ を示せば良いことになります。

$a+b=t$ の証明には[11]によると
$t_x = (\frac{b_y -a_y}{b_x-a_x})^2-a_x-b_x,t_y = (\frac{b_y -a_y}{b_x-a_x})(b_x-t_x)-a_y$
を示せば十分です。
そのためには $C_1,...,C_6$ から始めて順に
$C_7=Com_{Tom}(b_x-a_x)$
$C_8=Com_{Tom}((b_x-a_x)^{-1})$
$C_9=Com_{Tom}(b_y-a_y)$
$C_{10}=Com_{Tom}(\frac{b_y-a_y}{b_x-a_x})$
$C_{11}=Com_{Tom}((\frac{b_y-a_y}{b_x-a_x})^2)$ $C_{12}=Com_{Tom}(b_x-t_x)$
$C_{13}=Com_{Tom}((\frac{b_y-a_y}{b_x-a_x})(b_x-t_x))$
それぞれの演算に対応する知識証明を行い、最終的に
$C_5=C_{11}-C_1-C_3$ , $C_6=C_{13}C_{12}-C_2$
に対応する演算の知識証明を行います。

以上の手順で加算の知識証明をシグマプロトコルによって行えます。

スカラー乗算の知識証明

上記で説明した加算の知識証明を利用します。
ここでは群 $G_{NIST}$ 上の生成元 $g,h$ と群 $G_{NIST}$ 上の生成元 $g',h'$ 、コミットメント $C_1=Com_{NIST}(\lambda )(= \lambda g+ rh), C_2'=Com_{Tom}(x), C_3'=Com_{Tom}(y)$ が証明者Pと検証者Vに共通して与えられた上で、群 $G_{NIST}$ 上の元 $\lambda$ と群 $G_{Tom}$ 上の元 $x,y$ についてこれらの値を明かさずに $(x,y)=\lambda g$ を満たすことを示すことが目標です。（「'」が付くものは $G_{NIST}$ 上の元であることを表します。）

知識証明の手順

以下のような3ラウンドのやり取りでシグマプロトコルを構成します。

Pが $\alpha, \beta_1, \beta_2, \beta_3$ をランダムに選び、 $(\gamma_1, \gamma_2)=\alpha g$ として $a_1=\alpha g+\beta_1 h, a_2'=\gamma_1 g'+\beta_2 h', a_3=\gamma_2 g'+\beta_3 h'$ を計算します。 $(\alpha -\lambda )g$ の $x,y$ 座標の $G_{Tom}$ 上のコミットメントを $C_4',C_5'$ とした上で、 $a_1, a_2', a_3', C_4', C_5'$ と $(C_2', C_3')+(C_4',C_5')=(a_2',a_3')$ であることを示すコミットメント $X$ （上で示した加算の知識証明を利用）を送ります。
Vが1ビットの $c_0$ と加算の知識証明のためのチャレンジ $c_1$ からなる $c=(c_0, c_1)$ をチャレンジとしてPに送ります。
チャレンジに応じてPが次のように返答を送ります。
- $c_0 = 0$ のとき
  $z_1=\alpha, z_2=\beta_1, z_3=\beta_2, z_4=\beta_3$ として $(z_1, z_2, z_3, z_4)$ を送ります。
- $c_0 = 1$ のとき
  $z_1=\alpha -\lambda, z_2=\beta_1 -r$ （ $r$ は $C_1=Com_{NIST}(\lambda )$ の計算に使用）、 $X$ に対するチャレンジ $c_1$ の返答を $\pi$ として $(\pi, z_1,z_2)$ を送ります。

Pの返答に応じてVは以下のようにPの証明を検証します。

$c_0 = 0$ のとき
$(z_1, z_2, z_3, z_4)=(\alpha, \beta_1, \beta_2, \beta_3)$ を用いて $a_1, a_2',a_3'$ が $\alpha g, \gamma_1, \gamma_2$ のコミットメントであることを確かめます。
$c_0 = 1$ のとき
加算の知識証明によって $X, c_1, \pi$ から $(C_2', C_3')+(C_4',C_5')=(a_2',a_3')$ が成り立つことを検証します。そして $z_1 g+ z_2 h+C_1 = a_1$ が成り立つことと $C_4',C_5'$ が $z_1 g$ の $x,y$ 座標のコミットメントであることを確かめます。

シグマプロトコルであることの証明

以下このプロトコルがシグマプロトコルであることを示します。完全性（Pの証明が正しければVが証明が正しいと分かること）が成り立つことは容易に分かるのでSHVZKとSpecial soundnessが成り立つことを示します。

SHVZK

SHVZKは知識 $\lambda ,x, y$ がなくても $g,h,g',h'$ とランダムな $c=(c_0, c_1)$ が入力されるとVがプロトコルに従う場合のPとVのやり取りと確率的に区別できないやり取りを出力する「シミュレータ」を構成することで証明します。

$c_0 = 0$ のとき
ランダムに $\alpha, \beta_1, \beta_2, \beta_3$ を選び実際の証明と同じように $a_1=\alpha g+\beta_1 h, a_2'=\gamma_1 g'+\beta_2 h', a_3=\gamma_2 g'+\beta_3 h'$ 、 $(\alpha -\lambda )g$ の $x,y$ 座標の $G_{Tom}$ 上のコミットメント $C_4',C_5'$ 、加算の知識証明のコミットメント $X$ を計算し、実際の証明と同じようにやり取りを行います。
$c_0 = 1$ のとき
$z_1, z_2$ をランダムに選んで $a_1$ は $a_1 = z_1 g+ z_2 h+C_1$ 、 $C_4',C_5'$ は $z_1 g$ の $x,y$ 座標とします。加算の知識証明のコミットメント $X$ と返答 $\pi$ は加算の知識証明のシミュレータ（シグマプロトコルであることから存在が保証される）を用いてチャレンジ $c_1$ から構成します。

以上のようにシミュレータを構成できました。

Special soundness

Special soundnessは同一の $C_1,C_2',C_3',a_1, a_2', a_3', C_4', C_5, X'$ とVの異なるチャレンジに対する、Vが正しいと認める返答を入力すると知識 $\lambda ,x, y$ を出力する「エクストラクター」を構成することで証明します。Vのチャレンジ $c$ は $c_0=0$ の場合が1通り、 $c_0=1$ の場合が $c_1$ を持つ2通りの合計3通りを与えます。
まず $\lambda$ は $c_0=0 (z_1=\alpha)$ と $c_0=1 (z_1=\alpha-\lambda)$ の場合の $z_1$ の差を取ることで得られます。
さらに

$c_0=0,1$ のときにそれぞれ $a_2',a_3'$ と $C_4',C_5'$ が $G_{Tom}$ の元であることが確認でき、 $c_0=1$ のときに $(C_2', C_3')+(C_4',C_5')=(a_2',a_3')$ が成り立つことを確認できることから $C_2',C_3'$ も $G_{Tom}$ の元であること
ある $\alpha$ が存在して $a_2',a_3'$ が $\alpha g+ \beta_1 h$ のコミットメントであること
$c_0=1$ のときに $z_1 g+z_2 h+C_1=a_1 =\alpha g + \beta_1 h$ が成り立つこと
$C_2',C_3'$ が $c_0=0,1$ のときに $z_1 g+ t = \alpha g$ を満たす $t$ の $x,y$ 座標のコミットメントであること（加算の知識証明のエクストラクターを用いる）

を確認できます。したがって $(x,y)$ の値を $\lambda g$ として得ることができ、 $c_0=1$ のときに $t=\lambda g =(\alpha -z_1)g$ および $C_1=(\alpha -z_1)g+(\beta_1 -z_2)h$ が成り立つこと、つまり $C_1$ が $\lambda g$ のコミットメントであることを確認することができました。

ECDSA署名の知識証明

通常のECDSA署名は楕円曲線上の群を用いて

群の位数 $n$ 、生成元 $g$
秘密鍵 $d$
公開鍵 $q=dg$
メッセージ $m$ とそのハッシュ値 $t$
$R=(r,-)=kg$ ( $k$ はランダムに選ぶ)
$s=k^{-1}(t+rd)\;mod\;n$

に対して証明者が署名 $(r,s)$ を送り、検証者が $R=u_1g+u_2q(u_1=ts^{-1}, u_2=rs^{-1})$ を検証することによって行われます。
ZKAttestでは証明者が署名 $(R,z=sr^{-1})$ を送り検証者が $zR-tr^{-1}g=q$ を検証することによってECDSA署名を行います。この署名と検証に上で示した加法と乗法の知識証明を用いることでシグマプロトコルによってECDSA署名を実現できます。
詳細は元論文[1]を参照して下さい。

応用と実装

ZKAttestはリング署名、グループ署名、証明書が非失効であることの証明に応用できます。
またTypescriptを用いた具体的な実装がgithub上に公開されています。Webブラウザ上で動作し、10秒以内のメンバーシップの証明を最大数千のリストに対して行うことが可能だそうです。一回の証明の検証は一秒未満で実行できますが、健全性が保証されないので複数回実行することで補われます。
詳細は元論文[1]を参照して下さい。

まとめと感想

ZKAttestの具体的なプロトコルについてまとめました。紹介しきれなかった部分は元論文を参照して下さい。証明が複雑で誤植もあったので読むのが大変でした。理解しきれていない部分もあります。以下私の疑問点、理解不足の点を挙げます。

Special Soundnessの証明でProverの返答を3つ用いているのは正しいのか？（元のSpecial Soundnessの定義では2つの返答を用いている[8]。）
スカラー乗算の知識証明の1ラウンド目でProverが $\alpha, \beta_1, \beta_2, \beta_3$ をランダムに選択しなかったときに不都合は生じないのか？Proverの不正は行われないのだろうか？
ECDSA署名のリング署名への応用について理解できていない。