論文翻訳: Fast Multiparty Threshold ECDSA with Fast Trustless Setup

Abstract

しきい値署名スキームは \(n\) 人のプレーヤー間で分散署名を可能にし、サイズ \(t+1\) の任意のサブグループは署名できるが \(t\) 人以下のグループは誰も署名できない。これまでにも ECDSA 署名スキームに対する閾値スキームは存在していたが、我々は効率的でディーラーレスな鍵生成を用いて任意の \(t \le n\) マルチパーティ署名をサポートする最初のプロトコルを提示する。我々のプロトコルは従来のソリューションより高速であり通信複雑性も大幅に削減されている。また正直ではない多数派を持つ悪意のある敵対者に対しても安全であることを証明した。我々はこのプロトコルを実装し、効率的で現実的な配備に適していることを実証した。

• ¹ City University of New York rosario@cs.ccny.cuny.edu
• ² Princeton University goldfeder@cornell.edu

Table of Contents

1. Abstract
2. 1 導入
   1. 1.1 この方法の概要
   2. 1.2 悪意的敵対者ケースでの高価な ZK 証明の回避
   3. 1.3 実験的な結果
3. 2 事前準備
   1. 2.1 署名スキーム
   2. 2.2 しきい値署名
   3. 2.3 加法準同型暗号
   4. 2.4 頑強で曖昧なコミットメント
   5. 2.5 電子署名標準
   6. 2.6 Feldman's VSS プロトコル
   7. 2.7 仮定
4. 3 共有変換プロトコル
5. 4 我々のスキーム
   1. 4.1 鍵生成プロトコル
   2. 4.2 署名生成
   3. 4.3 ゼロ知識証明
   4. 4.4 セキュリティ証明
   5. 4.5 Simulating the key generation protocol
   6. 4.6 Signature generation simulation
   7. 4.7 Semi-correct executions
   8. 4.8 Simulation of a non semi-correct execution
   9. 4.9 Finishing up the proof
6. 5 Removing the ZK proofs from the \({\sf MtA}\) protocol
7. 6 Extensions
   1. 6.1 Other additively homomorphic schemes.
   2. 6.2 Other multiplicative to share conversions.
   3. 6.3 Simulation-Based Security
   4. 6.4 Deterministic Key Generation
8. 7 Implementation, Benchmarks, and Evaluation
   1. 7.1 Benchmarking the data complexity
   2. 7.2 Benchmarking signature generation time
9. 8 Conclusion
10. 9 Acknowledgments
11. References
12. A The ZK Proofs for the MtA protocol
    1. A.1 Range Proof
    2. A.2 Respondent ZK Proof for \({\sf MtAwc}\)
    3. A.3 Respondent ZK Proof for \({\sf MtA}\)
13. 翻訳抄

1 導入

しきい値署名スキームは \(n\) 個の当事者が単一の公開鍵に基づいて電子署名を発行する権限を共有できる。しきい値 \(t\) はプレーヤーの任意の \(t+1\) 部分集合が共同して署名できるが、それより小さい部分集合では署名できないように指定される。一般的に、既存の集中型署名スキームと互換性のある署名を生成することが目的である。しきい値スキームでは、鍵生成と署名アルゴリズムは当事者間の通信プロトコルに置き換えられるが、検証アルゴリズムは集中型の当事者が発行した署名の検証と同じである。

近年、特に ECDSA 署名のしきい値生成でこのトピックが注目されているが、これは主にビットコインや他の暗号通貨で ECDSA が使用されていることに起因している。実際 ECDSA の安全なしきい値署名スキームは、ビットコインにおいてトランザクションを認可するために使用されている秘密署名鍵の侵害による恒常的な盗難に対する有効な対策となるだろう。ビットコインを保護することはこれらの鍵を保護することと同じである。それらを単一の場所に保存する代わりに、鍵は分割されコンピュータのしきい値セットによって認証すべきである。これらのマシンのいずれか ─ またはしきい値未満のマシンだけの違反は、攻撃者がいかなる金銭を盗難したり鍵に関する情報を収集することもできない。

ビットコインが登場する以前の最善の ECDSA しきい値署名スキームは Gennaro らによる研究 [18] であったが、これにはかなりの後退がある。\(t\) 個のプレーヤーのセキュリティしきい値を実装するためには (つまり \(t\) 以下のプレーヤーでは署名できない)、少なくとも \(2t+1\) 個のプレーヤー間で鍵を共有する必要があり、署名には少なくとも \(2t+1\) 個のプレーヤーの参加が必要である。この制限によってすべての参加者の署名が必要となる \(n\)-of-\(n\) 共有が除外される。さらに鍵の共有を保持している多くのサーバをセットアップする必要があり、これはコストがかかるだろうし攻撃者の作業をある意味簡単にしてしまう (標的となるサーバがより多く、署名するために正直な参加者が \(2t+1\) 個必要だが攻撃者は鍵を盗難するために \(t+1\) サーバを侵害するだけで済む)。

これらの問題を解決する試みとして、Mackenzie と Reiter は Gennaro らのスキームによってカバーされていない 2-out-of-2 署名ケース (つまり \(t=1\) と \(n=2\)) に対する特化されたスキームを構築した [29]。最近ではより改善された 2-out-of-2 スキームが発表されている [12, 27]。しかしながら 2-out-of-2 共有は非常に限定的であり、特定のアプリケーションで必要とされるより柔軟な共有ポリシーを表現することができない。

Gennaro らは [17] ([4] の改良) でしきい値最適 (threshold optimal) の設定でより一般的な \((t,n)\) ケースを解決している。これは \(n \gt t+1\) であり、署名する必要があるのは \(t+1\) プレーヤーだけである。ただし、彼らのスキームもまた分散鍵生成のコストがとても高いという欠点を持っている。

我々の結果: 我々は ECDSA に対して [4, 17] よりも多くの重要な点で改善された新しいしきい値最適プロトコルを紹介する。新しいプロトコルは [4, 17] よりも速く、必要な通信も遥かに少なくて済む; 概念的にも簡素であり複雑な分散鍵生成プロトコルを必要としない (比較の詳細は後述する)。

同じ議事録に登場した並行研究で Lindell らは類似したプロトコルである効率的な鍵生成を備えたマルチパーティしきい値 ECDSA [28] を提示している。

1.1 この方法の概要

元 \(g\) によって生成される素数位数 \(q\) の任意の巡回群 \(\mathcal{G}\) 上で機能する "一般的な" DSA 署名アルゴリズムについて考える。これは任意のデータ列を \(Z_q\) へ定義するハッシュ関数 \(H\) と、\(\mathcal{G}\) から \(Z_q\) へ定義する別のハッシュ関数 \(H'\) を使用する。秘密鍵 \(x\) は \(Z_q\) 上の一様乱数として選択し、対応する公開鍵を \(y=g^x\) とする。メッセージ \(M\) に署名するために、署名者は \(m=H(M) \in Z_q\) を算出し、\(Z_q\) から一様乱数で \(k\) を選択して \(\mathcal{G}\) 上の \(R=g^{k^{-1}}\) と \(r=H'(R) \in Z_q\) を算出する。そして \(s=k(m+xr) \bmod q\) を計算する。\(M\) の署名は \((r,s)\) ペアであり、検証は \[ R' = g^{ms^{-1} \bmod q} y^{rs^{-1}\bmod q} \ \ \mbox{in} \ \ \mathcal{G} \] を計算して \(H'(R')=r\) であれば受け入れる。

DSA 署名を共有する技術的な困難は \(R\) を共同で計算する必要があることと、2 つのシークレット値 \(k, x\) を乗算する必要のある \(s\) を計算することによってもたらされている。[18] で示されているように、プレーヤー間で共有されているシークレット値に対して 2 つの乗算を行う方法を示すだけで十分である。[18] ではこれらの値は Shamir の秘密分散、つまり自由項 (free term) が秘匿されている次数 \(t\) の多項式上の点として共有される。乗算の効果は多項式の次数が倍化されることである。これは [18] の方法が少なくとも \(2t+1\) プレーヤーが参加することを必要としているかの理由を説明している。この問題を解決するために [29] は秘密鍵 \(x\) を \(x=x_1 \cdot x_2\) のように乗算的に共有する方法を採用しているが (このアプローチは [12, 27] でも採用している)、ただしこれは \(t\gt 2\) に一般化することが困難である。

[17] では異なるアプローチが取られた。これは、秘密鍵 \(x\) が公開鍵暗号スキーム \(E\) に基づいて暗号化され、プレーヤー間で共有される共有される \(E\) の秘密鍵であり \(x\) の秘密分散を効率的に提供する。\(E\) が相加的に同型暗号スキームであるなら (例えば Paillier の [31])、それらはいくつかの厄介なボトルネックを持つ合理的に効率的なプロトコルを構築することが可能であることを示している。その主たるものはプロトコルが相加的同型暗号 \(E\) に対して公開鍵/秘密鍵の共同生成を必要としていることである。Paillier を用いて \(E\) を具現化するとき、RSA モジュラスの分散生成を必要とする。この問題に対する対策は知られているが (例えば [23]) それらはスケーラブルや効率性とは程遠い。我々の知る限り [23] のプロトコルは悪意を持ったマルチパーティのケースに対しては実装されていない。このプロトコルについて我々が唯一知っているベンチマークでは、2 つの半正直な (semi-honest) ケースで 15 分であり [27]、悪意を持ったマルチパーティの設定ではかなり長い時間がかかると推測することができる。さらに [4, 17] の署名生成プロトコルでは長いメッセージと複雑な ZK 証明を必要とする。

この論文では、我々はマルチパーティ計算に対する SPDZ アプローチ [9] に触発されて異なる道筋を選択している。プレーヤー間で加算的に共有される 2 つのシークレット \(a\), \(b\)、つまり \(a=a_1+\ldots+a_n\) と \(b=b_1+\ldots+b_n\) とする。ここでプレーヤー \(P_i\) は \(a_i\) と \(b_i\) を保持しているものとすると、我々は \(c=ab\) の加算的共有を生成したいと考えている。\(ab=\sum_{i,j} a_i b_j\) であり、したがって \(ab\) の加算的共有を得るためには個々の項 \(a_i b_j\) の加算的共有を得ることで満たされることに注意。そのためには、2 つの当事者がシークレットの乗算的共有を同じシークレットの加算的共有に変換することを可能にする 2-party プロトコルを使用する。プレーヤーはこのプロトコルに対の方式で (pairwise fashion) 従って積 \(ab\) の加算的共有を取得する。

このアプローチを使用して、我々は一般的なマルチパーティ設定に対してシンプルでエレガントなしきい値 ECDSA プロトコルを構築する。プレーヤーたちは秘密鍵 \(x\) の \((t,n)\) Shamir 共有から開始する。\(t+1\) プレーヤーが署名をするとき、2 つのランダム値 \(k=\sum_i k_i\) と \(\gamma=\sum_i \gamma_i\) の加算的共有を生成し、前述の発想を使用して (自明に再構築される) \(\delta=k\gamma\) と (共有されたままの) \(\sigma=kx=\sum_i w\) の積の加算的共有を計算する。\(\gamma\) のローカル共有に公開値 \(\delta^{-1}\) を乗算することで、プレーヤーたちは \(k^{-1}\) の加算的共有³を得ることになる。このとき値 \(R\) はべき乗 \(R=\prod_i g^{\gamma_i \delta^{-1}}\) で簡単に計算できる。各プレーヤーは \(s_i=k_i m+w_i r\) と \(s=\sum_i s_i\) を保持していることから値 \(s\) はプレーヤー間で加算的に共有されている。

• ³これは Bar-Ilan と Beaver の有名な反転トリック[1]である。

1.2 悪意的敵対者ケースでの高価な ZK 証明の回避

[27] に従い、我々はプレーヤーによる悪意的な挙動を検出するために最小限の ZK 証明を使用する。

我々は代わりに "楽観的" なアプローチを取り、全員が正直であると想定してプロトコルを実行する。そしてプロトコルから逸脱したプレーヤーがいないかを検出するために結果の署名の有効性を確認する (署名が検証できないのであれば少なくとも 1 つのプレーヤーが指示に従わなかったのは明らかである)。

この時点ではまだプレーヤーの中の多数派が不正な可能性があって正しい署名を生成できるという保証はないため、プロトコルを中断または異常終了させる。これは、良い実行の場合だけでなく異常終了する実行の場合でも、良いプレーヤーによって明らかにされた値がどのような貴重な情報も絶対に漏らさないように計らわなければならないという証明に技術的な複雑さをもたらす。後で説明するように、共有 \(S_i\) が明らかにされる前に有効な署名を再構築していることを "分散的に" チェックする必要があるだろう。このチェックは Cramer-Shoup スキームに基づくしきい値 CCA セキュア暗号 (threshold CCA secure encryption) を構築するために [7] で同様の問題を解決した Canetti と Goldwasser の方法をいくらか彷彿とさせる。

Range Proofs. 不正行為を検出するための署名検証ステップを使用する場合でも、我々は共有変換プロトコル中に 2 つの比較的高価な ZK 証明を実行しなければならない:

• Pailler の暗号スキームで暗号化された値 \(a\) が "小さい" という "range proof"
• \(E\) を Pailler の暗号スキームとしたとき、\(c=E(x)\) および \(y=g^x\) であるような \(x\) を当事者が知っているという証明

後で説明するように、これらの ZK 証明を削除することはサーバ間で共有されている DSA 秘密鍵 (およびそれぞれの署名で使用されている乱数子 \(k\)) に関する情報が漏洩する攻撃が発生する。この情報は非常に限られているため、これらがなくてもプロトコルは依然として安全なままであると推測する (詳細はセクション 5 を参照)。

1.3 実験的な結果

我々は我々のスキームを実装し、鍵生成と署名プロトコルの両方が非常に効率的であることを発見した。

鍵生成プロトコルは実装が簡単でありながら非常に高速である (妥当なパラメータを選択しても 1 秒以下)。これは鍵生成プロトコルが実装されておらず、実際の実行時間を見積もることが困難な [4, 17] とは全く対照的である。

我々の署名プロトコルは非常に効率的でもあり、データ転送と実行時間の両方で過去の研究よりも大幅に改善されている。

効率的な鍵生成と署名プロトコルの組み合わせで、我々のスキームは現実に配備されるのに適している。完全なベンチマークと評価はセクション 7 で示す。

2 事前準備

Communication Model. プレーヤーの全てのペアを接続する point-to-point チャネルと同等のブロードキャストチャネルが存在すると仮定する。

The Adversary. プロトコルの記述から意図的に逸脱する可能性のある、確率的多項時間の悪意のある敵対者を想定する。この敵対者は最大 \(t\) 個のプレーヤーを破壊することができ、破壊した全てのプレーヤーの内部状態を知ることができる。以前のしきい値 ECDSA スキーム [4, 17, 18, 18] と同様に、我々は敵対者がプロトコルを開始する時点で破壊するプレーヤーが選択されていなければならない静的な破壊に限定する。静的な破壊に対して安全なプロトコルを適応性のある破壊に対して安全なプロトコルに変換するための標準的な手法 [6, 24] は存在するが、これらはオーバーヘッドを発生させるだろう。

我々は駆け込み (rushing) 敵対者を想定している。つまり、敵対者はあるラウンドの最後に発言することができ、特に正直な参加者のメッセージを見た後でメッセージを選択することができる。

我々は [4, 17] に従い (ただし [18] とは異なるが)、不誠実な多数派 (dishonest majority)、つまり、敵対者の破壊するプレーヤー数 \(t\) が最大 \(n-1\) となる可能性があると想定する。この場合、プロトコルが完了する保証はないため、我々はロバスト性、つまり不正な参加者が存在していたとしてもプロトコルを完了する機能を達成しようとはしない。

2.1 署名スキーム

電子署名スキーム \(\mathcal{S}\) は 3 つの効率的なアルゴリズムで構成されている:

• \(({\sf sk},{\sf pk}) \leftarrow {\sf Key\mbox{-}Gen}(1^\lambda)\), セキュリティパラメータを入力に取り、秘密署名鍵 \({\sf sk}\) と公開検証鍵 \({\sf pk}\) を結果として返すランダム化鍵生成アルゴリズム。
• \(\sigma \leftarrow {\sf Sig}(sk, m)\), 秘密鍵 \(sk\) と署名されるメッセージ \(m\) を入力に取り、署名 \(\sigma\) を結果に返すランダム化署名アルゴリズム。署名はランダム化されている可能性があるため、(訳注: 同一の \(sk\), \(m\) に対して) 複数の有効な署名が存在する可能性がある。我々は有効な署名の集合を \(\{{\sf Sig}(sk,m)\}\) と表記し \(\sigma \in \{{\sf Sig}(sk,m)\}\) である必要がある。
• \({\sf b} \leftarrow {\sf Ver}(pk,m,\sigma)\), 公開鍵 \(pk\)、メッセージ \(m\)、署名 \(\sigma\) を入力に取り、\(\sigma\) が \(pk\) に基づいて \(m\) の有効な署名であれば 1 となるようなビット \(b\) を出力する決定論的検証アルゴリズム。

署名スキームが安全であることを証明するために、[22] で導入されている選択メッセージ攻撃に対する実在的偽造不可能性 (EC-CMA; existential unforgeability against chosen message attacks) の標準的な概念を再掲する。

定義 1 (Existential unforgeability). \({\sf Key\mbox{-}Gen}\) が出力した公開鍵 \(pk\) と、選択した適応的選択メッセージの署名を受信できる署名アルゴリズム \({\sf Sig}(sk,\cdot)\) へのオラクルアクセス権限が与えられた PPT 敵対者 \(\mathcal{A}\) について考える。\(\mathcal{M}\) を \(\mathcal{A}\) が要求したメッセージ集合とする。電子署名スキーム \(\mathcal{S}=({\sf Key\mbox{-}Gen}, {\sf Sig}, {\sf Ver})\) は、\(\lambda\) が無視できる場合を除き、メッセージ \(m \not\in \mathcal{M}\) 上で署名を生成できるような PPT 敵対者 \(\mathcal{A}\) が居ない場合に存在的に偽造できない (existentially unforgeable) と言われる。

2.2 しきい値署名

しきい値秘密分散. 秘密 \(x\) の \((t,n)\)-しきい値秘密分散は、共有 \(x_1,\ldots,x_n\) から \(t+1\) 個を入力を取り秘密を出力するが、\(t\) 個以下の共有だけでは秘密に関するいかなる情報も明かさない効率的なアルゴリズムが存在するような \(n\) 個の共有で成り立つ。

しきい値署名スキーム. 署名スキーム \(\mathcal{S}=({\sf Key\mbox{-}Gen},{\sf Sig},{\sf Ver})\) について考える。\(\mathcal{S}\) に対する \((t,n)\)-しきい値署名スキーム \(\mathcal{TS}\) は、プレーヤーの少なくとも \(t+1\) 個による任意のグループの中で共同して署名を生成できるが、サイズが \(t\) 以下のグループではできないというような、\(n\) 個のプレーヤーのグループ \(P_1,\ldots,P_n\) 間で署名を分散することができる。より正式には \(\mathcal{TS}\) は 2 つのプロトコルで構成されている:

• \({\sf Thresh\mbox{-}Key\mbox{-}Gen}\), セキュリティパラメータ \(1^\lambda\) を入力に取る分散鍵生成プロトコル。各プレーヤー \(P_i\) は、公開鍵 \(pk\) と、\(P_i\) の秘密鍵の共有である秘密出力 \(sk_i\) を出力として受け取る。値 \(sk_1,\ldots,sk_n\) は秘密鍵 \(sk\) の \((t,n)\) しきい値秘密分散を構成する。
• \({\sf Thresh\mbox{-}Sig}\), 署名するメッセージ \(m\) を公開入力とし、同様に各プレーヤーからの秘密入力 \(sk_i\) を取る分散署名プロトコル。署名 \(\sigma\in\{{\sf Sig}(sk,m)\}\) を出力する。

\({\sf Thresh\mbox{-}Sig}\) によって出力される署名は中央化された署名プロトコルである \({\sf Sig}\) の下で有効な署名であることに注意。従って我々は中央化された検証アルゴリズム \({\sf Ver}\) を使用するため検証アルゴリズムのしきい値バリアントは特記しない。

一部のアプリケーションでは、信頼できるディーラーに各参加者の秘密鍵共有を生成させることが許される場合がある。この場合 \({\sf Thresh\mbox{-}Key\mbox{-}Gen}\) は実行されない。

[18, 19] に従い、我々は EU-CMA に類似したゲームベースのセキュリティの定義を示す。

定義 2 (Unforgeable threshold signature scheme [18]). \((t,n)\)-しきい値署名スキーム \(\mathcal{TS} = ({\sf Thresh\mbox{-}Key\mbox{-}Gen}, {\sf Thresh\mbox{-}Sig})\) は、あるプロトコル \({\sf Thresh\mbox{-}Key\mbox{-}Gen}\) と、攻撃者が適応的に選択した入力メッセージ \(m_1,\ldots,m_k\) およびそれらのメッセージの署名上のプロトコル \({\sf Thresh\mbox{-}Sig}\) のビューを考慮して、最大で \(t\) 個のプレーヤーを破壊する悪意的な敵対者が (\(\lambda\) 的に) 無視できない確率で任意の新しい (つまり過去に署名されていない) メッセージ \(m\) の署名を生成できない場合に偽造不可能 (unforgeable) と言う。

これは、Goldwasser, Micali と Rivest [22] によって定義された、選択メッセージ攻撃の下での実在的偽造不可能性の概念に類似したゲームベースのセキュリティ定義である。中央集権型の EU-CMA と異なり、敵対者には鍵生成プロトコルの破壊されたプレーヤーのビューと、それが選択したメッセージに対する署名プロトコルのビューが追加で与えられる。より強力なシミュレーションベースの定義も可能である ([17, 18, 27] を参照)。セクション 6.3 ではこのより強力なシミュレーションベースの定義を用いて我々のプロトコルの安全性を証明する方法を示す。

2.3 加法準同型暗号

我々のプロトコルは大きな整数 \(N\) を法として準同型である暗号スキーム \(\mathcal{E}\) に依存している。\(E_{pk}(\cdot)\) を公開鍵 \(pk\) を使用して \(\mathcal{E}\) の暗号アルゴリズムを表すとする。ある暗号文 \(c_1 = E_{pk}(a)\) と \(c_2 = E_{pk}(b)\) が与えられると、以下のように効率的に計算可能な関数 \(+_E\) が存在する: \[ c_1 +_E c_2 = E_{pk}(a + b \bmod{N}) \]

暗号文の加法演算子の存在は \(\times_E\) で表すスラカー倍化演算も意味する。ある整数 \(a \in N\) および暗号文 \(c = E_{pk}(m)\) に対して \[ a \times_E c = E_{pk}(am \bmod{N}) \]

非公式には、2 つのメッセージの暗号の確率分布が計算上区別できない場合に \(\mathcal{E}\) は意味的に安全であると言う。

Paillier の加法準同型暗号スキーム [31] を使用して我々のプロトコルを具現化し、ここで詳細を再掲する:

• 鍵生成: 等しい長さの 2 つの大きな整数 \(P\), \(Q\) を生成し \(N = PQ\) と設定する。\(\lambda(N) = lcm(P-1,Q-1)\) を \(N\) の Carmichael 関数とする。最後に序数が \(N\) の倍数となるような \(\Gamma \in Z_{N^2}^*\) を選択する。公開鍵は \((N,\Gamma)\)、秘密鍵は \(\lambda(N)\) である。
• 暗号化: メッセージ \(m \in Z_N\) を暗号化するには \(x \in_R Z_N^*\) を選択し \(c = \Gamma^m x^N \bmod{N^2}\) を返す。
• 復号化: 暗号文 \(c \in Z_{N^2}\) を復号化するには、\(L\) を \(L(u) = (u-1)/N\) として計算される集合 \(\{u \in Z_{N^2}: u = 1 \bmod{N}\}\) で定義された関数とする。そして \(c\) の復号化は \(L(c^{\lambda(N)}) / L(\Gamma^{\lambda(N)}) \bmod{N}\) として計算される。
• 準同型特性: ある 2 つの暗号文 \(c_1,c_2\in Z_{N^2}\) は \(c_1 +_E c_2 = c_1 c_2 \bmod{N^2}\) を定義する。\(c_i = E(m_i)\) であれば \(c_1 +_E c_2 = E(m_1 + m_2 \bmod{N}\) である。同様にある暗号文 \(c=E(m) \in Z_{N^2}\) と数値 \(a \in Z_n\) に対して \(a \times_E c = c^a \bmod{N^2} = E(am \bmod{N})\) である。

Paillier の暗号システムのセキュリティは \(N\)-余剰性決定的仮定 (\(N\)-resiouosity decisional assumption) [31] に依存している。これは大雑把に述べるとランダムな \(N\)-余剰 (\(N\)-residues) を \(Z_{N^2}^*\) 内のランダムな群元から区別することは不可能であるというものである。

2.4 頑強で曖昧なコミットメント

トラップドアコミットメントスキームは送信者が情報理論的な秘匿性を持ってメッセージにコミットすることを可能にする。つまり、コミットメントフェーズのある記録が与えられたとき、たとえ無限の計算能力を持っていたとしても、受信者はコミットされたメッセージを乱数と同等にしか推測することができない。一方でメッセージを開くときには、送信者はコミットされたメッセージに計算量的に束縛されるだけである。実際、このスキームでは知識があればどのような方法でもコミットを開くことができるトラップドア (trapdoor) が認められている (我々はこれをコミットメントの曖昧化 (equivocate) とも呼ぶことにする)。このトラップドアは効率的に計算することが難しいだろう。

正式な (非インタラクティブな) トラップドアコミットメントスキームは以下の特性を持つ 4 つのアルゴリズム \({\sf KG}\), \({\sf Com}\), \({\sf Ver}\), \({\sf Equiv}\) で構成されている:

• \({\sf KG}\) は鍵生成アルゴリズムであり、セキュリティパラメータ上でペア \(\{{\sf pk},{\sf tk}\}\) を出力する。ここで \({\sf pk}\) はコミットメントスキームに関連付けられた公開鍵、\({\sf tk}\) はトラップドアと呼ばれる。
• \({\sf Com}\) はコミットメントアルゴリズムである。\({\sf pk}\) とメッセージ \(M\) の入力上で \([C(M),D(M)]={\sf Com}({\sf pk},M,R)\) を出力する。ここで \(r\) はコイントスである。\(C(M)\) はコミットメントデータ列であり、\(D(M)\) はオープン時まで秘密にされているでコミットメントデータ列である。
• \({\sf Ver}\) は検証アルゴリズムである。\(C\), \(D\) および \({\sf pk}\) の入力上でメッセージ \(M\) もしくは \(\perp\) のどちらかを出力する。
• \({\sf Equiv}\) はトラップドア情報が与えられた時にどのような方法でもコミットメントを開くアルゴリズムである。\({\sf pk}\), データ列 \(M\) と、\([C(M),D(M)] = {\sf Com}({\sf pk},M,R)\) となるような \(R\)、メッセージ \(M' \ne M\)、データ列 \(T\) を入力に取る。もし \(T={\sf tk}\) であれば \({\sf Equiv}\) は \({\sf Ver}({\sf pk},C(M),D')=M'\) となるような \(D'\) を出力する。

送信者がコミットメントを開くことを拒否した場合、我々は \(D=\perp\) および \({\sf Ver}({\sf pk},C,\perp) = \perp\) と置けることに注意。トラップドアコミットメントは以下の特性を満たす必要がある:

• 正しさ: \([C(M),D(M)] = {\sf Com}({\sf pk},M,R)\) であれば \({\sf Ver}({\sf pk},C(M),D(M)) = M\) である。
• 情報理論的安全性: 全てのメッセージペア \(M\), \(M'\) に対して \(C(M)\) と \(C(M')\) の分布は統計的に近い。
• 安全なバインディング: 敵対者が \({\sf Ver}({\sf pk},C,D)=M\), \({\sf Ver}({\sf pk},C,D')=M'\) かつ \(M \ne M'\) となるような \(C\), \(D\), \(D'\) を出力するとき、敵対者 \(\mathcal{A}\) が勝利すると言う。全ての効率的なアルゴリズム \(\mathcal{A}\) に対して、\(\mathcal{A}\) がかつ確率はセキュリティパラメータ上で無視できる必要がある。

メッセージ \(m\) に対するコミットメント \(C\) が与えられた敵対者 \(\mathcal{A}\) が、\(m\) に対する \(C\) が開かれるのを見た後に、\(\mathcal{A}\) が関連するメッセージ \(m'\) のデコミットに成功するような別のコミットメント \(C'\) を作ることができないのであれば、そのコミットメントは頑強 (non-malleable) [13] である (これは実際には [10] で導入された開かれていることに関する頑強性の概念である)。

[10, 11] の頑強コミットメントスキームは、セキュリティが \(t=1\) でのみ保持される (すなはち敵対者は 1 つのコミットメントしか見ない) という意味で "同時な (concurrently)" セキュリティではないため我々の目的には適していない。

\(t \gt 1\) での頑強性のより強力な同時セキュリティは [8, 15, 30] で紹介されたスキームによって達成されており、そのどれもが我々のしきい値 DSA スキームで使用することができる。

ただし実際には、任意のセキュアなハッシュ関数 \(H\) を使用し、一様に選択された長さ \(\lambda\) の \(r\) に対して \(x\) に対するコミットメントを \(h = H(x,r)\) と定義することができる。\(H\) はランダムオラクルとして振る舞うと仮定する。我々の実装ではこの効率的なランダムオラクルバージョンを使用する。

2.5 電子署名標準

Digital Signature Algorithm (DSA) は Kravitz により 1991 年に提案され 1994 年に NIST によって電子署名標準 (DSS) として採用された [3, 26]。DSA の楕円曲線変種である ECDSA は近年、特に暗号通貨の分野で非常に普及している。

この論文で紹介するすべての結果は伝統的な DSA と ECDSA の両方に適用される。我々は [17] での一般的な G-DSA 表記を使用してこの結果を定義する。ここにそれを再掲する。

公開パラメータは素数位数 \(q\) の環 \(\mathcal{G}\)、\(\mathcal{G}\) の生成元 \(g\)、ハッシュ関数 \(H:\{0,1\}^* \to Z_q\)、および別のハッシュ関数 \(H': \mathcal{G} \to Z_q\) で構成される。

• 鍵生成: セキュリティパラメータを入力すると \(Z_q\) 内から一様にランダムに選択された秘密鍵 \(x\) を出力する。公開鍵 \(y=g^x\) が \(\mathcal{G}\) で計算される。
• 署名: 任意のメッセージ \(M\) を入力すると
  • \(m=H(M) \in Z_q\) を計算する
  • \(k \in_R Z_q\) を選択する
  • \(\mathcal{G}\) で \(R=g^{k^{-1}}\) と \(r = H'(R) \in Z_q\) を計算する
  • \(s = k(m+xr) \bmod{q}\) を計算する
  • \(\sigma = (r,s)\) を出力する
• 検証: \(M\), \(\sigma\), \(y\) を入力すると
  • \(r,s \in Z_q\) を確認
  • \(\mathcal{G}\) で \(R' = g^{ms^{-1} \bmod{q}} y^{rs^{-1} \bmod{q}}\) を計算
  • \(H'(R')=r\) のときに限り受理 (1 を出力)

伝統的な DSA アルゴリズムは \(q | (p-1)\) となるような大きな素数 \(p\), \(q\) を選択し、\(\mathcal{G}\) を \(Z_q^*\) の次数 \(q\) の部分群であるように設定することで得られる。この場合、\(\mathcal{G}\) の乗算演算は \(p\) を法とする乗算となる。関数 \(H'\) は \(H'(R) = R \bmod{q}\) と定義される。

ECDSA スキームは基数 \(q\) の楕円曲線上の点の群として \(\mathcal{G}\) を選択することによって得られる。この場合 \(\mathcal{G}\) の乗算演算は曲線状の群演算である。関数 \(H'\) は \(H'(R) = R_x \bmod{q}\) として定義され、ここで \(R_x\) は点 \(R\) の \(x\)-座標である。

2.6 Feldman's VSS プロトコル

秘密 \(\sigma \in Z_q\) を共有するために、Shamir のスキーム [35] ではディーラーが \(p(0)=\sigma\) となるような \(Z_q\) 上のランダムな次数 \(t\) 多項式 \(p(\cdot)\) を生成する。秘密分散はその多項式 \[ p(x) = \sigma + a_1 x + a_2 x^2 + \cdots + a_t x^t \bmod{q} \] である。

各プレーヤー \(P_i\) は秘密 \(\sigma_i = p(i) \bmod{q}\) を受け取る。

検証可能な秘密分散スキームでは、プレーヤーが秘密に一貫性があることを確認し一意の秘密を定義できるようにする補助情報が公開される。

Feldman's VSS は Shamir 秘密分散の拡張であり、ディーラーは全ての \(i \in [1,t]\) に対する \(v_i = g^{a_i}\) と \(v_0 = g^\sigma\) を \(\mathcal{G}\) で公開する。

この補助情報を使用して各プレーヤー \(P_i\) は \[ g^{\sigma_i} \overset{?}{=} \prod_{j=0}^t v_j^{i^j} \ \ \mbox{in} \ \mathcal{G} \] を検証することで秘密 \(\sigma_i\) の整合性を確認することができる。

この確認がどのプレーヤーにも適用されない場合、苦情を提起してプロトコルは終了する。これは、正直な過半数を仮定し不正直なプレーヤーが苦情を申し立てても回復できるという当初 Feldman VSS が提示していた方法とは異なる点に注意。しかし我々はこの論文で不正直な過半数を想定しているため、苦情が発生したらプロトコルは異常終了する。

Feldman のスキームは \(g^\sigma\) が漏洩するが、それ以外は漏洩しないことをシミュレーションの論議で示すことが出来る。ただしここでの詳細は省略する。

2.7 仮定

DDH. \(G\) を生成元 \(g\) とする素数位数 \(q\) の環とする。DDH 仮定は \(G^3\) 上で次の 2 つの分布が計算上区別できないことを示している: \(DH = \{(g^a,g^b,g^{ab}) \ \mbox{for} \ a,b \in_r Z_q\}\) と \(R = \{(g^a,g^b,g^c) \ \mbox{for} \ a,b,c \in_R Z_q\}\)

Strong-RSA. \(N\) を 2 つの安全な素数 \(p=2p'+1\) と \(q=2q'+1\) の積 \(N=pq\) とする。ここで \(p'\) と \(q'\) は素数である。\(\phi(N)\) を \(\phi(N)=(p-1)(q-1)=p'q'\) となるような \(N\) のオイラー関数として表記する。\(Z_N^*\) は 0 から \(N-1\) までの整数の集合とし \(N\) とは互いに素である。

\(e\) を \(\phi(N)\) と互いに素な整数とする。RSA 仮定 [33] は \(Z_N^*\) で \(e\)-根を計算することが不可能であると述べている。つまりランダムな元 \(s \in_R Z_N^*\) が与えられると \(x^e = s \bmod{N}\) となるような \(x\) を見つけることが困難である。

([2] で導入された) 強 RSA 仮定は \(Z_N^*\) でランダムな元 \(s\) が与えられたとき \(x^e = s \bmod{N}\) となるような \(x, e \ne 1\) を見つけることが困難であると述べている。この仮定は、敵対者が \(e\)-根を計算できる指数 \(e\) を自由に選択できるようにしているという点で従来の RSA 仮定と異なっている。

ここで正式な定義を与える。\(SRSA(n)\) を整数の集合とし、\(N\) は 2 つの \(n/2\)-bit の安全な素数の積とする。

仮定 1 . 全ての確率的多項時間敵対者 \(\mathcal{A}\) に対して以下の確率 \[ {\it Prob}[N \leftarrow SRSA(n); s \leftarrow Z_N^*: \mathcal{A}(N,s) = (x,e) \ \ s.t. \ \ x^e = s \bmod{N}] \] が \(n\) において無視できるのであれば強 RSA 仮定は保持されるという。

3 共有変換プロトコル

秘密の乗法的共有 \(x = ab \bmod{q}\) を考えることのできる 2 つの秘密 \(a,b \in Z_q\) をそれぞれ持っているアリスとボブについて考える。アリスとボブは、アリスが持っている \(a\) とボブが持っている \(b\) とで \(\alpha+\beta=x=ab \bmod{q}\) となるようなランダムな値である \(x\) の加法的秘密共有 \(\alpha,\beta\) を計算したいと考えている。

ここで過去の文献 (例えば [9, 25, 27, 29]) で何度も登場しているが我々の用途に合わせた加法的準同型スキームに基づいたプロトコルを示す。アリスは整数 \(N\) 上の加法的準同型スキーム \(\mathcal{E}\) に対する公開鍵 \(E_A\) に関連付けられていると仮定する。また \(K \gt q\) は後述する境界とする。

以下ではこのプロトコルを \({\sf MtA}\) (Multiplicative to Additive) 共有変換プロトコルと呼ぶ。このプロトコルでは \(B=g^b\) も公開されよいものとする。この場合、ボブに正しい値 \(b\) を使わせることを強制するために追加の確認が行われる。この拡張プロトコルを \({\sf MtAwc}\) (MtA "with check") と呼ぶ。

1. アリスは以下のようにプロトコルを初期化する。
   • ボブに \(c_A = E_A(a)\) を送る
   • レンジプルーフを使用して \(a \lt K\) であるという ZK を証明する
2. ボブは暗号文 \(c_B = b \times_E c_A +_E E_A(\beta') = E_A(ab + \beta')\) を計算する。ここで \(beta'\) は \(Z_N\) で一様にランダムに選択される。ボブは彼の共有を \(\beta = -\beta' \bmod{q}\) に設定し、以下のようにアリスに応答する。
   • \(c_B\) を送信する
   • ZK で \(b \lt K\) であることを証明する
   • \(B=g^b\) が公開されている場合のみ彼が \(B=g^b\) と \(c_B=b \times_E c_A +_E E_A(\beta')\) となるような \(b\), \(\beta'\) を知っているという ZK を証明する
3. アリスは \(c_B\) を復号化し \(\alpha'\) を得て \(\alpha = \alpha' \bmod{q}\) と設定する。

Correctness. 両方のプレーヤーが正直であり \(N \gt K^2q\) であると仮定する。そしてアリスが値 \(a' = ab + \beta' \bmod{N}\) を復号化することに注意。もし \(\beta' \lt N - ab\) ならリダクションの \(\bmod{N}\) は実行されないことに注意。このイベントを条件として、プロトコルは \(\alpha+\beta=x \bmod{q}\) となるような \(\alpha\), \(\beta\) を正しく計算する。

\(ab \le K^2\) かつ \(N \gt K^2q\) であるため、\(\beta' \gt N - ab\) は最大でも \(1/q\) の (つまり無視できる程度の) 確率で存在することになる。

Simulation. 我々はまずスタンドアロンプロトコルとしてレンジプルーフを使わずにセキュリティが証明できることを示す。実際、もし敵対者がアリスを破壊した場合、ボブのメッセージはその入力 \(b\) を知らなくてもシミュレーションができる。シュミレーション実行者はランダムな \(b' \in Z_q\) を選択しボブのように振る舞うだけである。このシミュレーションでアリスによって復号化されるメッセージの分布は、ボブが現実の \(b\) を使用した時に復号化されるメッセージと同一である。これは "ノイズ" \(\beta'\) が \(Z_N\) で一様に分布しているためである。

もし敵対者がボブを破壊した場合、アリスのメッセージは入力 \(a\) を知らなくてもシミュレートすることができる。実際、シミュレーション実行者は乱数 \(a' \in Z_N\) を選択してアリスのように振る舞うだけである。この場合暗号スキーム \(\mathcal{E}\) のセマンティックセキュリティにより、ボブの観点は現実のものと計算上区別することができない。

しかし、レンジプルーフが使用されていなければ、悪意のあるアリスまたはボブは大きな入力を選択することでプロトコルを "失敗" させることができる。スタンドアロンプロトコルとしては、当事者たちはリダクション \(\bmod{N}\) が行われたことすら認識しておらず、他の当事者の入力についての情報が漏洩することもないので問題とはならない。しかし、我々のしきい値 DSA プロトコルで使用された場合、この攻撃は署名検証の失敗を引き起こし、この失敗情報は他の当事者の入力のサイズとリンクしている。

アリスが入力 \(a' = q^2 + a\) でプロトコルを実行するケースを例として考える。もしボブの入力が "小さい" ならリダクション \(\bmod{N}\) は実施されずプロトコルが成功し、結果的に我々のしきい値 DSA プロトコルによって生成される署名は正しく検証される (\(a'=a \bmod{q}\) であるため)。しかしボブの入力が大きければプロトコルは失敗する。

このため我々はリダクション \(\bmod{N}\) が発生するかどうかを当事者に伝えるオラクルの存在下でのセキュリティを必要としているが、リダクションのような ZK "レンジプルーフ" は無視できる確率で発生することからセキュリティは保持される。

Remark. 別のアプローチ. 上記のプロトコルは圧倒的に正しく \(b\) を完全に隠蔽することができる。我々はこれを \(\beta'\) が \([0...N-K^2]\) で一様にランダムに選択されるように修正することができる。この分布は統計的には \(Z_N\) 上の一様分布に近いため (\(K \gt q\) であるため)、値 \(b\) は統計的な意味で隠蔽される。一方でこのプロトコルは常に正しい。

Remark. ZK 証明と modulus \(N\) のサイズについて. プロトコルで必要とされる ZK 証明には、[29] で提示された (そして既に [17] で使用されている) 類似の ZK 証明の簡略版を使用する。これらは強 RSA 仮定の下でセキュリティを保持する ZK アーギュメントである。さらにそれらは \(K \sim q^3\) を必要とし、次に \(N \gt q^7\) を必要とする。典型的なパラメータの選択では \(N\) は約 \(q^8\) であり、(\(q\) は通常 256 ビット長であり \(N\) は 2048ビット RSA モジュラスであるため) この要件は問題とならない⁴ことを指摘しておく。

• ⁴\(a,b \lt K\) のような単純なレンジプルーフの場合、\(N \sim q^3\) を設定する \(K \sim q\) を確立する Boudot の証明 [5] の変種を使用できる。この証明は、ボブの \({\sf MtAwc}\) プロトコルでとにかく必要とされる [17, 29] の証明よりも効率が低くなる。さらに前述したように、実際には \(N \gt q^8\) であるため \(N\) のサイズの改善は ECDSA とは無関係である。

4 我々のスキーム

個々で我々のプロトコルを詳述する。プレーヤーは DSA 署名スキームで使用される巡回群の入力 \(G\), \(g\) で実行される。各プレーヤー \(P_i\) は加法準同型暗号スキーム \(\mathcal{E}\) の公開鍵 \(E_i\) に関連付けられていると仮定する。

4.1 鍵生成プロトコル

• \({\sf Phase 1}\). 各プレーヤー \(P_i\) は \(u_i \in_R Z_q\) を選択する; \([KGC_i, KGD_i] = {\sf Com}(g^{u_i})\) を計算し \(KGC_i\) をブロードキャストする。各プレーヤー \(P_i\) は Paillier の暗号システムの公開鍵である \(E_i\) をブロードキャストする。
• \({\sf Phase 2}\). 各プレーヤー \(P_i\) は \(KGD_i\) をブロードキャストする。\(y_i\) を \(P_i\) によってデコミットされた値とする。プレーヤー \(P_i\) は \(y_i\) を "指数の自由項" (free term in the exponent) として値 \(u_i\) の \((t,n)\) Feldman-VSS を実行する。公開鍵は \(y=\prod_i y_i\) に設定される。各プレーヤーは \(n\) Feldman VSS プロトコル中に受信した秘密共有を追加する。結果の値 \(x_i\) は秘密鍵 \(x = \sum_i u_i\) の \((t,n)\) Shamir の秘密共有である。値 \(X_i=g^{x_i}\) が公開されていることに注意。
• \({\sf Phase 3}\). \(N_i=p_iq_i\) を \(E_i\) に関連付けられている RSA モジュラスとする。各プレーヤー \(P_i\) は Schnorr のプロトコル [34] を使用して自分が \(x_i\) を知っていること、そして (例えば [32] のような) 整数因数分解の知識の証明を使用して \(p_i\), \(q_i\) を知っていることを ZK で証明する。

4.2 署名生成

ここで、上記で説明した鍵生成プロトコルの出力と入力 \(m\) (署名されるメッセージ \(M\) のハッシュ) に基づいて実行される署名生成プロトコルを説明する。後者のプロトコルは \(t\)-out-of-\(n\) プロトコルである (したがって秘密鍵 \(x\) は \((t,n)\) Shamir 秘密分散で共有される) ことに注意。

\(S \subseteq [1..n]\) を署名プロトコルに参加している当事者の集合とし \(|S|=t\) と想定する。署名プロトコルでは一般的な \((t,n)\) 構造をとらずとも \((t,t)\) 秘密共有スキームを使用して任意の揮発的 (ephemeral) な秘密が共有できる。\(S\) の各プレーヤーに適切なラグランジュ係数 \(\lambda_{i,S}\) を使用することで \(x\) から自身に割り当てられた \((t,n)\) 共有 \(x_i\) と \(x\) の \((t,t)\) 共有をローカルで対応付けることができ、\(w_i=(\lambda_{i,S})(x_i\) つまり \(x = \sum_{i \in S} w_i\) となることに注意。\(X_i = g^{x_i}\) と \(\lambda_{i,S}\) が公開値であるため、全てのプレーヤーは \(W_i=g^{w_i}=X_i^{\lambda_i,S}\) が計算できる。

• \({\sf Phase 1}\). 各プレーヤー \(P_i\) は \(k_i\), \(\gamma_i \in_R Z_q\) を選択する; \([C_i, D_i] = {\sf Com}(g^{\gamma_i})\) を計算し \(C_i\) をブロードキャストする。\(k=\sum_{i \in S} k_i\), \(\gamma = \sum_{i \in S} \gamma_i\) と定義する。\[ \begin{eqnarray*} k \gamma & = & \sum_{i,j \in S} k_i \gamma_i \bmod{q} \\ k x & = & \sum_{i,j \in S} k_i w_i \bmod{q} \end{eqnarray*} \] に注意。
• \({\sf Phase 2}\). \(P_i\) と \(P_j\) はそれぞれ共有 \(k_i\), \(w_j\) を使って \({\sf MtAwc}\) を実行する。\(\mu_{ij}\) をこのプロトコルの終わりにプレーヤー \(P_i\) が受信した共有とする。対照に \(\nu_{ij}\) を \(P_j\) とする。つまり \[ k_i w_j = \mu_{ij} + \nu_{ij} \] プレーヤー \(P_i\) は \(\sigma_i = k_i w_i + \sum_{j \ne i} \mu_{ij} + \sum_{j \ne i} \nu_{ji}\) を設定する。\(\sigma_i\) は \(kx = \sum_{i \in S} \sigma_i\) の \((t,t)\) 加法共有であることに注意。
• \({\sf Phase 3}\). 各プレーヤー \(P_i\) は \(\delta_i\) をブロードキャストし \(\delta = \sum_{i \in S} \delta_i = k \gamma\) を再構築する。プレーヤーは \(\delta^{-1} \bmod{q}\) を計算する。

• \({\sf Phase 4}\). 各プレーヤー \(P_i\) は \(D_i\) をブロードキャストする。\(\Gamma_i\) を、Schnorr のプロトコル [34] を使って \(P_i\) となるような \(\gamma_i\) を知っているという ZK を証明する \(P_i\) によってデコミットされた値とする。プレーヤーは \[ R = \left[ \prod_{i \in S} \Gamma_i \right]^{\delta^{-1}} = g^{\left( \sum_{i \in S} \gamma_i \right) k^{-1} \gamma^{-1}} = g^{\gamma k^{-1} \gamma^{-1}} = g^{k^{-1}} \] と \(r = H'(R)\) を計算する。

• \({\sf Phase 5}\). 各プレーヤー \(P_i\) は \(s_i = mk_i + r\sigma_i\) を設定する。\[ \sum_{i \in S} s_i = m \sum_{i \in S} k_i + r \sum_{i \in S} \sigma_i = mk + rkx = k(m + xr) = s \] であることに注意。つまり、\(s_i\) は \(s\) の \((t,t)\) 共有である。

  • \(({\sf 5A})\) プレーヤー \(P_i\) は \(\ell_i, \rho_i \in_R Z_q\) を選択し、\(V_i = R^{S_i} g^{\ell_i}\)、\(A_i = g^{\rho_i}\)、および \([\hat{C}_i, \hat{D}_i] = {\sf Com}(V_i,A_i)\) を計算し、\(\hat{C}_i\) をブロードキャストする。
  • \(({\sf 5B})\) プレーヤー \(P_i\) は \(\hat{D}_i\) をブロードキャストし、\(V_i = R^{s_i} g^{\ell_i}\) と \(A_i^{\rho_i}\) となるような \(s_i\), \(\ell_i\), \(\rho_i\) を自身が知っていることを ZK で証明する。もし ZK 証明が失敗したらプロトコルは異常終了する。\(V = g^{-m} y^{-r} \prod_{i \in S} V_i\) (これは \(V=g^\ell\) である必要がある)、\(A = \prod_{i \in S} A_i\) とする。
  • \(({\sf 5C})\) プレーヤー \(P_i\) は \(U_i = V^{\rho_i}\) と \(T_i = A^{\ell_i}\) を計算する。これは \([\tilde{C}_i, \tilde{D}_i] = {\sf Com}(U_i, T_i)\) をコミットし \(\tilde{C}_i\) をブロードキャストする。
  • \(({\sf 5D})\) プレーヤー \(P_i\) は \(U_i\), \(T_i\) をデコミットするために \(\tilde{D}_i\) をブロードキャストする。\(\prod_{i \in S} [T_i] \ne \prod_{i \in S} U_i\) であればプロトルを異常終了する。
  • \(({\sf 5E})\) そうでなればプレーヤー \(P_i\) は \(s_i\) をブロードキャストする。プレーヤーは \(s = \sum_{i \in S} s_i\) を計算する。もし \((r,s)\) が正当な署名でなければプレーヤーは異常終了し、そうでなければ受理してプロトコルは終了する。

Phase 5 の背景にある直感を説明しよう。ZK の高価な証明を回避することによって不正確な署名を再構築可能性がある。このとき署名はチェックされ場合によっては拒否される。最後のフェーズへのナイーブなアプローチは、プレーヤーが \(s_i\) を明らかにし \(s=\sum_i s_i\) を再構築することである。しかし、それは証明によって明らかになることから、これは証明上安全ではない ─ その直感的な理由は敵対者が無効な署名を出力してプロトコルを失敗させると、良いプレーヤーが保持している値 \(s_i\) が敵対者に有用な情報を与える可能性があるためである⁵。単純には、最初に \(S_i = R^{s_i}\) をブロードキャストし DSA 検証アルゴリズムに従って \(\prod_i S_i = R^s = g^m y^r\) をチェックすることでこれを行うことが出来る。しかし同様の理由でこのステップは証明に失敗する。そこで我々のプロトコルでは、プレーヤーは \(R^{s_i\) をランダムな値 \(g^{\ell_i}\) でマスクする。\(V_i = R^{s_i} g^{\ell_i}\) とすると \(\prod_i V_i = R^s g^\ell\) であり従って \(V = g^\ell\) である。\(R^{s_i}\) のマスクを解除することになるのでプレーヤーは \(g^\ell\) を明らかにして \(V\) の正しさをチェックすることはできない。ここで我々は "合計" 値を \(U=g^{\ell\rho}\) に "ランダム化" する。この傍でプレーヤーは分散 "Diffie-Hellman" 交換を介して \(g^{\ell\rho}\) を計算する。このランダム化署名検証が実行されると共有 \(s_i\) を開放しても安全だが、署名が検証されなければプロトコルは異常終了し、良いプレーヤーによって保持されている値 \(s_i\) は明示的に明かされることはない。

• ⁵攻撃はしていないが、証明を機能させる方法も見当たらない。

4.3 ゼロ知識証明

ステップ (5B) において、プレーヤー \(P\) は \(V = R^s g^\ell\) と \(A = g^\rho\) を出力し、上記の関係を満たす \(s\), \(\ell\), \(\rho\) を知っていることを証明しなければならない。\(A\) に対する証明は古典的な Schnorr の証明である。\(V\) に対して、このタスクでの古典的な (honest-verifier) ZK 証明は以下のようになる:

• 証明者は \(a, b \in_R Z_q\) を選択し \(\alpha = R^a g^b\) を送信する。
• 検証者はランダムチャンレンジ \(c \in_R Z_q\) を送信する。
• 証明者は \(t = a + cs \bmod{q}\) と \(u = b + c \ell \bmod{q}\) で応答する。
• 検証者は \(R^t g^u = \alpha V^c\) であることをチェックする。

4.4 セキュリティ証明

この章で我々は以下を証明する

定理 1. 以下を仮定するとき、前章での我々のしきい値 DSA 署名スキームは偽造不可能 (unforgeable) である。

• DSA 署名スキームは偽造不可能であり;
• 強 RSA 仮定が保持されており;
• \({\sf KG}\), \({\sf Com}\), \({\sf Ver}\), \({\sf Equiv}\) が頑強性で等号化可能 (equivocable) なコミットメントスキームであり;
• DDH 仮定が維持されている

この定理の証明は従来のシミュレーションアーギュメントによって進められる。つまり、もし有意な確率でしきい値スキームで偽造を行う敵対者 \(\mathcal{A}\) が存在するならば、同様に優位な確率で集中型 DSA スキームも偽造できる偽造者 \(\mathcal{F}\) を構築することができることを示す。

そこで、\(\epsilon \ge \lambda^{-c}\) より大きな確率でしきい値スキームを偽造する敵対者 \(\mathcal{A}\) が存在すると仮定しよう。

我々はこの敵対者がプレーヤー \(P_2, \ldots, P_{t+1}\) をコントロールしており \(P_1\) が正直なプレーヤーであると仮定する。我々は、同時に (敵対者が正直なプレーヤーから多くのコミットメントを見ることのできる) 頑強性コミットメントを使用していることから、敵対者が \(t\) より少ないプレーヤーをコントロールし、少なくとも 1 つの正直なプレーヤーが存在するのであれば証明も成立することを指摘している。従って上記の仮定は一般性を失わない。

4.5 Simulating the key generation protocol

4.6 Signature generation simulation

4.7 Semi-correct executions

4.8 Simulation of a non semi-correct execution

4.9 Finishing up the proof

5 Removing the ZK proofs from the \({\sf MtA}\) protocol

6 Extensions

6.1 Other additively homomorphic schemes.

6.2 Other multiplicative to share conversions.

6.3 Simulation-Based Security

6.4 Deterministic Key Generation

7 Implementation, Benchmarks, and Evaluation

7.1 Benchmarking the data complexity

7.2 Benchmarking signature generation time

8 Conclusion

9 Acknowledgments

References

1. Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In: Proceedings of the eighth annual ACM Symposium on Principles of distributed computing. pp. 201–209. ACM (1989)
2. Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 480–494. Springer (1997)
3. Boneh, D.: Digital signature standard. In: Encyclopedia of cryptography and security, pp. 347–347. Springer (2011)
4. Boneh, D., Gennaro, R., Goldfeder, S.: Using level-1 homomorphic encryption to improve threshold dsa signatures for bitcoin wallet security. In: Latincrypt (2017)
5. Boudot, F.: Efficient proofs that a committed number lies in an interval. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 431–444. Springer (2000)
6. Canetti, R., Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Adaptive security for threshold cryptosystems. In: Annual International Cryptology Conference. pp. 98–116. Springer (1999)
7. Canetti, R., Goldwasser, S.: An efficient Threshold public key cryptosystem secure against adaptive chosen ciphertext attack. In: Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding. pp. 90–106 (1999)
8. Damgard, I., Groth, J.: Non-interactive and reusable non-malleable commitment schemes. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. pp. 426–437. ACM (2003)
9. Damg˚ard, I., Keller, M., Larraia, E., Miles, C., Smart, N.P.: Implementing aes via an actively/covertly secure dishonest-majority mpc protocol. In: International Conference on Security and Cryptography for Networks. pp. 241–263. Springer (2012)
10. Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. pp. 141–150. ACM (1998)
11. Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and non-interactive non-malleable commitment. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 40–59. Springer (2001)
12. Doerner, J., Kondi, Y., Lee, E., et al.: Secure two-party threshold ecdsa from ecdsa assumptions. In: IEEE Symposium on Security and Privacy. p. 0. IEEE (2018)
13. Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography,”. In: Proceedings of the 23rd Annual Symposium on the Theory of Computing, ACM (1991)
14. Fujisaki, E., Okamoto, T.: Statistical zero knowledge protocols to prove modular polynomial relations. In: Annual International Cryptology Conference. pp. 16–30. Springer (1997)
15. Gennaro, R.: Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In: Annual International Cryptology Conference. pp. 220–236. Springer (2004)
16. Gennaro, R., Goldfeder, S.: Fast multiparty threshold ecdsa with fast trustless setup. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. pp. 1179–1194. ACM (2018)
17. Gennaro, R., Goldfeder, S., Narayanan, A.: Threshold-optimal dsa/ecdsa signatures and an application to bitcoin wallet security. In: International Conference on Applied Cryptography and Network Security. pp. 156–174. Springer (2016)
18. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust threshold dss signatures. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 354–371. Springer (1996)
19. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust threshold dss signatures. Information and Computation 164(1), 54–84 (2001)
20. Gennaro, R., Micali, S.: Independent zero-knowledge sets. In: International Colloquium on Automata, Languages, and Programming. pp. 34–45. Springer (2006)
21. Gilboa, N.: Two party rsa key generation. In: Advances in Cryptology - CRYPTO ’99. pp. 116–129 (1999)
22. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17(2), 281–308 (1988)
23. Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T.: Efficient rsa key generation and threshold paillier in the two-party setting. In: Cryptographers’ Track at the RSA Conference. pp. 313–331. Springer (2012) Fast Multiparty Threshold ECDSA with Fast Trustless Setup 25
24. Jarecki, S., Lysyanskaya, A.: Adaptively secure threshold cryptography: Introducing concurrency, removing erasures. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 221–242. Springer (2000)
25. Keller, M., Pastro, V., Rotaru, D.: Overdrive: making spdz great again. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 158–189. Springer (2018)
26. Kravitz, D.W.: Digital signature algorithm (Jul 27 1993), uS Patent 5,231,668
27. Lindell, Y.: Fast secure two-party ecdsa signing. In: Annual International Cryptology Conference. pp. 613–644. Springer (2017)
28. Lindell, Y., Nof, A.: Fast secure multiparty ecdsa with practical distributed key generation and applications to cryptocurrency custody. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. pp. 1837–1854. ACM (2018)
29. MacKenzie, P., Reiter, M.K.: Two-party generation of dsa signatures. In: Annual International Cryptology Conference. pp. 137–154. Springer (2001)
30. MacKenzie, P., Yang, K.: On simulation-sound trapdoor commitments. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 382–400. Springer (2004)
31. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 223–238. Springer (1999)
32. Poupard, G., Stern, J.: Short proofs of knowledge for factoring. In: Public Key Cryptography, Third International Workshop on Practice and Theory in Public Key Cryptography, PKC 2000, Melbourne, Victoria, Australia, January 18-20, 2000, Proceedings. pp. 147–166 (2000)
33. Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
34. Schnorr, C.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161–174 (1991)
35. Shamir, A.: How to share a secret. Communications of the ACM 22(11), 612–613 (1979)

A The ZK Proofs for the MtA protocol

A.1 Range Proof

A.2 Respondent ZK Proof for \({\sf MtAwc}\)

A.3 Respondent ZK Proof for \({\sf MtA}\)

翻訳抄

1. Rosario Gennaro, Steven Goldfeder. Fast Multiparty Threshold ECDSA with Fast Trustless Setup, ACM Conference on Computer and Communications Security (CCS), 2018