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

お知らせ
Table of Content

はじめに

この記事では前回の記事 [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_yG_{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 = 2aa_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ラウンドのやり取りでシグマプロトコルを構成します。

  1. 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 )gx,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(上で示した加算の知識証明を利用)を送ります。
  2. Vが1ビットのc_0と加算の知識証明のためのチャレンジc_1からなるc=(c_0, c_1)をチャレンジとしてPに送ります。
  3. チャレンジに応じて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 -rrC_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 gx,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 )gx,y座標のG_{Tom}上のコミットメントC_4',C_5'、加算の知識証明のコミットメントXを計算し、実際の証明と同じようにやり取りを行います。
  • c_0 = 1のとき
    z_1, z_2をランダムに選んでa_1a_1 = z_1 g+ z_2 h+C_1C_4',C_5'z_1 gx,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のチャレンジcc_0=0の場合が1通り、c_0=1の場合がc_1を持つ2通りの合計3通りを与えます。
まず\lambdac_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を満たすtx,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署名のリング署名への応用について理解できていない。

これらの疑問点に対する答えや間違いを見つけたら教えて下さい。

参考文献

[1]https://dl.acm.org/doi/abs/10.1007/978-3-030-99277-4_4
[2]https://doi.org/10.1007/3-540-46766-1_9
[3]https://www.w3.org/TR/webauthn-2/
[4]Bröker, R.: Constructing Elliptic Curves of Prescribed Order. Ph.D. thesis, Leiden (2006)
[5]https://doi.org/10.1007/3-540-48910-X_8
[6] https://doi.org/10.1007/978-3-662-46803-6_9
[7] IPUSIRON(2017). 暗号技術の全て, 翔泳社
[8] Damgard(2010). On Σ-protocols https://www.cs.au.dk/~ivan/Sigma.pdf
Goldwasser, S., Micali, S., & Rackoff, C. (1985). The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985.
[9] WebAuthn: https://developer.mozilla.org/ja/docs/Web/API/Web_Authentication_API#Registration
[10]https://doi.org/10.1007/3-540-48910-X_8
[11]https://doi.org/10.1007/978-0-387-09494-6_3
[12] https://tech.hashport.io/3356/

タイトルとURLをコピーしました