ECDSAの3ラウンドt-of-n 閾値署名アルゴリズムの解説

Table of Contents

はじめに

この記事では[1]の論文の部分的な解説をします。いわゆるDKLSプロトコル[5][6]と呼ばれる効率的なECDSA閾値署名アルゴリズムを開発した研究者グループによる最新の研究成果です。

概要

この論文[1]では、3ラウンドでt-of-n閾値ECDSA署名を実行する方法について解説しています。この論文で提案されている手法の特徴としては以下の通りです。

ECDSAで既に使用されている暗号学的仮定以外の仮定を必要としない
EDDSAにおいて安全であることが知られている単純な閾値署名アルゴリズム[2]と同じラウンド数（3ラウンド）で、ECDSAの閾値署名が実行可能である

なおこのプロトコルでは内部的に紛失通信プロトコルを使っているため、その紛失通信プロトコルの暗号学的仮定に依存します。効率の良い紛失通信プロトコルを使い、より多くの暗号学的仮定を受け入れる選択肢もあります。

プロトコル

概要、記号の説明など

ECDSA署名自体の解説は割愛するのでwikipediaの記事[4]を見てください。
この記事中での変数を以下のように定義します。
秘密鍵 $\text{sk}$ 、署名対象のメッセージ(全員が知っている公開情報)をa、最終的に出力される署名値を $(R_x, s)$ とし、 $b = R_x = [r \cdot G]_x$ はナンス値rを生成元Gに掛けた点（有限体上で定義された楕円曲線上の点）のx座標とします。

また、パーティの集合を $P$ と置き、パーティi以外の集合を $P^{-i}$ と置きます。

ここで、 $s =\frac{a + b\ \text{sk} }{r}$ として生成することになるのですが、このナンス値rはaとb両方にかかっています。このsを計算する際の式のために、ECDSAは線型性がありません。そこで、線形性を導入するために[3]などの方法で無理やり分割していました。
この論文でも各パーティが持っているシェアを加算して線形性を導入します。手法としては[3]と似たような紛失通信を利用したシェアの分割・変換を使うのですが、分割方法が以前の手法とは異なっています。

プロトコルの直観的な説明

主に [1]の3.2 The Basic Three-Round Protocol を解説します。

まず、各パーティiがナンスrと秘密鍵skの加算シェア $r_i, \text{sk}_i$ に加えて、マスク変数 $\phi_i$ を生成します。
さらに、これらのシェアを組み合わせて再分配することで、以下のような式を満たすシェア $u_i, v_i$ を入手できたと仮定しましょう。

(1) $\sum_{i \in P} u_i = \sum_{i \in P} r_i \cdot \sum_{i \in P} \phi_i$
(2) $\sum_{i \in P} v_i = \sum_{i \in P} \text{sk}_i \cdot \sum_{i \in P} \phi_i$

この時、署名値sは以下のようにして $u_i, v_i, \phi_i$ の組み合わせで表現できます。

$\frac{ \sum_{i \in P} a \cdot \phi_i+ b\cdot v_i }{ \sum_{i \in P} u_i } = \frac{a + b\cdot \text{sk}}{r}$

各パーティが手元に持つシェアは $a\cdot\phi_i + b\cdot v_i$ と $u_i$ になり、これを他のパーティに送信することで上記の署名値を作ることになります。

なので、大雑把にいえば上記を満たす $u_i, v_i$ を作ることが目標になります。

なおラウンドとしては、大雑把に $R_i = r_i \cdot G$ をコミットするのが1ラウンド、上記の $u_i, v_i$ を作るのに2ラウンド使い、合計3ラウンドになります。

RVOLE

シェア $u_i, v_i$ を直接作ることは難しいので、まず $r_i, \text{sk}_i$ を分割して $c_{i,j}^U, c_{i,j}^V, d_{i,j}^U, d_{i,j}^V, \chi_{i,j}$ のような変数を作り、それらを組み合わせて (1)(2)の関係を満たす $u_i, v_i$ を作ることにします。

そのために、 $r_i, \text{sk}_i$ を分割する何らかの別のプロトコルが必要になります。この論文でそのために導入されているプロトコルが RVOLE (Random Vector Oblivious Linear Evaluation: 直訳すればランダムベクトル紛失線形評価(?))です。

実現方法の詳細は立ち入って説明しませんが、アリスとボブの2者間で行われるプロトコルです。それぞれアリスもボブも攻撃者として振る舞う可能性があるプロトコルであり、その不正に振る舞った事実をRVOLEプロトコル内では検出できません。そのため、RVOLEを実行する際には、RVOLEの外部で通信相手が正しくプロトコルに従ったかどうかを検証する必要があります。

RVOLEの機能の説明

Functionality 3.5. FRVOLE(q, l): Random Vector OLEからの抜粋です。プロトコルではなく機能の説明であることに注意してください。

このプロトコルには2つのパラメータ(q, l)があります。qはやりとりされる有限体要素の属する有限体の位数であり、lはやりとりされる有限体要素ベクトルの長さです。

i. アリスもボブも正直にプロトコルに従った場合

アリスは有限体の要素からなる長さlのベクトル $\alpha$ を入力とする。
ボブはランダムな値 $\beta$ を入力とする。
プロトコルが終了すると、 $\{\alpha_i \cdot \beta\}_{i\in[l]} = \{ c_i + d_i\}_{i\in[l]}$ を満たすベクトル $c, d$ がそれぞれアリスとボブに分配される。

ii. アリスが不正を行う場合

上記の(i)のプロトコルにおいて、アリスは自分でcを先に決定し、ボブが受け取るベクトルdを $d = \{\alpha_i \cdot \beta -c_i\}_{i\in[l]}$ のように操作することができる。

iii. ボブが不正を行う場合

上記の(i)のプロトコルにおいて、ボブは自分でdを先に決定し、アリスが受け取るベクトルcを $c = \{\alpha_i \cdot \beta -d_i\}_{i\in[l]}$ のように操作することができる。さらに、ボブはランダムな値 $\beta$ をランダムではなく、自分で好きな値を設定するように操作することができる。

RVOLEを使ったシェアの実現方法

主にProtocol 3.6. π ECDSA(G, n, t): t-Party Three-Round ECDSA の解説です。

パーティiは、自分以外のすべてのパーティj とRVOLEプロトコル(q, 2)を2回並列に実行します。この実行は、①パーティiが上記RVOLE機能におけるアリスとして振る舞うものと、②パーティiがボブとして振る舞うものがあります。

①においてはパーティiはベクトル $\{ r_i, \text{sk}_i\}$ を渡します。また、②においてパーティiは $\chi_{i,j}$ (上記RVOLE機能におけるb)を受け取るものとします。

①の結果としてパーティi は $\{c_{i,j}^U, c_{i,j}^V\}$ （上記RVOLE機能におけるc）を受け取り、②の結果としてパーティi は $\{d_{i,j}^U, d_{i,j}^V\}$ （上記RVOLE機能におけるd）を受け取ります。
いずれもやりとりするのは2要素のベクトルです。

さらに、パーティiは自分を除く全員のパーティjから $\psi_{j,i} = \phi_{j} - \chi_{j,i}$ を受け取ります。

この結果として得られた $c_{i,j}^U, d_{i,j}^U,\chi_{j,*}$ を使って、式(1)を満たすような $u_i$ を以下のようにして定義します(なお、以下はすべて $r_i$ の分割、すなわちRVOLEでやり取りしたベクトルの第一要素のみを扱っていますが、 $sk_i$ の分割についてもまったく同様に式(2)を満たすような $v_i$ が(4)のように定義できます)。
これはパーティiが持っているシェアだけを使って計算できます。

(3) $u_i = r_i\cdot(\phi_i + \sum_{j \in P^{-i}} \psi_{j,i}) + \sum_{j \in P^{-i}}(c_{i,j}^U + d_{i,j}^U)$
(4) $v_i = \text{sk}_i\cdot(\phi_i + \sum_{j \in P^{-i}} \psi_{j,i}) + \sum_{j \in P^{-i}}(c_{i,j}^V + d_{i,j}^V)$

実際、式(3)の $u_i$ の値に $\psi_{j,i} = \phi_{j} - \chi_{j,i}$ を代入すると、以下のように式変形できます。

$u_i = r_i\cdot\phi_i + r_i \sum_{j \in P^{-i}} \phi_j - r_i \cdot \sum_{j \in P^{-i}} \chi_{j,i} + \sum_{j \in P^{-i}} (c_{i,j}^U + d_{i,j}^U) = r_i\phi + \sum_{j \in P^{-i}} (c_{i,j}^U + d_{i,j}^U - r_i \cdot \chi_{j,i} )$
最右辺の第2項はすべてのiについて足し合わせると0になるので、結局式(3)の定義は式(1)を満たしていることがわかります。

おわりに

RVOLEの詳細までは調べていないのですが、[3]で似たようなプロトコルについて説明しています。
この記事ではRVOLEの出力の正当性検証については説明を省略していますが、3.2節の一貫性チェックのところで記述されています。
他にも、[1]の1. Introductionのところに書いてあるECDSAの閾値署名の歴史がよくまとまっていてわかりやすかったです。
論文自体がまだプレプリントなので、レビューの進捗となんらかのプログラミング言語による実装が公開されるのを待ちたいと思います。