最短1ラウンドで和積変換を行う非対話アルゴリズムを用いた2ラウンド閾値ECDSA

Table of Contents

はじめに

NotebookLMのスライドはこちらです。Class_Groups_NIM_and_1-Round_Signatures

以下「準同型秘密分散 (Homomorphic Secret Sharing; HSS) とブランチングプログラム(Branching Programs)」「誤り確率 O(1/T) で実現する準同型秘密分散」「宇宙船問題アルゴリズムによる解決」等のセクションは、どうやってNIMが発明されるに至ったのかという経緯を説明しているだけなので、新しい和積変換にのみ興味がある場合は「剰余類の基本（一般論）」から読んでください。

概要

2ラウンドで閾値ECDSAの署名が実行になる論文¹の解説をします。
この実装は非対話で積を計算する論文²の成果を利用していますが、²は非対話での積の計算を行えるようにした最初の研究ではありません。

非対話で積が計算できるようになった歴史的背景を説明します。まず ³ において「暗号化された値と、秘密分散された値の積を和に変換したものを各パーティが個別に計算しておき後で合算する」ようなアルゴリズムが開発されました。
しかし、そのアルゴリズムは一定のエラー確率 $O(1/T)$ で失敗する(Tは実行時間)という問題があり、さらに積の値は十分小さな値である必要がありました、エラー率の問題を改善して限界を示した研究が⁴です。⁴によってエラー確率は $O(1/T^2)$ まで改善されましたが、まだ積の値が小さな値でなければならないという制約は残りました。

ここまでの研究はすべて標準的な暗号学的仮定 (DDHなど)を用いてきました。非標準的な暗号学的仮定であるペイエ暗号と同等の仮定（DCR⁵）を用いることで、トラステッドセットアップは必要であるものの、エラーが発生しないようにし、さらに「積の値が小さな値でなければならない」という制約を無くすことに成功した研究⁶が出てきます。

さらに上記研究⁶のペイエ暗号の仮定（DCR⁵）を、別の非標準的な暗号学的仮定である類群(Class Group)上のDDH-CL, DXDH-CLのような仮定に入れ替えられるように一般化し、任意の積の値をエラーなしで計算することができるように⁶を改善した研究が ⁷です。類群を使うことで、トラステッドセットアップも不要になりました。

この⁷の論文を利用して非対話での積（ベクトル内積）の計算を形式化したのが ² です。¹はその成果を利用して、ECDSA署名計算に必要な乗算を加算に変換し、線形化することで、閾値ECDSAを実現しています。¹で実現したいことは⁸と同じであり、既存の紛失通信プロトコル(SoftSpokenOT⁹等)に依存した¹⁰のような手法よりもラウンド数が少なく実現できるのが嬉しいポイントです。
ただし、その代償として¹では⁷から引き継いだ非標準的な暗号学的仮定(DDH-CL, DXDH-CL)に依存しています。また¹では2ラウンド署名の先行研究としてそれぞれDCR⁵に依存した2パーティ閾値ECDSAの研究¹¹¹²を挙げていますが、それぞれOTや準同型暗号を発展させた伝統的な手法であり、¹で使用された手法とは大きく異なります。
以前紹介した手法¹⁰は3ラウンドですが、標準的な暗号学的仮定を使用しており、データ送信サイズも¹と比べて少ないため、採用検討の余地は十分にあります。

準同型秘密分散 (Homomorphic Secret Sharing; HSS) とブランチングプログラム(Branching Programs)

以下のようなシチュエーションを考えます。

アリスがボブとキャロルにある関数Fの実行を依頼することを考える。アリスは関数Fを自分自身では実行せず結果を教えてもらいたい。ボブとキャロルは互いに通信できない。関数F自体はアリス、ボブ、キャロルの全員が知っているが、関数の入力値xを知っているのはアリスだけであり、アリスはボブとキャロルにxの値を知らせたくない。
そこで、アリスは入力値xを $x = x_1 + x_2$ になるように秘密分散してボブとキャロルに $x_1, x_2$ を渡す。ボブとキャロルは、自分の手元で秘密分散された $x_i$ と Fを使って関数fを実行し、その結果 $f(x_i)$ をアリスに返却する。
アリスはボブとキャロルから受け取った $f(x_i)$ を手元で足し合わせて $F(x)$ を回復する。

このようなシチュエーションで、秘密分散値の評価結果を足し合わせることで、秘密分散される以前の値を評価した値を回復することができるスキームを準同型秘密分散 (Homomorphic Secret Sharing; HSS) と呼びます。
任意の関数Fを評価することができれば良いのですが、標準的な仮定においては、そのような手法は知られていません。一方で、関数Fが線形な関数であれば、上記の準同型秘密分散は常に成り立ちます。
それでは、Fが線形よりももう少しだけ複雑な関数の場合にはどのようなことが言えるでしょうか。2016年の研究³によって、関数Fが以下のような性質を持つ関数（Branching Programs）¹³ の場合には、標準的仮定であっても 確率的には 成立することがわかっています。

ブランチングプログラム(Branching Programs)
以下を満たすような関数Fをブランチングプログラムと呼ぶ。関数Fの入力値は秘密入力値であることに注意する。
$x = (x_1, . . . , x_n) \in \{0, 1\}^n$ を秘密の入力とする。
以下のような命令セットの組み合わせからなる関数 $F (x) \in \mathbb{Z}$ を計算したい。

$v_i , v_j , v_k \in \mathbb{Z}$ の内部変数に対して $v_i \leftarrow v_j \pm v_k$ の操作を実行する。内部の変数として線形な加算の操作を行う。

$v_i \leftarrow v_j \cdot x_k$ の操作を行う。ただし $x_k$ は秘密の入力値である。すなわち、内部変数と秘密の入力値をかけ合わせて、内部変数に代入する操作を行う。

$v_i \leftarrow x_k$ の操作を行う。内部変数に入力値を代入する操作を行う。

秘密入力値xについて:
各計算者には $x_i = y_i + z_i$ を満たすような変数 $y_i , z_i$ を作成して分配する。
また、Gを生成元gで生成される暗号学上の群として、El-Gamal暗号のような形式で暗号化された $x_i$ の値 $g^{x_i}$ を公開して各パーティが使用可能にしておく（後述の積和変換で利用するため）。ここでは単純化のために $g^{x_i}$ と書くが、実際にはもっと強固に暗号化されていることに注意。

ブランチングプログラムは RMSプログラム¹⁴とほぼ同じです。一般的なループのないプログラムは Straight-line program¹⁵ とよばれ、その中で乗算を制限したものが RMSプログラムです。このようなブランチングプログラムでは全ての関数が表現できるわけではありませんが、それでも2番の乗算が可能であることから、単純な線形の関数よりも多くの関数を表現できるため、PIR等の応用先があります³。

誤り確率 O(1/T) で実現する準同型秘密分散

上記の準同型秘密分散をブランチングプログラムに対して適用しようとすると、 $v_i \leftarrow v_j \cdot x_k$ の乗算操作が問題になります。この乗算操作を行おうとすると、 $v_i, v_j$ は良いとして、2人のプレイヤーが $x_k$ を個別に評価することができないためです。そこで、上記のEl-Gamal 暗号の手法を使います。2人のプレイヤーの持つ変数を $v_{i,0}, v_{i,1}$ とし、暗号化された入力値を $g^{x_k}$ とします（再度注意: この $g^{x_k}$ はわかりやすくするために単純化して書いており、実際にはもっと複雑に暗号化されます）。ここで秘密分散された $x_k = y_k + z_k$ は出てこないことに注意してください。
2人のプレイヤーは手元で $(g^{x_k})^{v_{i,0}}, (g^{x_k})^{v_{i,1}}$ を計算します。この時点で $g^{{x_k} \cdot {( v_{i,0} + v_{i,1} ) }} = g^{v_i}$ が成立しています。なので、あとはこのgの指数部分に乗った $v_i = a + b$ の加法分散シェアを手元で求めればよいのです。
ストレートに考えると、gの離散対数を計算しなければシェアは求められません。しかし、以下の宇宙船問題アルゴリズム¹⁶を使えば、「 $v_i$ は小さな値である」という制限のもとで $v_i = a + b$ を満たすようなシェアを求めることができます。

宇宙船問題アルゴリズムによる解決

単純化するために $v_i \in \{0,1\}$ であるとします。このとき $v_i = a - (-b) = x_k \cdot v_{i,0} + x_k \cdot v_{i,1}$ の差分が0,1のいずれかであると言えます。(※)

ボブは $g^{x_k \cdot v_{i,0} }$ を知っておりキャロルは $g^{-x_k \cdot v_{i,1} }$ ( $g^{x_k \cdot v_{i,1} }$ から計算)を知っています。もしもボブとキャロルがローカル計算だけで共通の群要素 $g^\tau$ を見つけることができて、 $g^\tau = g^{x_k \cdot v_{i,0} + t_0} = g^{-x_k \cdot v_{i,1} + t_1}$ が成り立つのであれば、 $x_k \cdot v_{i,0} + x_k \cdot v_{i,1} = t_1 - t_0 = v_i$ になることから、 $a = t_1, b= -t_0$ とおくことで加法秘密分散が取得できます。
このような都合の良い $t_0, t_1$ を見つけるために、ボブとキャロルは $\text{start} = x_k \cdot v_{i,0}$ 、 $\text{start} = -x_k \cdot v_{i,1}$ のそれぞれから、 $g^{\text{start} + t}$ の要素を検索し（ $0\le t\le T$ ）、最も小さな値 $g^\tau = \text{min}(g^{\text{start} + t})$ を見つけます。そして、(※)の前提条件から差分が0または1であるためその最も小さな値が一致しないエラー確率は $O(1/T)$ になります。

この検索方法を改善することでエラー確率を $O(1/T^2)$ にした研究⁴も、基本的には同じ方法を使っています。

なお、実際にはEl-Gamal暗号に似た暗号方式で暗号化されているため、上記の指数部分が小さな値であっても離散対数が解かれ、復号されてしまうことはありません。

平方剰余仮定を用いた誤り確率0のアルゴリズム

上記の宇宙船問題を使ったケースでは、内部変数は小さな値である必要があり、さらに共通の群要素を見つけられるかどうかが確率的でした。Pailler暗号の仮定である平方剰余を用いることで、内部変数の制限がなくなり共通の群要素を確実に見つけられるようになります⁶¹⁷。また、トラステッドセットアップが必要になります。（この記事では説明しません）

類群を用いた誤り確率0のアルゴリズム

平方剰余仮定の代わりに類群¹⁸¹⁹を用いることで、トラステッドセットアップを不要にすることができます⁷²⁰。
以下の説明は過去の記事 ¹⁸が前提になっているので、類群やCL暗号についてはそちらを参照してください。

剰余類の基本（一般論）

G が可換群で、F がその部分群、g は G の元とする。このとき、 $g F=\left\{gf:f\in F\right\}$ を G における F の剰余類 (coset) という²¹。

以下、 Fを巡回群とする。Gの要素a, b に対して $aF = bF$ が成り立つとき「同じ」剰余類であるという（同値関係）。この同値関係の条件は $a \cdot b^{-1} \in F$ が成り立つことと等しく²¹、さらに $a = z \cdot f^{u},\; b = z \cdot f^{v} \;$ (同じz)という形式で表せることとも等しい（²²の同値ならば $a = b \cdot h, h = f^m \in F$ という形で表現できるという説明と、巡回群Fの要素が $f^m$ で表せるという説明から成立）。

CL暗号フレームワークを使った表現

CL暗号¹⁸はイデアル類群を使った暗号フレームワークです。以前のブログ記事¹⁸で解説した「離散対数問題が易しい部分群Fを持つが、それ自体の離散対数問題は難しいようなイデアル類群G」を使用します。以前のブログ記事¹⁸ではこのイデアル類群を加法準同型暗号を作るために使っていましたが、ここでは共通の要素へのマッピングを行うのに都合が良い関数「剰余類ラベル関数」を構成するのに使います。さらに、このマッピングを行った結果を利用し、離散対数問題が易しい部分群のみを抽出して、結果を取り出すのにも使っています。

上記で言う「共通の要素へのマッピング」とは、上記で言う「宇宙船問題アルゴリズム」を失敗確率0で実行できるアルゴリズムに該当します。

剰余類ラベル関数 φ の説明

$\phi$ を「剰余類 $zF$ の代表元（ラベル）を返す」関数とし、「剰余類ラベル関数」と呼びます。 $\phi(z f^{u}) = \phi(z f^{v}) = z$ となります。
各サーバーは同じラベル $z$ を得ることができます。この前提として、各サーバーは事前に同じ剰余類 $zF$ に所属している要素を入力する必要があります。

直感的には、以前のブログ記事¹⁸で書いたような判別式 $\Delta_p$ (p倍数しかいない世界) と $\Delta_K$ (p倍数以外もいる世界)のそれぞれの世界を考えます。

まず $\Delta_K$ の世界から $\Delta_p$ の世界に持ってくるときに部分群Fの情報を消して Fによらない部分の共通の情報だけを抽出し、それを再度 $\Delta_p$ の世界から $\Delta_K$ の世界に持ち込む（＝自然なイデアルの整数環の拡張）ことで、 $\Delta_K$ の世界での共通の要素を取得することができます。

加法シェアを作る手順

サーバー $b$ が $a_b = z \cdot f^{u_b}$ を持っているとします。

剰余類ラベルを取得： $\ell_b \leftarrow \phi(a_b)$ （両者同じ $\ell = z$ ）
剰余類部分を消す： $X_b \leftarrow a_b \cdot \ell^{-1} = f^{u_b} \in F$
離散対数問題が簡単な部分群で指数を読む： $u_b \leftarrow \log_f(X_b)$ （CL ではこれができる）
符号付きで出力: サーバー0は $w_0 = -u_0$ 、サーバー1は $w_1 = u_1$

すると $w_0 + w_1 = -u_0 + u_1 = \log_f\!\left(\frac{a_0}{a_1}\right) = \log_f( \frac { z\cdot f^{x_k \cdot v_{i,0} } }{ z\cdot f^{-x_k \cdot v_{i,1} } } ) = \log_f( f^{x_k \cdot (v_{i,0} + v_{i,1}) } ) = {x_k \cdot (v_{i,0} + v_{i,1}) }$ が積の加法分散になります。

「誤り確率 O(1/T) で実現する準同型秘密分散」では離散対数問題が簡単な部分群が無かったので、(3) の代わりに “特別な点までの歩数”を使って指数差を再現していた、という対応関係です。

なお、このままだと $f^{x_k}$ という値がHSSの依頼者から送られてくることになってしまい、それを各サーバー側で復号して秘密情報であるはずの xを入手できてしまうので、実際にはクライアントは秘匿化したxをサーバーの公開鍵で暗号化した値をサーバーに送り、サーバーがxの値を直接のローカル計算で得られない（しかし比を取ると部分群F上に計算したい値が入ってくる）ように工夫する必要があります。この正しい方法については ⁷の5.2 Public-Key HSSで説明されています。

トラステッドセットアップ不要かつ誤り確率0のHSSを用いた非対話型の積和変換 (NIM)

上記で説明した「類群を用いた誤り確率0のアルゴリズム」とほぼ同様のアルゴリズムを使って、積和変換アルゴリズムを構成できます。（応用というよりは、むしろ積和変換アルゴリズムの方が前提が少なくわかりやすいですが）

非対話型といっても、「一度相手に情報を送った後は非同期的にローカル計算で積和変換が完了する」という意味であり、プレイヤー間のコミュニケーションがないわけではありません。
トラステッドセットアップ不要な類群を用いた上記HSSと類似のアルゴリズムを使うと、積を和に変換するアルゴリズムを非対話で実行することができます²。

具体的には²の「4.3 Constructions from group-based assumptions」で説明されているNIMアルゴリズムのようになります。なお以下の説明ではベクトルではなく単一の要素の積和変換を行っていますが、論文ではベクトルの内積計算をしています。また、 $h_0, h_1$ は共有されたランダムな生成元です。

アリス入力: rを乱数として $d = {h^r_0} {h^a_1}$
ボブ入力: sを乱数として $(e_0, e_1) = (h^s_0, f^b h^s_1)$

アリス操作: $Z_A = e^r_0 e^a_1 = h^{rs}_0 f^{ab} h^{as}_1$
ボブ操作: $Z_B = d^s = {h^{rs}_0} {h^{as}_1}$

これによって、アリスとボブの $Z_A$ , $Z_B$ の比 $Z_A / Z_B = f^{ab}$ が成り立つため、上記のHSSと同じように剰余類ラベル関数φを使って手元で以下を計算することで、加法分散を得ることができます。

（ここでランダムに選んだ $h_0, h_1$ にも未知の $f$ 成分は含まれると考えられるため、単純にφを適用するだけでは $f^{ab}$ が出てくることは無いはず）

以下のシェアは $w_a + w_b = ab$ を満たします。

アリスのシェア: $w_a = \log_f( Z_A / \phi(Z_A) ) = \log_f(f^{ab} \cdot f^x)$
ボブのシェア: $w_b = -\log_f( Z_B / \phi(Z_B) ) = -\log_f(f^x)$

非対話型の積和変換を使った2ラウンドt-of-n閾値ECDSA

上記の非対話型積和変換を利用することで、2ラウンドt-of-n閾値ECDSA¹を実現できます。
2ラウンドとは言っても、ラウンド1の方は署名値が出てくる前に計算しておくことが可能なので、署名の際に必要なのは実質1ラウンドと言えます。

Round 1（事前計算／presigning）

各参加者 $i$ は乱数 $k_i,\ \gamma_i$ を選び、コミットとして $g^{k_i}$ を公開する。同時に、各参加者は $k_i,\ x_i,\ \gamma_i$ をNIM に入力する。すると、各ペア $(i,j)$ は加法シェアとして $k_i\gamma_j$ と $x_i\gamma_j$ を得る。その結果、各参加者は最終的に $k\gamma$ と $x\gamma$ の加法シェアを持つことになる（ここで $k=\sum_i k_i$ 、 $\gamma=\sum_i \gamma_i$ ）。また $g^k$ は公開の値となる。

Round 2（メッセージ確定後のオンライン署名）

署名対象メッセージが分かった段階で、トランスクリプト（通信ログ）からハッシュにより $z,y$ を導き、nonce を $k$ から $zk+y$ に再ランダム化する。
これにより $R=g^{zk+y}$ を計算し、 $r$ を $R$ の $x$ 座標（ $r=R|_{x\text{-axis}}$ ）として定め、これらは公開で共有される。
各参加者 $i$ は自分の持つシェアを使って $m\gamma_i + r\cdot(x\gamma)_i$ と $z\cdot(k\gamma)_i + y\gamma_i$ の2 つの値を送る。これらを全員分集めて足し合わせると、それぞれ $\gamma(m+rx)$ と $\gamma(zk+y)$ が得られる。

最後に割り算（＝逆元による乗算）で $\sigma=(zk+y)^{-1}(m+rx)$ を得る。

感想

これまで見てきた和積変換の仕組⁸¹⁰と比べて圧倒的にシンプルであり、結果として2ラウンドECDSAのアルゴリズム自体も非常にシンプルになっています（安全性の証明までは追ってないので正しいのかはわかりませんが）。
調べてみる前は、イデアル類群というのは普段名前を聞かないし、あまり保守的な仮定ではないのでは？と漠然と考えていたのですが、楕円曲線暗号と同じく1980年代からある暗号ファミリーで、楕円曲線暗号と同じく複雑な群の離散対数問題の困難性に依存しているなど、別にそこまでおかしな仮定には思えなくなりました。

そもそも以前のブログ¹⁸で書いたように、離散対数問題に依存している問題については、元になっている群の複雑さの関係性が知られていない以上、どちらがより保守的なのか、というのを簡単に決めることはできないのではないでしょうか。

類数計算の困難性²³についても、厳密に指数時間かかるということは説明されていなかったものの、すくなくともガウスの時代(19世紀初頭)から、二次形式の同値類（＝虚二次の場合は類群の元）を「実際に列挙・計算する」こと自体が重要なテーマであり、歴史的に困難とみなされてきた問題であるようです。そのことを考えると、やはり「類数計算の困難性」「イデアル類群の離散対数問題の複雑性」に依存した暗号系（CL暗号）は安全性について筋が通っているように感じました。