セキュリティ

論文翻訳: Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme

Takami Torao 2002年の論文 #BLS署名 #署名分散 #しきい値署名 #マルチ署名 #ブラインド署名
  • このエントリーをはてなブックマークに追加
Alexandra Boldyreva
Dept. of Computer Science & Engineering, University of California at San Diego,
9500 Gilman Drive, La Jolla, CA92093, USA
aboldyre@cs.ucsd.edu
http://www-cse.ucsd.edu/users/aboldyre

Abstract

任意の (Computational Diffie-Hellman 問題は困難だが Decision Diffie-Helloam 問題は容易である) Gap Diffie-Hellman (GDH) 群で機能する堅牢で順行的 (proactive) なしきい値署名スキーム、マルチ署名スキームおよびブラインド署名スキームを提案する。我々の構造は最近提案された Boneh ら [8] の GDH 署名スキームに基づいている。GDH 群と基本スキームの手段となる構造により、我々のほとんどの構造は既存の類似構造よりもシンプルでより効率的で有用な特性を持っていることが分かる。対応するセキュリティ概念を使用して、適切な計算上の仮定の下で、提案された全てのスキームを証明付きでサポートする。

Table of Contents

  1. Abstract
  2. 1 導入
    1. 新しい GDH しきい値署名スキーム
      1. The new GDH threshold signature scheme
      2. Related Work
    2. 新しい GDH マルチ署名スキーム
      1. Related work
      2. The new GDH multisignature scheme
    3. 新しい GDH ブラインド署名スキーム
  3. 2 背景
    1. 署名スキームとそれらのセキュリティ
    2. Diffie-Hellman 問題と GDH 群
    3. GS, GDH 署名スキーム
  4. 3 堅牢な順行性しきい値 GDH 署名スキーム
    1. 通信モデル
    2. しきい値秘密分散
    3. しきい値署名とそれらのセキュリティ
    4. , しきい値 GDH 署名スキーム
    5. 順行性セキュリティの追加
  5. 4 GDH マルチ署名スキーム
    1. マルチ署名スキーム
    2. , GDH マルチ署名スキーム
    3. 署名のバッチ検証
    4. マルチ署名のセキュリティ
    5. マルチ署名スキームのセキュリティ
  6. 5 ブラインド GDH 署名スキーム
    1. BGS, ブラインド GDH 署名
    2. ブラインド署名のセキュリティ
    3. Chosen-target CDH 仮定
    4. BGS ブラインド署名スキームのセキュリティ
  7. 6 Acknowledgments
  8. References
  9. 翻訳抄

1 導入

最近 Boneh, Lynn and Shacham [8] は Computation Diffie-Hellman (CDH) 問題は難しいが Decisional Diffie-Hellman (DDH) 問題は容易である群を利用した新しい署名方式を提案した (3 つのランダムな群要素 が与えられたとき CDH 問題は を計算し、DDH 問題は 4 つの群要素 が全てランダムであるか有効な Diffie-Hellman タプルであるか、つまり という特性を持っているかを決定するよう求めることに注意)。[8] に従いこのような群を Gap Diffie-Hellman (GDH) 群と呼ぶ。GDH 群の最初の例は [29] にあり、GDH 群の存在と構成に関する詳細は [30, 6, 8] に見られる。GDH 群で機能する別の署名スキームは Lysyanskaya によって [32] で提案されている。これは [8] と違いランダムオラクルを使用しないが効率は劣る。

を素数位数 の GDH 群とし、 を の生成元とする。ほとんどの離散対数ベースのスキームと同様に [8] の署名スキーム の秘密鍵はランダムな元 であり公開鍵は である。メッセージ に署名するために を保持する署名者は署名 を計算する。ここで は任意の文字列を の元にマッピングするハッシュ関数であり、 は の恒等元を示す。[8] に従い とする。メッセージ の候補署名 の正当性を検証するため、検証者は単純に が正しい Diffie-Hellman タプルかを確認する。

Boneh ら [8] は、基礎になる群が GDH であると仮定すると、ランダムオラクルモデルでの選択メッセージ攻撃の下で署名スキーム が実在的偽造に対して安全であることを証明した。彼らはまた、いくつかの GDH 群でのこれらの署名の使用は長さが約 160bit の非常に短い署名になることを示している。この論文ではより魅力的な特性に加えて が様々な効率的な拡張をもたらすことを示す。より正確には我々は堅牢なしきい値順行性署名スキーム、マルチ署名スキーム、ブラインド署名スキームを提案する。GDH 群と基本スキームの洗練された構造のおかげで、ほとんどの構造は既存の同様の構造よりも単純で効率的で有用な特性を持っていることが分かった。対応するセキュリティの概念を使用して、適切な計算上の仮定の下で、提案する全てのスキームを証明付きでサポートする。

新しい GDH しきい値署名スキーム

-しきい値暗号アプローチ [9, 14, 16, 43] の背後にある考え方は単一障害点を除去するために パーティ間で秘密情報 (例えば秘密鍵) と計算 (例えば署名生成や復号化) を分散することである。目標は、最大 (しきい値) 個のパーティが故障する可能性のあるアクティブな敵対者が存在する状況で、 以上のパーティの任意の部分集合が共同で秘密を再構築し、セキュリティを維持しながら計算を実行できるようにすることである。しきい値暗号に関する研究のレビューは [15] に示されている。

しきい値署名スキームでは、信頼できるディーラーの補助や、または全てのパーティ間で対話型プロトコルを実行することによって秘密鍵が 個のパーティに配布される。あるメッセージ に署名するために 以上のパーティの任意の部分集合が秘密分散を使用して対話的な署名生成プロトコルを実行することで の署名が出力される。しきい値署名スキームのセキュリティ概念は、秘密鍵から何らかの情報を得たり、それらが選択した新しいメッセージ上に有効な署名を偽造できるような 個のパーティを破損する多項式時間の敵対者 (polynomial-time adversary) が存在しない必要がある。しきい値署名スキームの重要な特性は堅牢性である。これは、プロトコルから逸脱した 個のパーティであっても有効な署名を生成することを妨害することができないことを要求する。しきい値署名スキームの別の有用な特性は順行性 (proactivness) [37, 13] (または秘密分散の定期的な更新) である。この目的は、いくつかの場所への侵入を何度か試みることによって秘密の情報を蓄積しようとする敵対者からシステムを防御することである。一般的に、しきい値署名の主な目的は次の特性を証明可能に達成することである: 可能な限り高いしきい値 をサポートすること、信頼できるディーラーの使用を回避すること、堅牢で順行性であり、計算、インタラクション、分散の長さに関して可能な限り効率的であること。

The new GDH threshold signature scheme

セクション 3 では任意の GDH 群で機能するしきい値署名スキーム TGS を提案する。これは [8] の GDH 署名スキームに基づいている。我々のしきい値 GDH 群署名スキームは任意の 個の悪意のあるパーティを許容することができる。これは最適な結果である。この鍵生成プロトコルは信頼済みディーラーを必要としない。署名生成プロトコルはインタラクションやゼロ知識証明を必要とせず、様々なしきい値スキームに関する他の難しい問題を回避する署名生成プロトコルのオーバーヘッドはベースのスキームのオーバーヘッドと比較して最小限である。分散は短く、その長さはパーティの数に依存しない。署名分散生成プロトコルは基本的にベースのスキームの署名アルゴリズムであり、署名の再構築には分散の乗算のみを必要とする。セキュリティの結果は定理 2 に示している。この証明はランダムオラクルモデルにおいてのみであるが、後者 (どこ?) がベースの署名スキームのセキュリティ証明に使用されているためである。また我々は [26, 25] の一般的な方法を使用して我々のスキームにどのように順行的なセキュリティを追加できるかを示している。

しきい値署名には [16, 24, 17, 19, 41, 21, 44] など数多くのスキームが存在する。[16, 24] の提案はセキュリティ証明が欠落しており、[16, 17] は堅牢ではなく、[19, 41] は堅牢で順行性だが多くのインタラクションを必要とする。我々のスキームを Gannaro ら [21] のしきい値 DSS 署名スキーム、Shoup [44] のしきい値 RSA スキームと比較する。

[21] で提案されているしきい値 DSS 署名は堅牢であり、信頼済みディーラーが不要でランダムオラクルの仮定なしでセキュリティの証明を持っている。これは、2 つの秘密分散をそれらの秘密の積の分散に結合したり、この秘密の特定の分散を与える分散の逆数の分散を生成するといった技術的な困難を伴う。堅牢性を達成するために著者らは Berlekamp and Welch [4] の誤り訂正手法を使用している。その結果、しきい値 DSS は悪意のあるパーティを のみしか許容できず、しきい値署名生成プロトコルは多くのインタラクションを必要とし、しきい値スキームの複雑性は基本の署名スキームに関連して大幅に増加している。この方式は [26, 25] の方法に従って順行性にすることができる。

[44] の堅牢なしきい値 RSA 署名スキームはランダムオラクルモデルで安全であることが証明されている。 の悪意のあるパーティを許容でき、その署名生成アルゴリズムは非対話型である。しかしこれは鍵生成プロトコルに信頼済みディーラーを必要とする。公開鍵は 2 つの安全な素数の積である RSA モジュラスを使用する。このプロトコルは堅牢性を実現するためランダムオラクルにおけるゼロ知識証明を利用する。順行性化は [44] では考慮されない。

新しい GDH マルチ署名スキーム

マルチ署名スキームとは何かを直感的に理解するために、まずこの概念を非公式に論議して他の概念と比較する。

マルチ署名スキームによって、プレーヤー集合の部分集合が共同でドキュメントに署名できるようになるため、検証者は部分集合の各メンバーが署名に参加したことを確証することができる。この非公式の定義を満たす自明なソリューションは以下の通りである。結果として生成されるマルチ署名は、部分集合の説明と、部分集合の各メンバーが自身の秘密鍵を使用して算出した通常の署名を単純に連結したものである。実際この簡単なスキームはセクション 4 で正規化するセキュリティ要件を満たすだろう。ただし、その主な欠点は部分集合のユーザ数とともに線形に増大する署名の長さと検証時間である。

マルチ署名スキームはいくつかの理由でしきい値署名とは違っている。マルチ署名の目標は、ある部分集合の各メンバーがメッセージに署名し、そしてその部分集合のサイズを任意にできることを証明することであるが、一方で後者の設定では十分なサイズの部分集合がメッセージに署名したことを証明することである。この最小サイズはスキームのパラメータで事前に知らされておく必要がある。マルチ署名とは対照的にしきい値署名は個々の署名者の身元を明らかにしない。もう一つの違いは、しきい値署名方式の検証プロトコルが署名者の現在の部分集合に依存しないということである。マルチ署名はグループ署名 [13, 10] やリング署名 [42] とは異なり、グループの全てのメンバーがグループ全体にわたって有効な署名を生成できる。後者の 2 つの設定では署名者は検証者に対して匿名のままである。グループ署名設定には署名者の ID を識別できるグループマネージャと呼ばれるサードパーティも存在する。

マルチ署名は [28] で導入されており、[24, 31, 27, 34, 35, 36, 33] などの多くの研究のトピックとなっている。[35, 36] のスキームは署名者の部分集合をサポートしていない。これらはグループの各プレーヤーがドキュメントに署名する場合にのみ許可する。[28, 34] のソリューションはあまり効率的ではない: マルチ署名の生成と検証の時間はプレーヤーの数に比例して増加する。最も重要なのは最近の Ohta と Okamoto の研究、そして Micali らの研究 [36, 33] までマルチ署名に対するセキュリティの正式な概念はなく、従って証明可能でセキュアなマルチ署名スキームが存在しなかったことである。その結果 [31, 24] の提案は攻撃が成功した。[36] のセキュリティ概念は鍵生成中の敵対的攻撃の可能性を考慮していないため十分に強力ではない。

Micali ら [33] はマルチ署名に対するセキュリティの強い概念を最初に形式化した (彼らは "accountable-subgroup multisignatures" と呼んでいる)。彼らは [36] で Ohta and Okamoto によって最初に提案された Schnorr 署名に基づくマルチ署名スキームを修正しそのセキュリティを証明した。セキュリティのモデルと [33] のマルチ署名スキームは署名者 の部分集合が事前に知られていることを前提としている。各署名者は署名者 の現在の部分集合の全ての参加者を知っている必要があり、その説明もハッシュ化されメッセージと共に署名される。[33] の著者は、署名分散が算出された後に部分集合の構成を決定できる証明可能な安全なマルチ署名スキームを見つけることは興味深い未解決の問題であると述べている。

独立した研究で Boneh ら [7] はGS 署名スキームに基づく新しい集約署名スキームを提案した。マルチ署名とは異なり、集約署名は異なるメッセージの複数の署名をユーザのグループが集約できるようにする。[7] のスキームは双線形写像によって提供される特別な構造を持つ GDH 群を必要とする。

The new GDH multisignature scheme

セクション 4ではマルチ署名スキームの正確な定義とそれらのセキュリティを示す。我々のセキュリティモデルは [33] のセキュリティの単純化したモデルと非常に似ているが、より一般的であり、署名者の部分集合を事前に知っておく必要があるという制限がない。次に、我々は新しい GDH マルチ署名スキーム MGS を提案する。これは GDH 群で機能する。我々の MGS スキームは [33] で述べられている未解決の問題を解決する: 署名者の部分集合に関する事前の知識を必要とせず、証明可能な安全性を持っている。我々はセキュリティの結果を延べて [5] で証明を提供する。さらに MGS はマルチ署名生成プロトコルに 3 ラウンドの通信を必要とする [33] の一つよりもより効果的である。MGS はたった 1 ラウンドのみを必要とし、それは基本的に非対話型である。それらのスキームと同様に、MGS の署名の長さと検証の時間は部分集合の数には依存しておらず、基本の署名スキームとほぼ同等である。事実、我々のマルチ署名スキームの各署名分散は標準の GDH 署名である。[33] のスキームでは直前の署名プロトコルが完了するまで署名者が新しい署名プロトコルを開始することはできない。これはそれらのセキュリティの証明が並行性と互換性のない巻き戻し (rewinding) を行っているためである。我々のスキームは証明が巻き戻しを使用しないだけではなく主に署名プロトコルが非対話的であるためそのような制限はない。

マルチ署名スキーム MGS の基礎となるアプローチを使用して異なる公開鍵の下で同じメッセージの GDH 署名の効率的なバッチ検証を使用できることに注意。

新しい GDH ブラインド署名スキーム

ブラインド署名はデジタル通貨スキームの基本的なツールである。ブラインド署名プロトコルを使用するとユーザは銀行からデジタルコイン、つまり銀行によって適切に署名されたトークンを取得できる。ブラインド署名プロトコルの目標はユーザが署名者から署名を得られるようにすることである。これにより、署名者は署名したメッセージに関する情報を学習せず、ユーザは署名者との 1 回の対話後に複数の有効な署名を得ることはできない。Chaum [11] は RSA に基づくブラインド署名スキームを最初に提案した。しかし、それは最近になってやっと Bellare ら [2] によって安全であることが証明された。この時間差の理由は、標準の RSA の仮定に基づいて Chaum のスキームのセキュリティを証明することは不可能に見えるためである。[2] で取られたアプローチは、新しいもっともらしい計算上の仮定 (the new plausible computational assumption)、つまり "chosen-target-one-more-RSA-inversion" を導入し、この仮定に基づいて Chaum の RSA ブラインド署名のセキュリティを証明することだった。[2] で著者らはこの仮定の類似体を一方関数の任意のファミリーに対して定式化できることを示唆していた。

セクション 5 では GDH 群で機能する新しいブラインド署名スキーム BGS を定義する。このプロトコルは RSA ブラインド署名プロトコルに非常に似ている。つまり、ユーザはメッセージのハッシュにランダムな群元を乗算し、それを銀行に提出し、その後に公開鍵と乱数因子 (random factor) の知識を使用して銀行から得た署名を "ランダム化解除" (derandomize) する。BGS のセキュリティを証明するために我々は [2] のアプローチに従い、新しい計算問題である Chosen-target Computational-Diffie-Hellman 問題を定義する。[5] では Chosen-target CDH 仮定の下でブランド署名 BGS スキームのセキュリティを証明する。

2 背景

署名スキームとそれらのセキュリティ

署名スキーム は 3 つのアルゴリズムで構成されている。ランダム化された鍵生成アルゴリズム はグローバル情報 を取得し、秘密鍵と公開鍵のペア を出力する。グローバル情報は、例えばセキュリティパラメータ、群やその生成元の詳細、およびハッシュ関数の詳細を含むことができる。我々はこれらのパラメータを誰が生成するかには焦点を当てておらず、それらがパブリックに利用可能であると想定している。(おそらく) ランダム化された署名生成アルゴリズム は署名するメッセージ とグローバル情報 、秘密鍵 を受け取り、署名 とともに を出力する。決定論的検証アルゴリズム は公開鍵 、メッセージ 　と署名 を取り、署名が有効な場合は 1 (accept)、そうでない場合は 0 (reject) を出力する。ランダムオラクルモデル [1] では署名アルゴリズムと検証アルゴリズムの両方がランダムハッシュオラクルにアクセスできる。通常 である。一般的な要件は全ての に対して となることである。

署名スキームのセキュリティで広く受け入れられている概念は選択メッセージ攻撃 (chosen-message attack) [23] の下での偽造不可能性である。この論文の完全版 [5] でランダムオラクルモデルに調整されたこの概念を思い出そう。

ここで [8] の基本的な署名スキームを思い出そう。これは Gap-Diffie-Hellman 群を使用するため、最初に後者の定義を提供する。

Diffie-Hellman 問題と GDH 群

を素数位数 の乗法群とする。 における以下の 2 つの問題を考慮する。

Computational Diffie-Hellman (CDH) 問題. の 3 つのランダムな元 を与えて を計算する。

Decisional Diffie-Hellman (DDH) 問題. の 4 つの元 を与えると、それらは等しい確率で の全てのランダムな元であるか、 の特性を持つかのいずれかであり、前者の場合 0、そうでない場合 1 を出力する。

上記で定義した特性を持つ の 4 つの元を有効な Diffie-Hellman (DH) タプルと呼ぶ。

ここで GDH 群を定義することができた。それらは基本的に CDH 問題が難解な群だが、DDH 問題は簡単である。

定義 1 . DDH 問題を解く効率的なアルゴリズム が存在し、CDH 問題を解く多項式時間 ( ) アルゴリズムが存在しない場合、素数位数群 は GDH 群である。

GDH 群の存在と構成の詳細については [6, 8, 29, 30] を参照。

GS, GDH 署名スキーム

を GDH 群とする。 をハッシュ関数ファミリとし、その各メンバーが任意の長いデータ列を にマップし、 をこのファミリのランダムなメンバーとする。グローバル情報 は の生成元 と の詳細を含んでいる。 のアルゴリズムは次の通り。

  • : を として解析する。ランダムに を選択し を計算する。 を返す。
  • : を として解析する。 を計算する。 を返す。
  • : を と解析する。もし であれば 1 を返し、そうでなければ 0 を返す。

[8] で著者らは以下の結果を述べて証明している。

定理 1 . を GDH 群とする。 はランダムオラクルモデルにおける安全な署名スキームである。

3 堅牢な順行性しきい値 GDH 署名スキーム

我々は堅牢かつ順行性で信頼済みディーラーを必要としない GDH 署名スキームのしきい値バージョンを提示する。基本スキームの構造により RSA, DSS な多くの標準署名スキームのしきい値バージョンを作成しながら、克服する必要がある多くの困難を回避できるため、構築は非常に簡単である。

ここでしきい値署名スキームと基本設定、概念を思い出そう。

通信モデル

通常、我々のスキームの参加者は のプレーヤー である。全てのプレーヤーはブロードキャストチャネルと安全な point-to-point チャネルによって接続されている。

しきい値秘密分散

この集合の任意の 個の値が に関するいかなる情報も明らかにせず、この集合の任意の 個の値を入力として取り を出力する効率的なアルゴリズムが存在する場合、値 の集合は -しきい値秘密分散 (threshold secret sharing) であると言う。これを と記述する。

しきい値署名とそれらのセキュリティ

を署名スキームとし を関連するグローバル情報とする。対応する -しきい値署名スキーム は 3 つのアルゴリズムで構成されている。ここで検証アルゴリズムは のものと同じである。ランダム化された分散しきい値鍵生成アルゴリズム は を取りプレーヤー によって実行される対話型プロトコルである。このプロトコルは公開鍵 を返し、各プレーヤー のプライベート出力は となるような値 である。ここで は に対応する秘密鍵である。 は の出力と同じ分布を持つ を主力する場合、正常に完了する (complete successfully) という。分散された可能性のあるランダム化されたしきい値署名生成アルゴリズム はプレーヤーの部分集合によって実行される対話型プロトコルである。ここで各プレーヤー の入力はメッセージ 、グローバル情報 、そしてプレーヤーのプライベート入力 である。このアルゴリズムは署名分散生成と署名再構築という 2 つの対話型プロトコルで構成されると見なすことができる。署名分散生成プロトコルの最後に各プレーヤーはその署名分散を出力する。そして全ての署名分散は署名再構築プロトコルを使用して結合される。アルゴリズムの出力はメッセージ署名ペア である。 は全ての に対して であるような を出力するならば正常に完了する。

定義 2 . をグローバール情報、 を署名スキーム、 を対応するしきい値署名とする。 は以下の条件を満たすとき安全で堅牢なしきい値署名スキームと呼ばれる:
  1. 偽造不可能性. を与えられた多項式時間の敵対者は、 個までのプレーヤーを故障させることができてプロトコル の観点を与えられたときに後者が敵対者の選択した入力メッセージ上で実行されたとしても、 が の公開入力として敵対者によって提出されていないように、有効な ペアを生成することができる。
  2. 堅牢性. 個のプレーヤーまで故障することが可能な全ての多項式時間の敵対者に対して、プロトコル は正常に完了する。

上記の定義における故障とは、攻撃者が事前に故障させたいプレーヤーを選択し、故障したプレーヤーの計算を何らかの方法で変更し、プライベート入力を見ることができることを意味する。上記の定義がランダムオラクルモデルに合わせて調整されている場合、全てのパーティにランダムハッシュオラクルのアクセスが与えられている。

, しきい値 GDH 署名スキーム

を GDH 群、 をグローバル情報、 をセクション 2 で定義した GDH 署名スキームとする。しきい値 GDH 署名スキーム に対応するアルゴリズム は以下のように定義される。

はまさに Gennaro ら [22]1 の離散対数に基づくシステムのための分散鍵生成プロトコル DKG である。ペアの集合 によって共同で実行される。これは を入力に取り公開鍵 を出力する。各プレーヤー に秘密出力は となるような分散 である。ここで である。 プレーヤーの任意の部分集合 はよく知られた方法のラグランジュ補間 を使用して を再構築できる。ここで は集合 の適切なラグランジュ係数である。[22] が示すように、各 に対して値 は公開されている有効な情報から算出することができる。従ってこれらの値は公開的に有効であり堅牢性を達成するために使用すると想定する。

の署名分散生成プロトコルを実行するために、 を超えるプレーヤーの任意の部分集合における各プレーヤー は、メッセージ とその分散 を入力に取り、署名分散 を算出して をブロードキャストする。署名再構築プロトコルは任意のプレーヤーまたはプレーヤーの集合によって実行することができる。簡略化のためある指定されたプレーヤー によって行われると仮定する。堅牢性を達成するため はそれぞれの に対して を確認する。これが成立しない場合、対応するプレーヤーから新しい出力が要求されるか、または悪意があると見なされる。 が の正直なプレーヤーの集合であると仮定すると、 は結果の署名 を算出する。ここで は集合 に対する公開的に知られている適切なラグランジュ係数である。プロトコルの出力は となる。

定理 2 . を GDH 群とする。このとき は、 プレーヤーを故障させることができる敵対者に耐性を持つ、ランダムオラクルモデルの安全なしきい値署名スキームである。

上記定理の証明の完全版は論文 [5] で行われている。

順行性セキュリティの追加

順行性アプローチの考え方は、ある期間に (しきい値より小さい) いくつかの分散を学習した敵対者によって得られた情報が、未来の期間に行われる敵対者の次の攻撃で役に立たないように、秘密の分散を定期的に更新することである。順行性秘密分散アルゴリズム PSS は [25] で提案されている。PSS の適用を簡素化するため [25] は PSS プロトコルの助けを借りた順行性化のためのしきい値署名スキームの用件を述べている。つまり著者らは、離散対数ベースの堅牢なしきい値署名スキームであれば、PSS プロトコルを使用するときに堅牢なしきい値署名スキームのセキュリティが保持されることを保証している。このしきい値鍵生成プロトコルは公開鍵 に対応する秘密鍵 の Shamir 秘密分散を実装し、検証情報 を出力する。ここで はプレーヤーの秘密分散であり、しきい値署名プロトコルはシミュレーション可能である。TGS はこれら全ての要件を満たしていることに注意 (上記の検証情報は によって明示的に出力されるのではなく、公開的に有効な情報を使用して算出できることを思い出そう)。従って TGS は PSS と [26, 25] の方法を使用して順行性化することができる。我々は、各分散の更新後に PSS が検証情報を出力するため、署名分散の検証は以前と同様に実行できることを付け加えておく。

ここで TGS の特性を簡単に要約する。これは堅牢であり任意の の悪意のあるパーティーに耐性を持つ。その鍵生成プロトコルは信頼済みディーラーを必要としない。その署名分散生成プロトコルは基本的にベースとするスキームの署名アルゴリズムであり、署名再構築は分散の乗算のみを必要とする。従って署名生成プロトコルはインタラクションや任意のゼロ知識証明を必要とせず、ベースとなるスキームと比較して最小限のオーバーヘッドを持つ。分散は短く、その長さはパーティの数に依存しない。我々はまた順行性なセキュリティを我々のスキームに追加する方法も示した。セクション 1 ではこの新しい GDH しきい値署名スキームをいくつかの既存の設計と比較している。

  • 1 我々はある秘密の Shamir 秘密分散 [43] を生成する信頼済みディーラーを必要としない検証可能なしきい値鍵生成アルゴリズムに興味がある。あるしきい値署名スキーム、例えば [21] で提案されているしきい値 DSS は Pedersen [38] の分散鍵生成プロトコル (DKG) を使用する。後者のプロトコルの背景にある直感は、各プレーヤーがディーラーとして機能するように Feldman の検証可能な秘密分散プロトコル [18] を 並列で実行することである。しかし [22] では [38] の DKG の弱点を指摘している。つまり、故障した敵対者が分散された秘密鍵の配布を操作することでプロトコルが正しく完了することを妨害する可能性がある。[22] の DKG プロトコルは [38] のプロトコルと類似した考え方に基づいており、同等の複雑さを持つが、後者の弱点を確実に修正している。

4 GDH マルチ署名スキーム

マルチ署名スキーム

を プレーヤーの集合とする。 をグローバル情報のデータ列とする。マルチ署名スキーム のアルゴリズムは以下のように定義される。ランダム化鍵生成アルゴリズム はグローバル情報 を取り秘密鍵と公開鍵のペア を出力する。各プレーヤー は を実行し、その結果秘密鍵と公開鍵のペア を得る。ランダム化マルチ署名生成アルゴリズム はおそらくプレーヤーの任意のサブセット によって実行される対話型プロトコルである。各 の入力はメッセージ 、グローバル情報 とプレーヤーの秘密鍵 である。アルゴリズムの出力はメッセージと部分集合 の詳細、マルチ署名で構成されるタプル である。決定論的検証アルゴリズム は , , と の全てのプレーヤーの公開鍵、 を取り 1 (accept) または 0 (reject) を出力する。

メッセージに署名するために必要な部分集合を決定することは特定のアプリケーション次第である点に注意。マルチ署名の有効性を検証する人は、署名が無効であるということだけではなく、メッセージに署名した部分集合に満足していないために拒否する可能性がある。我々はこの責任を署名者の望ましい部分集合に毎回同意するようにアプリケーションに任せ、分析のためにこの問題は考慮しない。

, GDH マルチ署名スキーム

ここで我々がセクション 2 で述べた [8] の GS 署名スキームに基づいた新しいマルチ署名スキーム MGS について説明する。この構造は非常にシンプルで効果的であり、[33] に記載されている未解決の問題も解決する。つまり、署名者が署名分散を算出した後に部分集合の構成を決定できる証明可能で安全な祭り署名スキームを見つける。

を GDH 群、 を の生成元 で構成されるグローバル情報、、ハッシュ関数ファミリー のランダムなメンバーの詳細を とする。 をプレーヤーの集合とする。 の鍵生成アルゴリズムは の一つと同じである。それ以外のアルゴリズムは以下の通り。

: 秘密鍵 を持ち署名の参加を望んでいる任意のプレーヤー は を算出してブロードキャストする。を署名に貢献したプレーヤーの部分集合とする。 はそのようなプレーヤーのインデックス集合を示す。一般性を失わなず (wlog)、各署名の署名者を知っていると仮定する特定の署名者 (任意のプレーヤーに実装されることができる) は を計算し を出力する。

: 検証者は と 内のプレーヤーの公開鍵リスト を取る。ここで各 に対して である。検証者は を算出し を出力する。

が受信したそれぞれの署名の有効性を検証する場合、MGS に堅牢性の特性を追加することができる。セクション 1 で MGS と他のマルチ署名スキームとの比較を提供した。

署名のバッチ検証

上記のマルチ署名スキームの基礎となるアプローチは、異なる公開鍵の下で同じメッセージの複数の GS 署名の効率的なバッチ検証を提供するために簡単に適用できる2。検証者は最初に の役割を果たして与えられた署名を乗算し、そして上記の検証アルゴリズムに従った検証を続行する必要がある。

マルチ署名のセキュリティ

マルチ署名のセキュリティの概念は、敵対者が部分集合 と、部分集合 のどのプレーヤーもメッセージに署名しなかったときに検証者によって受け入れらる後者のようなあるメッセージのマルチ署名を "偽造" する敵対者の可能性を捕捉しなければならない。言い換えれば、いかなる有効なマルチ署名も署名に参加しなかった場合には に属する正直なプレーヤーに責任を持たせるべきではない。

その目的を達成するために、敵対者はプレーヤーを破壊させたり、マルチ署名生成プロトコル中に任意のメッセージを送信するような可能性がある。我々はまた、敵対者が既知の不正鍵攻撃 (well-known rogue-key attack) をモデル化するために、おそらく正直なプレーヤーの鍵に依存する、破損したプレーヤーの任意の鍵を生成することを許している。これらの攻撃に関して我々は公的者に 1 つの制限のみを課す。つまり、公開鍵の登録中に秘密鍵の知識を証明することを要求する。これは標準的なプラクティスである (べきである)。我々は鍵生成アルゴリズムで破壊差破損したユーザの公開鍵と秘密鍵を出力するよう敵対者に問い合わせることでこれを簡単にモデル化する。あるいは、我々が秘密鍵を抽出できるように敵対者に知識の証明の証明を問い合わせることもできるが、しかしこれは不必要にモデルを複雑化するだろう。我々は敵対者が 1 人のプレーヤーを除くすべてのプレーヤーを陥落させることを許可する。その目的は正直なプレーヤーを "フレーム化" することである。このような強力な敵は常にプロトコルから逸脱する可能性があるあるため、結果として有効なマルチ署名の生成を妨害することに注意。[33] と同様にこの研究では堅牢性の特性に焦点を当てていない。しかし、我々のマルチ署名スキームをどのように堅牢にするかについてスケッチしている。

ここでマルチ署名のためのセキュリティ概念を形式化する。これは [33] で述べられているものと似ているが、我々の定義では個々の署名者が共同署名者の部分集合を知る必要がないという点でより一般的である。

定義 3. 攻撃者 A はグローバル情報 と、1 人の正直なプレーヤーに対応するランダムに生成された公開鍵 を学習する。一般性を失わず、我々は正直なプレーヤー を参照する。A は公開鍵と秘密鍵の 対の残りのペアを生成して出力し、攻撃者によって選択されたメッセージ上の 個の破損したプレーヤーに代わって正直なプレーヤーとマルチ署名生成プロトコルを実行することができる。敵対者の優位性 は、, および が入力メッセージ 上でマルチ署名生成プロトコルを完了しなかったように、A が有効なメッセージ部分集合署名タプル を出力する確率として定義される。

無視できない優位性 を持つ多項式時間の敵対者 A が存在しないのであれば、選択メッセージ攻撃 (chosen message attack) の下で、マルチ署名スキーム は実在的偽造に対して安全 (または単にセキュアマルチ署名スキーム) であると言う。

通常通り、上記の定義をランダムオラクルモデルに併せるために全てのパーティと署名オラクルにランダムハッシュオラクルのアクセスが与えられる。

マルチ署名スキームのセキュリティ

定理 3 . を 群とする。このとき はランダムオラクルモデルにおいてセキュアマルチ署名スキームである。

上記定理の証明はこの論文の完全版 [5] に存在する。

  • 2 この問題は同じ鍵の下で異なるメッセージの署名のバッチ検証の問題と直行している。これは [3] で対処されている。

5 ブラインド GDH 署名スキーム

ブラインド署名スキーム に鍵生成アルゴリズムと検証アルゴリズム の構文は通常の署名スキームの対応するアルゴリズムの一つと同じである。ブラインド署名アルゴリズム はユーザと署名者間の対話型プロトコルである。ここで前者は公開鍵を知っており、後者はグローバル情報と秘密鍵を与えられている。そしてプロトコルの最後にメッセージ署名ペア を出力する。 がブラインド署名アルゴリズムの出力であれば の必要がある。

BGS, ブラインド GDH 署名

GDH 署名スキームに基づく新しいブラインド署名スキームを提案する。

を GDH 群とする。 をグローバル情報とする。 を我々がセクション 2 で述べた [8] の GDH 署名スキームであるとする。ブラインド GDH 署名スキーム は以下のように定義される。アルゴリズム , は でのアルゴリズムと同じである。ブラインド署名プロトコル は以下のように定義される。ユーザは署名者の公開鍵 を保持している。メッセージ を "ブラインド" で署名するために、ユーザは乱数 を選択し、 を計算して署名者に送信する。署名者は を知っており、秘密鍵 を持っている。署名者は を計算しそれをユーザに送信する。ユーザは を計算し を出力する。

上記の は署名者による 上の有効な署名であることに注意。

ブラインド署名のセキュリティ

ブラインド署名のセキュリティの概念は 2 つの特性をとらえている。最初の特性は "不可視性" (blindness) である。つまり、ブラインド署名プロトコルの署名者は、ユーザが署名を得たメッセージに関するいかなる情報を学習すべきではない。第二の特性は偽造不可能性の特別な形式、つまり、ブラインド署名プロトコルの実行に 回従事しているユーザは 個を超える署名を取得できないはずである。電子署名におけるメッセージ選択攻撃 [23] の下での偽造不可能性の標準的な概念は、ブラインド署名の偽造不可能性の概念としては使用できない。これは、その構造によりユーザは以前に署名されていないメッセージの有効な署名を生成できる必要があるためである。ブラインド署名に対するセキュリティの容認された形式化は一つ以上の偽造に対する (against one-more-forgery) [39, 40] セキュリティである。

定義 4. を署名スキームとし を対応するブラインド署名スキームとする。攻撃者 A は によってランダムに生成された公開鍵 を学習する。A はブラインド署名プロトコルの実行でユーザの役割を行うことができる。署名者との対話後、A はいくつかのメッセージ-署名のペアを出力する。攻撃者の優位性 は A が有効なメッセージ署名ペアの集合 を出力する確率として定義される。これにより、署名者との間で呼び出されるブラインド署名プロトコルの数は厳密に のサイズより小さくなる。

無視できない優位性 を持つ多項式時間の攻撃者 A が存在しないのであれば、選択メッセージ攻撃の下で一つ以上の偽造に対してブラインド署名スキーム BS は安全である、あるいは単にセキュアブラインド署名スキームという。

Chosen-target CDH 仮定

[2] で与えられる Chaum の RSA ベースのブラインド署名スキーム [11] のセキュリティ証明と同様に、我々はブラインド署名スキームの偽造不可能性の意味でのセキュリティを、適切な計算仮定の chosen-target バージョンに削減する。RSA ブラインド署名のセキュリティは chosen-target RSA 反転問題の難易度を想定して安全であることが証明されている。すはなち、ランダムに生成された RSA 鍵ペア , に対して3 が与えられた多項式時間の攻撃者が存在しない場合、 にランダムなターゲットポイントを出力する "ターゲット" オラクルと、"ヘルパー" RSA 反転オラクル は、ヘルパー RSA 反転オラクルに対するクエリーの数がターゲットオラクルに対するクエリーの数よりも厳密に少なくなるように、ターゲットポイントの任意のサブセットを反転 ( を算出) できるという仮定である。[2] ではこの過程に類似したものが任意の一方向関数ファミリーに対して定式化できることが示唆されている。以下に類似の問題と仮定を提案する。

定義 5. を素数位数 の群とする。 を のランダムな元とし とする。 をハッシュ関数ファミリー のランダムなインスタンスとする。攻撃者 B は が与えられ、 のランダムポイント を返すターゲットオラクル とヘルパーオラクル へのアクセスを持つ。, をそれぞれ B がターゲット、ヘルパーオラクルに対して行ったクエリーの数とする。chosen-target CDH 問題を攻撃する攻撃者の優位性 は、つまり 個のペア の集合 を出力する確率として定義される。ここで となるような全ての に対して、すべての が異なり である。

chosen-target CDH 仮定は、無視できない を持つ多項式時間の攻撃者 B は存在しないことを述べている。

上記の攻撃者がターゲットオラクルに対して 1 つのクエリーを実行する場合、chosen-target CDH 仮定は標準 CDH 仮定と同等であることに注意。chosen-target CDH 問題は、CDH 問題が難しいすべてのグループにとって難しいと仮定している; これは GDH 群も含まれる。

BGS ブラインド署名スキームのセキュリティ

定理 4 . もし において chosen-target CDH 仮定が true であれば、選択メッセージ攻撃の下で は一回以上の偽造 (one-more forgery) に対してセキュアである。

上記定理の証明はこの論文の完全版 [5] を参照。

  • 3 ここで は 2 つのランダムな素数の積であり、 は のランダムな元、 である。 はオイラーの 関数である。

6 Acknowledgments

We thank Mihir Bellare for the useful discussions, for suggesting to consider the topic of threshold signatures. We thank Daniele Micciancio and Adriana Palacio for their useful comments on the draft of this paper. We also thank Leonid Reyzin for clarifications on [33]. This research was supported in part by SDSC Graduate Student Diversity Fellowship, NSF Grant CCR-0098123 and NSF Grant ANR-0129617.

References

  1. M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols. First ACM Conference on Computer and Communications Security, ACM, 1993.
  2. M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko, “The One-More-RSA-Inversion Problems and the security of Chaum’s Blind Signature Scheme,” Financial Cryptography 01, Lecture Notes in Computer Science, 2001.
  3. M. Bellare, J. Garay and T. Rabin, “Fast batch verification for modular exponentiation and digital signatures ,” Eurocrypt 98, 1998.
  4. E. Berlekamp and L. Welch, “Error correction of algebraic block codes,” US Patent 4,633,470. 33
  5. A. Boldyreva “Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme,” Full version of this paper. Available at http://www-cse.ucsd.edu/users/aboldyre/.
  6. D. Boneh and M. Franklin. “Identity-based encryption from the Weil Pairing,” Crypto 01, 2001.
  7. D. Boneh, C. Gentry, B. Lynn and H. Shacham, “Aggregate signatures from bilinear maps,” Manuscript.
  8. D. Boneh, B. Lynn and H. Shacham, “Short signatures from the Weil pairing,” Asiacrypt 01, 2001.
  9. C. Boyd, “Digital multisignatures,” Cryptography and Coding, 1986
  10. J. Camenisch and M. Stadler, “Efficient group signatures for large groups,” Crypto 97, 1997.
  11. D. Chaum, “Blind signatures for untreaceable payments,” Crypto 82, 1982.
  12. D. Chaum and E. van Heyst, “Group signatures,” Eurocrypt 91, 1991.
  13. R. Canetti and A. Herzberg, “ Maintaining security in the presence of transient faults,” Crypto 94, 1994.
  14. Y. Desmedt, “Society and group oriented cryptography,” Crypto 87, 1987.
  15. Y. Desmedt, “Threshold cryptography,”, European Transactions on Telecommunications, 5(4), 1994.
  16. Y. Desmedt and Y. Frankel, “Threshold cryptosystems,” Crypto 89, 1989.
  17. Y. Desmedt and Y. Frankel, “Shared generation of authenticators and signatures,” Crypto 91, 1991.
  18. P. Feldman “Apractical scheme for non-interactive verifiable secret sharing,” FOCS 87, 1987.
  19. Y. Frankel, P. Gemmal, P. MacKenzie and M. Yung, “Proactive RSA,” Crypto 97, 1997.
  20. S. Galbraith, J. Malone-Lee, N. P. Smart, “Public key signatures in the multi-user setting”, Information Processing Letters, Vol. 83, Issue 5, 2002.
  21. R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, “Robust threshold DSS signatures,” Eurocrypt 96, 1996.
  22. R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, “Secure distributed key generation for discrete-log based cryptosystems”, Eurocrypt 99, 1999.
  23. S. Goldwasser, S. Micali and R. Rivest, “Adigital signature secure against adaptive chosen-message attacks”, SIAM Journal on Computing, 17(2):281-308, 1988.
  24. L. Harn, “Group-oriented (t,n) threshold digital signature scheme and digital multisignature,” IEE Proc. Computers and Digital Techniques, 141(5), 1994.
  25. A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk and M. Yung, “Proactive public key and signature systems,” ACM Conference on Computers and Communication Security, 1997. 22:612-613, (1979).
  26. A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, “Proactive secret sharing, or: How to cope with perpetual leakage,”, Crypto 95, 1995.
  27. P. Horster, M. Michels and H. Petersen, “Meta-multisignatures schemes based on the discrete logarithm problem,” IFIP/Sec 1995.
  28. K. Itakura and K. Nakamura, “Apublic key cryptosystem suitable for digital multisignatures,” NEC Research & Development, 71:1-8, 1983.
  29. A. Joux, “Aone-round protocol for tripartite Diffie-Hellman,” ANTS-IV conference, vol. 1838.
  30. A. Joux and K. Nguyen, “Separating Decision Diffie-Hellman from DiffieHellman in cryptographic groups,” e-print archive, report #2001/03.
  31. C. Li, T. Hwang and N. Lee, “Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders,” Eurocrypt 94, 1994.
  32. A. Lysyanskaya, “Unique signatures and verifiable random functions from the DH-DDH separation”, Crypto 02, 2002.
  33. S. Micali, K. Ohta and L. Reyzin, “Accountable-subgroup multisignatures,” ACM Conference on Computer and Communications Security, 2001.
  34. T. Okamoto, “Adigital multisignature schema using bijective public-key cryptosystems,” ACM Transaction on Computer Systems, 6(4): 432-441, 1988.
  35. K. Ohta and T. Okamoto, “Adigital multisignature scheme based on the Fiat-Shamir scheme”, Asiacrypt 91, 1991.
  36. K. Ohta and T. Okamoto, “Multi-signature scheme secure against active insider attacks”, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E82-A(1):21-31, 1999.
  37. R. Ostrovsky and M. Yung, “How to withstand mobile virus attacks,” PODC, 1991.
  38. T. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” Eurocrypt 91, 1991.
  39. D. Pointcheval and J. Stern, “Provably secure blind signature schemes,” Asiacrypt 96, 1996.
  40. D. Pointcheval and J. Stern, “Security arguments for digital signatures and blind signatures,” Journal of Cryptology, 13(3):361-396, 2000.
  41. T. Rabin, “Asimplified approach to threshold and proactive RSA,” Crypto 98, 1998.
  42. R. Rivest, A. Shamir and Y. Tauman, “How to leak a secret”, Asiacrypt 01, 2001.
  43. A. Shamir, “How to share a secret,” Communications of the ACM, 22:612-613, (1979).
  44. V. Shoup, “Practical threshold signatures”, Eurocrypt 00, 2000.

翻訳抄

[8] の Gap Diffie-Hellman 群を 1) BLS 署名を秘密分散のスキームに拡張したしきい値署名、2) 複数の署名分散から一つの署名を作成するマルチ署名、3) メッセージを秘匿するブラインド署名のそれぞれに応用した 2002 年の論文。

  1. Alexandra Boldyreva (2002) "Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme"