コンテンツにスキップ

Fast Multiparty Threshold ECDSA with Fast Trustless Setup

2019-03-13

Rosario Gennaro, Steven Goldfeder. 2018. 論文。 著者のイニシャルと発表年をとって GG18 と呼称しているようなので倣う。

離散対数暗号の DSA 形式の署名における多人数の threshold signatures の問題への解法が述べられている。

DSA の threshold signatures

threshold signing / threshold signatures とは、nn人で秘密鍵を分割保有し、そのうち t+1t+1 人集まれば署名を作成できるというシステム。いわゆるマルチシグ。

離散対数の DSA は一般的に

R=g1kr=H′(R)s=k(H(m)+xr) \begin{aligned} R &= g^{\frac{1}{k}} \\ r &= H'(R) \\ s &= k(H(m) + xr) \\ \end{aligned}

と表される。 ここで、

  • x x は秘密鍵
  • k,r,s k,r,s は署名に用いる一時的な値
  • M M は署名対象のメッセージ
  • H H はメッセージのダイジェストを得る関数
  • H′ H' は巡回群 G G からスカラ Zq Zq へ変換する関数
    たとえば ECDSA なら座標 P P の x x 座標を得る関数

である。

threshold signing のためには、x,k を分散して保有し、r,s を生成できればよいのだが、分散保有した値から、kの逆数の指数演算と、二つの秘密数 x,k の積を求めるのが難しい。

MtA

この問題を解決するため、GG18 論文では Multitive to Addaptive というテクニックを適用している。積和変換とでも訳せばよいか。

Alice, Bob がそれぞれ秘密数 a,b a, b を持っているとする。

  1. Alice は自身の公開鍵 A A で a a を加法準同型暗号化した値 cA=EA(a) c_A = E_A(a) を Bob へ送る
  2. Bob はランダムな値 β′ \beta' を選び、 cB=b×EcA+EEA(β′) c_B = b \times_E c_A +_E E_A(\beta') を計算して Alice へ送る。
    ここで、 ×E,+E \times_E, +_E は、暗号化された値に対する演算。
  3. Alice は得た cA c_A を秘密鍵で複合し、α′ \alpha' を得る。
  4. それぞれ β=−β′ (mod q),α=α′ (mod q) \beta = -\beta'\ (mod\ q), \alpha = \alpha'\ (mod\ q) を計算する。
  5. ab=α+β ab = \alpha + \beta である。

途中に出てきた cB c_B を展開すると、

cB=b×EcA+EEA(β′)=b×EEA(a)+EEA(β′)Eは加法で準同型なので、cB=EA(ab+β′) \begin{aligned} c_B &= b \times_E c_A &+_E E_A(\beta') \\ &= b \times_E E_A(a) &+_E E_A(\beta') \\ E は加法で準同型なので、\\ c_B &= E_A(ab + \beta') \\ \end{aligned}

cB c_B を複合した値が α′ \alpha' であるから、

α′=ab+β′ab=α′−β′=α+β \begin{aligned} \alpha' &= ab + \beta' \\ ab &= \alpha' - \beta' = \alpha + \beta \end{aligned}

MtA を用いた秘密数の積の分散

k k の加法分散 k1,k2,...,kn k_1, k_2, ..., k_n を n人のプレーヤー P0,P1,...Pn P_0, P_1, ... P_n それぞれに秘密共有する。 同様に γ \gamma も秘密共有する。

k=k1+k2+...+knγ=γ1+γ2+...+γn \begin{aligned} k &= k_1 + k_2 + ... + k_n \\ \gamma &= \gamma_1 + \gamma_2 + ... + \gamma_n \\ \end{aligned}

k k と γ \gamma の積を計算すると、

k×γ=(k1+...kn)×(γ1+...+γn)=+ k1γ1+k1γ2+...+k1γn+ k2γ1+k2γ2+...+k2γn+ ...+ knγ1+k2γ2+...+knγn=∑i,jnkiγj \begin{aligned} k \times \gamma &=& &(k_1 + ... k_n) \times (\gamma_1 + ... + \gamma_n) \\ &=&+&\ k_1\gamma_1 + k_1\gamma_2 + ... + k_1\gamma_n \\ & &+&\ k_2\gamma_1 + k_2\gamma_2 + ... + k_2\gamma_n \\ & &+&\ ... \\ & &+&\ k_n\gamma_1 + k_2\gamma_2 + ... + k_n\gamma_n \\ &=& & \sum_{i,j}^n k_i\gamma_j \end{aligned}

ここで、 kirj=αij+βij k_i r_j = \alpha_{ij} + \beta_{ij} として、上の式を展開すると、

k×γ=∑i,jn(αij+βij)=∑jn∑in(αij+βji)右の総和をδi=∑jn(αij+βji)と置くと、k×γ=∑inδiδiを展開して、δi=∑jn(αij+βji)=(αii+βii)+∑j≠in(αij+βji)=ki×γi++∑j≠in(αij+βji) \begin{aligned} k \times \gamma &=& \sum_{i,j}^n (\alpha_{ij}+\beta_{ij}) \\ &=& \sum_j^n \sum_i^n (\alpha_{ij}+\beta{ji}) \\ 右の総和を \\ \delta_i &=& \sum_j^n (\alpha_{ij}+\beta_{ji}) \\ と置くと、 \\ k \times \gamma &=& \sum_i^n \delta_i \\ \delta_i を展開して、\\ \delta_i &=& \sum_j^n (\alpha_{ij}+\beta_{ji}) \\ &=& (\alpha_{ii}+\beta_{ii}) + \sum_{j\neq i}^n (\alpha_{ij}+\beta_{ji}) \\ &=& k_i \times \gamma_i + + \sum_{j\neq i}^n (\alpha_{ij}+\beta_{ji}) \\ \end{aligned}

すべてのプレーヤー同士 Pi,PjP_i, P_j で ki×γjk_i \times \gamma_j と kj×γik_j \times \gamma_i を MtA すると、プレーヤー PiP_i は、αij;j≠i \alpha_{ij; j\neq i} と βji;j≠i\beta_{ji; j\neq i} を所有する。PiP_i は当然 ki,γik_i, \gamma_i も保有しているので、δi\delta_iを計算できる。

つまり、二つの秘密数の加法分散共有から、その積の加法分散共有へと変換できる。

分散鍵生成

論文ではよく分からないが、joint-Feldman VSS を用いていると思われる。 ここでは鍵生成は省略し、以下の性質の秘密分散が出来ているとして進める。

  • 秘密鍵を xx とし、各パーティ PiP_i はその加法分散 uiu_i を持つ。

    x=∑inui x = \sum_i^n u_i

  • 公開鍵 y y は、

    y=gx=g∑inui=∏ingui y = g^x = g^{\sum_i^n u_i} = \prod_i^n g^{u_i}

署名生成プロトコル

以上を踏まえて署名生成プロトコルを説明する。

論文では悪意あるプレーヤーへの耐性や、一般的な (t,n) threshold signining について述べているが、ここでは善意のパーティによる (n-1,n) threshold signing に簡略化する。

Phase 1

各プレーヤー PiP_i はランダムな値 ki,γik_i, \gamma_i を選ぶ。

さらに、 guig^{u_i} および gγig^{\gamma_i} をブロードキャストする。

Phase 2

全てのプレーヤーのペア Pi,PjP_i, P_j で ki,γjk_i, \gamma_j の MtA を行い、

δi=kiγi+∑j≠in(αij+βji) \delta_i = k_i\gamma_i + \sum_{j\neq i}^n (\alpha_{ij} + \beta_{ji})

を計算する。

同様に、kiui=μij+νij k_iu_i = \mu_{ij} + \nu_{ij} の MtA を行い、

σi=kiui+∑j≠in(μij+νji) \sigma_i = k_iu_i + \sum_{j\neq i}^n (\mu_{ij} + \nu_{ji})

を計算する。

Phase 3

各プレーヤー PiP_i は、 δi\delta_i をブロードキャストする。

自身の持つ δi\delta_i と、受け取った δj\delta_j を足して、

δ=kγ=∑iδiを計算し、その巡回群上の逆数も計算する。 \delta = k\gamma = \sum_i{\delta_i} を計算し、その巡回群上の逆数も計算する。

Phase 4

各プレーヤー PiP_i は、R=(∏ingγi)δ−1 R=(\prod_i^n g^{\gamma_i})^{\delta^{-1}} を計算する。なお、gγi g^{\gamma_i} は Phase1 で受け取っている。

この式を展開すると、

R=(∏ingγi)δ−1=(g∑inγi)(kγ)−1=gγ×(kγ) −1=gk−1 \begin{aligned} R &= (\prod_i^n g^{\gamma_i})^{\delta^{-1}} \\ &= (g^{\sum_i^n \gamma_i})^{(k\gamma)^{-1}} \\ &= g^{\gamma \times (k\gamma)~{-1}} \\ &= g^{k^{-1}} \\ \end{aligned}

になる。

H′H' 関数を用いて、

r=H′(R) r = H'(R)

も計算する。これが署名の一つ rr の値である。

Phase 5

各プレーヤー PiP_i は si=mki+rσi s_i = mk_i + r\sigma_i を計算する。

さらに、計算した sis_i をブロードキャストし、受け取った sjs_j を用いて総和を計算する。この総和は、

s=∑insi=∑in(mki+rσi)=m∑inki+r∑inσi=mk+rkx=k(m+rx) \begin{aligned} s &= \sum_i^n s_i \\ &= \sum_i^n(mk_i + r\sigma_i) \\ &= m\sum_i^n k_i + r\sum_i^n \sigma_i \\ &= mk + rkx \\ &= k(m + rx) \\ \end{aligned}

であり、署名の ss 値に一致する。

検証

DSA と同じく

gms+yrs=R g^{\frac{m}{s}} + y^{\frac{r}{s}} = R

を確認すればよい。

gms+yrs=gms+(gx)rs=gm+rxs=g1k=R \begin{aligned} g^{\frac{m}{s}} + y^{\frac{r}{s}} &= g^{\frac{m}{s}} + (g^{x})^{\frac{r}{s}} \\ &= g^{\frac{m+rx}{s}} \\ &= g^{\frac{1}{k}} \\ &= R \\ \end{aligned}

リンク