Threshold ECDSA：マルチパーティ署名

ECDSA署名では、ランダムなノンスk、曲線上の点R = k*G、そして秘密鍵xとRのx座標rを使った署名s = k^{-1}(h + r*x) mod nを計算する必要があります。kの逆元計算と秘密鍵による乗算があるため、ECDSAは、応答が単純な線形結合になるSchnorr署名とは異なり、本質的に非線形です。この非線形性により、当事者間で計算を分散することが非常に難しくなります。

GennaroとGoldfederによるGG18プロトコル（2018年）は、信頼されたディーラーなしで安全に動作する、実用的な2者間およびしきい値ECDSA構成として初めて登場したものです。その核心となるアイデアは、非線形なECDSA計算に必要な乗法から加法への変換（MtA）を実行するために、Paillier準同型暗号を使用することです。GG18は、静的な半正直攻撃者に対するシミュレーションベースの安全性を提供します。

GG20（GennaroとGoldfeder、2020年）は、信頼されたセットアップなしで悪意のある攻撃者に対する安全性を証明することで、GG18を改良しました。GG20では、各当事者がプロトコルに正しく従っていることを保証するために、ゼロ知識証明を追加しています。これらの証明により、悪意のある当事者がノンスや署名に偏りを持たせ、他の当事者の鍵シェアに関する情報を引き出すことを防ぎます。GG20は、多くの本番用MPCウォレット実装の基盤となりました。

CGGMP21（Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021）は、現在最先端の閾値 ECDSA プロトコルです。識別可能なアボートを実現しており、署名プロトコルが悪意のある行動によって失敗した場合に、どの参加者に責任があるかを特定できます。これは、説明責任が重視されるエンタープライズ環境への導入において重要です。CGGMP21 は、tss-lib や multi-party-sig などの主要な MPC ライブラリに実装されています。

閾値 ECDSA における中心的な課題は、秘密シェアを明らかにせずに秘密シェア同士の積を計算することです。MtA（乗法から加法への変換）は、2 者のシェアの積 a*b を加法シェアに変換します。つまり、参加者 1 が alpha、参加者 2 が beta を受け取り、alpha + beta = a*b となるようにします。これは Paillier 暗号を使って実現します。参加者 1 が a を暗号化し、参加者 2 が準同型演算によって b を乗算して乱数を加え、その結果を参加者 1 が復号して加法シェアを得ます。

Paillier 暗号は、加算と平文による乗算の両方をサポートする部分準同型暗号方式です。暗号文 Enc(a) が与えられると、誰でも復号せずに、既知の b に対する Enc(a*b) を計算できます。この性質によって MtA プロトコルが可能になります。参加者 1 が Paillier の鍵ペアを生成し、ノンスと秘密鍵のシェアである Enc(k1) と Enc(x1) を送信します。参加者 2 は準同型演算を使って、k1 や x1 を知ることなく自分の寄与分を計算します。

閾値 ECDSA の署名では、通常、複数ラウンドの通信が必要です。GG20 では、ノンスとランダムなブラインディング値に対するコミットメントを計算する前処理フェーズ（2 ラウンド）と、部分署名を組み合わせるオンライン署名フェーズ（1 ラウンド）があります。前処理はメッセージが判明する前に実行できるため、オンライン処理のレイテンシーを 1 ラウンドに短縮できます。CGGMP21 はこれをさらに最適化しています。

識別可能なアボートとは、閾値署名プロトコルが失敗した場合に、正直な参加者が、どの参加者が不正な振る舞いをしたかを暗号学的に特定できることです。これは、各ステップで正しい計算を行ったことを示すゼロ知識証明を必要とします。識別可能なアボートがなければ、悪意のある参加者は、特定されることなく、プロトコルの完了を拒否してサービス拒否を引き起こせます。

EdDSA（Ed25519 上の Schnorr ベースの署名）は、Schnorr 署名が線形であるため、ECDSA よりもはるかに容易に閾値化できます。応答 z = r + c*x は加法シェアの和だからです。Komlo と Goldberg（2020）による FROST（Flexible Round-Optimized Schnorr Threshold）は、信頼されたセットアップなしで 2 ラウンドの閾値 Schnorr 署名を実現します。FROST は、プライバシー保護プロトコルや暗号資産ウォレットで利用するため、IETF によって標準化が進められています（RFC ドラフト）。

閾値 ECDSA は、MtA プロトコルとゼロ知識証明が必要なため、単一参加者による ECDSA より計算コストが高くなります。GG20 の 2 者署名は最新のハードウェアで約 1～2 秒かかります。n が大きい場合の閾値署名では、参加者ペアごとに MtA を実行するため、さらに時間がかかります。CGGMP21 の最適化により、処理時間は数百ミリ秒まで短縮されます。署名レイテンシーが重要な暗号資産取引では、この性能は許容範囲ですが、無視できないコストです。

閾値 ECDSA は、機関投資家向け金融分野で大規模に導入されています。Fireblocks は GG20 ベースの閾値 ECDSA を使用し、4 兆ドルを超える取引額を保護しています。Coinbase Prime は、閾値署名に基づく MPC カストディを使用しています。Qredo と Copper.co は、機関投資家向け資産管理のための閾値 ECDSA を提供しています。tss-lib Go ライブラリ（Binance が使用）と multi-party-sig（Coinbase が使用）は、主要なオープンソース実装です。

閾値 ECDSA において、Paillier 準同型暗号はどのような役割を果たすのでしょうか？

閾値 ECDSA では、どの参加者も完全な鍵を知らないまま、t 人の参加者が署名できます。ECDSA の非線形構造には、Paillier 準同型暗号を使った MtA 変換が必要です。GG18 がこのアプローチを先駆け、GG20 が悪意のある参加者に対する安全性を追加し、CGGMP21 が識別可能なアボートを追加しました。EdDSA/Schnorr は、FROST（2 ラウンド、信頼されたセットアップ不要）によって、より容易に閾値化できます。Fireblocks や Coinbase での実運用導入により、数兆ドル規模の資産が保護されています。