セキュリティ

論文翻訳: Short Signatures from the Weil Pairing

Takami Torao 2001年の論文 #BLS署名 #GDH
  • このエントリーをはてなブックマークに追加

Dan Boneh*, Ben lynn, and Hovav Shacham

Computer Science Department, Stanford University
{dabo,blynn,hovav}@cs.stanford.edu

Abstract

特定の楕円曲線および超楕円曲線に関する Computational Diffie-Hellman 仮定に基づいた短い署名スキームを紹介する。同等のセキュリティレベルをもつ DSA 署名に比べて署名の長さは半分である。我々の短い署名スキームは、署名が人の手で入力されたり低帯域幅チャネルを介して送信されるシステム向けに設計されている

  • * Supported by NSF and the Packard Foundation.

Table of Contents

  1. Abstract
  2. 1 導入
  3. 2 Gap Diffie-Hellman に基づく署名スキーム
    1. 2.1 Gap Diffie-Hellman 群 (GDH 群)
    2. 2.2 GDH 署名スキーム
    3. 2.3 セキュリティ
  4. 3 小さな表現での Gap Diffie-Hellman 群の構築
    1. 3.1 楕円曲線とヴェイユペアリング
    2. 3.2 特別な超特異曲線
    3. 3.3 楕円曲線へのハッシュ化
    4. 3.4 具体的な短い署名スキーム
    5. 3.5 未解決問題：高セキュリティの短い署名
  5. 4 定理のセキュリティ証明
    1. 4.1 概要
    2. 4.2 の構築
    3. 4.3 最適化と結論
  6. 5 実験結果
    1. 5.1 実装の詳細
    2. 5.2 実行時間
  7. 6 結論
  8. Acknowledgments
  9. References
  10. 翻訳抄

1 導入

人間が手動で署名を入力する必要がある環境では短いデジタル署名が必要である。例えば製品登録システムではしばしば CD ラベルに記載されている署名を入力するようユーザに求めている。より一般には低帯域幅の通信環境では短い署名を必要としている。例えば郵便切手に署名を印刷する場合は短い署名が必要である [21,19]。現在最も頻繁に使用されている署名スキームの RSA と DSA は提供するセキュリティに比べていささか長い署名を提供する。例えば 1024 ビットのモジュラスを使用する RSA 署名の長さは 1024 ビット長である。同様に 1024 ビットのモジュラスを使用する標準の DSA 署名は 320 ビット長である。ECDSA などの楕円曲線 DSA 変種も 320 ビット長である [1]。320 ビットの署名は人間が入力するには長すぎる。

我々は長さが約 160 ビットで 320 ビットの DSA 署名と同様のセキュリティを提供する署名スキームを提案する。我々の署名スキームは (ランダムオラクルモデルでの) 選択メッセージ攻撃 (chosen message attack) の下での実在的偽造 (existential forgery) に対してセキュアである。Computational Diffie-Hellman 問題 (CDH) が特性 3 の有限体上の特定の楕円曲線上で困難であると仮定している。署名の生成は曲線上での単純な乗算である。署名の検証は曲線上の双線形ペアリングを使用して行われる。我々の署名スキームは本質的に楕円曲線の特性を使用している。その結果 に我々のスキームに相当するものはない。

我々が使用する曲線の特性により、今のところ我々は以下に示す長さの署名のみを提供できる。これらの群の CDH 問題を解くためのもっともよく知られたアルゴリズムは特性 3 の有限体で離散対数を必要とする。フィールドのサイズは以下の表の右端の列に (ビットで) 与えられる。

Signature size
(bit)		 EC group size
(bit)		 Discrete-log Security
(bit)
126 126 752
154 151 923
237 220 1417
259 256 1551
265 262 1589

2 行目は 154 ビット長の署名で 320 ビット DSA または 320 ビット ECDSA に匹敵するセキュリティを獲得できることを示している。154 ビット署名を偽造するためのもっとも知られたアルゴリズムでは 923 ビットサイズの有限体か 151 ビットサイズの楕円曲線群で CDH 問題を解く必要がある。セクション 3.5 では我々の手法を一般化し任意長の署名を構築するアプローチを概説する。

短い署名の作成は古くからある問題である。いくつかの提案はセキュリティレベルを維持しながら DSA 署名スキームを短縮する方法を表している。Naccache and Stern [19] は署名の長さが約 240 ビットとなる DSA の一種を提案している。Mironov [18] は同様の長さの DSA 変種を提案しその構造の具体的なセキュリティ解析を (ランダムオラクルモデルで) 与えている。DSA 署名長を削減するために提案された別の手法はメッセージ回復を伴う署名 [21] である。このようなシステムではメッセージの一部を署名にエンコードすることで、メッセージ-署名のペアの全長が短縮される。長いメッセージの場合は長さ 160 ビットの DSA 署名オーバーヘッドを達成することができる。しかし、非常に短いメッセージ (例えば 64 ビット) では全体の長さは依然として 320 ビットである。我々の署名スキームを使用することで、メッセージの長さに関係なく署名の長さは常に 160 ビットのオーダーとなる。メッセージを送信せず署名だけを送信する場合、メッセージ回復を伴う DSA 署名は標準の DSA 署名よりも短くならないことに注意。

我々の署名スキームは、CDH 問題は困難だが Decision Diffie-Hellman 問題 (DDH) は容易である群を使用している。このような群の最初の例は [12] で与えられ、以前には [11,4] で用いられた。このような群を Gap Diffie-Hellman 群、略して GDH 群と呼ぶ。Okamoto and Pointcheval [20] は Gap Diffie-Hellman 群が署名スキームを生み出すとコメントした。しかし、ほとんどの Gap Diffie-Hellman 群は比較的長く、短い署名にはつながらない。GDH 群から派生した署名スキームのセキュリティを証明し、それらが非常に短い署名をもたらす方法を示す。セクション 5 で提案した署名スキームを実験し実行時間を与える。

2 Gap Diffie-Hellman に基づく署名スキーム

我々は任意の Gap Diffie-Hellman 群で機能する署名スキームを提示する。前述のように、このスキームは Okamoto and Pointcheval [20] によって暗黙的に記述されている。このスキームは Chaum and Pederson [5] によって提案された否認不可署名スキームに似ている。次のセクションではこの署名スキームがどのように非常に短い署名を生成するかを示す。

2.1 Gap Diffie-Hellman 群 (GDH 群)

が素数である (乗法) 巡回群 を考える。我々は において 3 つの問題に興味がある。

Group Action (群作用). 与えられた に対して を求める。
Decision Diffie-Hellman. に対して が与えられた場合、 であるかを決定する。
Computational Diffie-Hellman. に対して が与えられた場合、 を計算する。

Gap Diffie-Hellman 群を段階的に定義する。

定義 1 . group action をある時間単位で計算でき、 上の Decision Diffie-Hellman を最大 時間で計算できる場合、 は Diffie-Hellman の 決定群である。
定義 2 . 群 で Computational Diffie-Hellman 問題を解く際のアルゴリズム の優位性は ここで確率は , の選択、そして のコイントスを超える。もし が最大 で時間内に実行され である場合、アルゴリズム は の Computational Diffie-Hellman を -break するという。
定義 3 . 素数位数群 が Diffie-Hellman に対して -決定群であり、Computational Diffie-Hellman を -break するアルゴリズムが存在しない場合、 は -GDH 群である。

2.2 GDH 署名スキーム

GDH 署名スキームは任意のメッセージ 上での署名作成を可能にする。署名 は の元である。ベースの群 と生成元 はシステムパラメータである。我々は によって を表す。ここで は の恒等写像である。

署名アルゴリズムは KeyGen, Sign, Verify の 3 つのアルゴリズムで構成される。フルドメインハッシュ関数 を使用する。セキュリティ分析では はランダムオラクル [3] とみなされる。セクション 3.3 ではフルドメインハッシュの要件を弱めている。

鍵生成. をランダムに選び、 を計算する。公開鍵は であり、秘密鍵は である。
署名. 与えられた秘密鍵 とメッセージ に対して と を計算する。署名は である。
検証. 与えられた公開鍵 、メッセージ 、署名 に対して を計算し、 が有効な Diffie-Hellman タプルであることを検証する。

GDH 署名は の単一元であることに注意。したがって短い署名を作成するには元が短い表現を持つ GDH 群を必要とする。セクション 3 ではそのような群を構築する。

2.3 セキュリティ

選択メッセージ攻撃の下で実在的偽造に対する GDH 署名スキームのセキュリティを示す。

定義 4. 署名オラクル にアクセスが与えられると、偽造アルゴリズム の実在署名偽造の優位性は確率は鍵生成アルゴリズムと偽造者のコイントスに引き継がれる。

ここで敵対者 は署名オラクルに適応的に問い合わせを行うことができる: その問い合わせのいずれかは以前の回答に依存するかもしれないが、以前にオラクルに問い合わせたメッセージの署名を発行しないかも知れない。また、敵対者はランダムオラクルとして扱われるフルドメインハッシュ関数にアクセスできる。

定義 5 . 偽造者 は、 が最大 回実行され、ハッシュ関数に対して 問い合わせを実行し、署名オラクル に対して最大 回要求し、 のとき、署名スキームを -break する。
定義 6 . 署名スキームは、偽造者が -break しない場合、適用型選択メッセージ攻撃の実在的偽造に対して -secure である。

次の定理は GDH 署名スキームがセキュアであることを表している。この定理の証明はセクション 4 で示す。

定理 . を次数 の Diffie-Hellman の -gap 群とする。このとき 上の Gap 署名スキームは適用型選択メッセージ攻撃の実在的偽造に対して -secure である。ここで であり は小さな定数である。ここで は自然対数の底である。

3 小さな表現での Gap Diffie-Hellman 群の構築

ヴェイユペアリング (Weil pairing) を使用すると特定の楕円曲線を GDH 群として使用することができる。楕円曲線に関するいくつかの事実を思い出し (例えば [14,22] 参照)、GDH 署名に特定の曲線を使用する方法を示す。特に、我々は 上の を説明する。

3.1 楕円曲線とヴェイユペアリング

Computational Diffie-Hellmann が困難だが Decision Diffie-Hellman は容易であるような大きな素数位数を持つある群 を構築するために使用できるのであれば楕円曲線は GDH 署名スキームの基礎として使用することができる。最初に の部分群での CDH 困難性の必要条件を特徴づける。

定義 7 . を素数、 を正の指数、 を 点を持つ 上の楕円曲線とする。 内の を となるような素数位数 の点とする。 の の次数が の場合、部分群 はある整数 に対してセキュリティ乗数 を持つという。言い換えると:

CDH が部分群 上で困難であるためには、この部分群のセキュリティ乗数 が小さすぎないようにしなければならないことが (後述のとおり) よく知られている。一方で で効率的な Decision Diffie-Hellman アルゴリズムを得るためには を大きくしすぎない必要がある。従って短い署名の構築における問題は がセキュリティ面で充分に大きく効率面で充分に小さい曲線を見つけることである。現在のセキュリティパラメータを使用すると が短い署名を得るために充分である。 のように少し高い を持つ楕円曲線を構築することは未解決問題である (セクション 3.5 参照)。

Discrete-log on elliptic curves: をセキュリティ乗数 を持つ次数 の の部分群とする。 で離散対数を算出するための標準的な 2 つの方法について簡単に説明する。

  1. MOV: Menezes-Okamoto-Vanstone 帰着 [15] のように、効率的に計算可能な準同型を使用して の離散対数問題を のある拡張、つまり の離散対数問題にマッピングする。この準同型写像の下での のイメージは次数 の の部分群である。従って であり、 の定義により であることを意味する。従って MOV メソッドは最善で の離散対数問題を の部分群の離散対数問題に削減することができる。従って、 において離散対数が困難であることを保証するために、我々は大きな を持つ曲線が必要である。
  2. Generic: Baby-Step-Giant-Step や Pollard's Rho メソッド [16] のような Generic 離散対数アルゴリズムは に比例する実行時間を持つ。従って が十分に大きいことを保証しなければならない。

Decision Diffie-Hellman on Elliptic curves: を素数位数 の点とする。部分群 はセキュリティ乗数 を持つと想定する。 と仮定する。Balasubramanian and Koblits [2] は が から線形に独立した点 を含んでいることを示した。そのような点 は効率的に見つけることができる。 と の線形独立性は後述するヴェイユペアリングを介して検証できることに注意。

それぞれ次数 の 2 つの線形独立点 と で、我々は、DDH オラクル [12] を構築できる特定の質問に答えるためにヴェイユペアリングを使用することができる。 を と によって生成された の部分群を示すものとする。ヴェイユペアリングは以下の特性を持つマップ である:

  1. Identity: 全ての に対して である。
  2. Bilinear: 全ての と に対して となる。
  3. Non-degenerate: もし に対して全ての で ならば、 である。
  4. Computable: 全ての に対してペアリング 効率的に計算することができる [17]。

と が線形依存である場合にのみ であることに注意。

双方とも次数 を持つ線形独立点 と に対して、ヴェイユペアリングによりタプル が であるかを判断できる; 実際、である。 から の計算可能な同型 も存在するとする。必然的に はすべての に対して のようになる。ここで である。この場合、ヴェイユペアリングによりタプル が のようになるかを決定判別することができる: 同型 によりヴェイユペアリングは Decision Diffie-Hellman のアルゴリズムを提供する。DDH のアルゴリズムでは 上の点のヴェイユペアリングの 2 つの評価が必要であることに注意。

3.2 特別な超特異曲線

セクション 3.1 の機構を使用して 上の で与えられる超特異楕円曲線 から小さな表現の GDH 群を導き出す。のちに述べるように、これらはセキュリティ乗数 を持ったユニークな超特異楕円曲線である。従って MOV 帰着は の離散対数問題を にマップする。これは短い署名を得るために比較的小さな の値を使用できることを意味するが、セキュリティは大きな有限体の離散対数問題に依存する。我々はこれらの曲線のふるまいを説明するために 2 つの単純な補題を使用する ([23,13] も参照)。

補題 1. 上で によって定義される曲線 はを満たす。 上で によって定義される曲線 はを満たす。

Proof. [13, section2] 参照。∎

つまり、 が か に等しいなら、必要に応じて と の一つを単純に選択することで 上の 点を持つ楕円曲線を構築する方法を示している。

補題 2. を 上の によって定義される楕円曲線とする。ここで は か に等しいとする。このとき は を割り切る。

Proof. であるため、任意の整数 に対して に従う。特に のとき となる。ここで が上記のような楕円曲線だった場合、 が または のいずれかであることが分かる。しかし である。従って である。

補題 1 と 3 を併せると に関連する値に対して曲線 と のセキュリティパラメータ は最大で 6 となるだろう (より具体的には )。曲線の特定の素数部分群に対して実際にセキュリティパラメータが 6 かどうかは計算によって決定されなければならない。

, の自己同型: が か と等しいような に対して、 の 3 つの元 , , は , , を満たす。ここで 上の以下のマッピングを考える:

補題 3. が か と等しいとする。 は の自己同型であり、 は と自己同型である。さらに、もし が 上の (または 上の) 次数 の点の場合、 (または は に線形独立な次数 の点である。

Proof. Silverman [22, p.326] 参照。∎

前のセクションで示したように、これらの曲線のいずれかの次数 の点 に対して、適切な自己同型により Decision Diffie-Hellman 問題を解くことができる。

3.3 楕円曲線へのハッシュ化

GDH 署名スキームにはハッシュ関数 が必要である。ここで は GDH 群である。我々は GDH 群として楕円曲線の部分群を使用することを提案している。楕円曲線の部分群で直接ハッシュ化するハッシュ関数を構築することは難しいため、ハッシュ要件をわずかに緩和する。

を で定義される次数 の楕円曲線とする。 を素数位数 の点とする。ここで とする。部分群 を GDH 署名スキームの GDH 群として使用したいと考えている。ハッシュ関数 が与えられたとすると、そのようなハッシュ関数 は標準的な暗号論的ハッシュ関数から構築することができる。セキュリティ分析では をランダムオラクルとみなす。我々は MapTopGroup と呼ばれる次の決定的アルゴリズムを使用して のメッセージを 上にハッシュ化する。小さなパラメータ を修正する。ここで は失敗確率の望ましい限界である。

: を定義するアルゴリズムは以下の通り:

  1. として を設定する;
  2. を設定する;
  3. が の二次剰余のとき、次を実行する:
    1. を の 2 つの平方根とする。これらの平方根を選ぶために を使用する。, を 上の次数 の多項式と見立てる。そして の整数として見立てるとき の定数項が の定数項より大きくないことを確認する (必要に応じて と は入れ替える)。 を点 \) に設定する
    2. を計算する。 は 内である。もし が 内にあるなら、 を出力して停止する。
  4. それ以外の場合、 をインクリメントして Step 2 に行く; もし が に達したら失敗を報告する。

失敗確率は適度に大きい を選択することで任意に小さくすることができる。各 に対して が 上の点に至る確率はおおむね である (ここで確率はランダムオラクル の選択を超える)。従って 呼び出しの予想回数は約 2 であり、特定のメッセージ がハッシュ不可能と検出される確率は である。

補題 4. ランダムハッシュ関数 を使用するとき、部分群 で GDH 署名スキームが -secure であると仮定する。このとき、ハッシュ関数 が で計算される場合 -secure である。ここで はランダムハッシュ関数 である。

Proof Sketch: ハッシュ関数 が を使用して計算されるとき、偽造アルゴリズム は部分群 の Gap 署名スキームを -break すると仮定する。我々は がランダムオラクル である場合にスキームを -break するアルゴリズム を構築する。

我々の新しい偽造 はブラックボックスとして を実行するだろう。 は独自のハッシュオラクル を使用して に対して の動作をシミュレートする。これは の元の配列 を使用する。配列には 行と 列がある。初期化時に は の均一に選択された元で を満たす。

そして は を実行し、 が要求する ハッシュに対してすべてのユニークなメッセージ を追跡 (およびインデックス化) する。 が、 の見たことのない のメッセージ (および は任意の -bit データ列) の ハッシュを問い合わせると、 は行 , をスキャンする。各 について、 は前述 の Step 3 に従い の点を探す。 が にマップされる最小の について、 は を次のように定義した別の点 に置き換える。 とする。 は となるようにランダムな を構築する。 を設定する。ここで は Step 3a で が にマッピングされるように設定される。そして必要に応じて を設定する。

この事前準備パッチが完了すると は単に を返すだけでデータ列 に による ハッシュクエリーに答えることができる。 から見えるシミュレートされた は実際の攻撃の場合と統計的に区別することができない。従って、 が を使用して署名スキームを破ることに成功した場合、 は、 を参照しながら を実行することで、同じ可能性で成功し、 の Step 3 で追加情報を維持して指数演算を実行することによる実行時間のペナルティのみを被る。∎

3.4 具体的な短い署名スキーム

ここまでを要約するために で定義された曲線 から導出された GDH 群を使って具体的な署名スキームを説明する。これらの曲線の有用なインスタンスを Table 1 に示す。これらのインスタンスは Weil-descent attacks [9,10] を回避するため が素数となるものに限定していることに注意。セクション 3.3 で説明したように、我々は任意のデータ列から の元と追加のビットへ、ハッシュ関数 を使用して任意のビット列を の次数 の点にマップするために を使用する。

Table 1. GDH 署名に対する超特異楕円曲線。ここで 、 は を割り切る最も大きい素数。MOV 帰着は曲線を 元の体にマップする。
curve Signature Size
 DLog Security
 Multipler
 MOV Security
79 126 126 6 752
97 154 151 6 923
149 237 220 6 1417
163 259 256 6 1551
163 259 259 6 1551
163 259 252 6 1589

具体的な署名スキーム:

鍵生成
Table 1 の値 のいずれかが与えられたとき、 を対応する曲線とし、 を曲線の次数の最大素因数とする。 を次数 の点とする。 をランダムに選び を設定する。ここで は公開鍵であり は秘密鍵である。
署名
メッセージ に署名するには、 を点 にマップするためアルゴリズム を使用する。 を設定する。署名 は の 座標である。したがって 。
検証
公開鍵 、メッセージ 、署名 が与えられたとき:
  1. ある に対して 座標が 、 座標が の次数 の点 を見つける。もしそのような点が存在しなければ署名を無効として拒否する。
  2. と を設定する。ここで は曲線 上のヴェイユペアリング、 は補題 3 で説明した曲線の自己同型である。
  3. もし または = v\) のどちらかであれば署名を受け入れる。そうでなければ拒絶する。

と は両方とも 座標を として持つ 上の点であることに注意。これらの 2 点のいずれかは署名アルゴリズムで署名を生成するために使用する点 とすることができる。実際、曲線上では であるため となる。したがって、 は が Diffie-Hellman タプルであることをテストし、 は が Diffie-Hellman タプルであることをテストする。

次の補題は (ランダムオラクルモデルでの) 選択メッセージ攻撃の下で、実在的偽造能力を持つ攻撃者が の Diffie-Hellman 問題も解くことを示している。

補題 5. を Table 1 に示されている曲線の一つとし、 を を割り切る最大の素数とし、 が 上の次数 の点であり、 上で Computational Diffie-Hellman を -break するアルゴリズムが存在しないと想定する。 をランダムオラクルとする。このとき、前述の具体的な署名スキームは (ランダムオラクルモデルの) 適応型選択メッセージ攻撃 (adaptive chosen-message attack) の実在的偽造に対して -secure である。ここでであり は小さな定数である。

Proof. 仮定より は -GDH 群である。ここで は 上でヴェイユペアリングを計算する為に必要な時間の 2 倍である。任意のビット列から へのランダムハッシュオラクル の存在を仮定すると、(セクション 2.2 で指定している) 上の一般的な GDH 署名スキームは、主定理 (セクション 4) による適応型選択メッセージ攻撃の実在的偽造に対して -secure である。ここでであり は小さな定数である。

セクション 3.3 より、我々はハッシュ関数 から 上にハッシュ関数 を構築できる。補題 4 より、アルゴリズム を使用する 上の一般的な GDH 署名スキームは、主定理 (セクション 4) による適応型選択メッセージ攻撃の実在的偽造に対して -secure である。ここで 上の一般的な GDH 署名スキームと上記に説明する 上の具体的なスキームの唯一の違いは、後者のスキームでの署名が ではなく の元であるということである。具体的なスキームを破る敵対者 が与えられると、以下のように一般スキームを破るようなアルゴリズム を構築することができる。公開鍵は 2 つのスキームで同一であるため は単純に に を与える。2 つのスキームでハッシュは同一であるため、 は へのハッシュ要求を自身のハッシュオラクルに渡し に回答を提供する。 がメッセージ の署名を要求すると はその署名オラクルから署名 を取得し、 に の 座標 を与える。最後に、 がメッセージ 上に (具体的なスキームに対する) 偽造署名 を出力したとき、 は 座標が となるような点 を見つける。前述の論議より、 が 上の具体的なスキームの署名であるような が Diffie-Hellman タプルであるか、 が 上の具体的なスキームの署名であるような が Diffie-Hellman タプルである。 は適切な と のどちらか一つとともに を出力する。

このシミュレーションに必要な追加の時間は 2 つの追加の署名検証によって支配され、それぞれの時間には 時間がかかる。したがってもし一般的な GDH スキームが -secure であれば具体的な GDH スキームは -secure である。ここで (), (), () を組み合わせると必要な削減量が得られる。∎

3.5 未解決問題：高セキュリティの短い署名

前のセクションでは の離散対数と同様の安全性を持つ短い署名スキームを構築するために 上の超特異曲線を使用することを提案した。しかし、超特異曲線に固執する必要はない。他の楕円曲線または長楕円曲線を使用すると、さらに高いセキュリティ乗数を実現できる可能性がある。

セクション 3.2 では 上の曲線 と が最大 6 のセキュリティパラメータ を持っている事を示した。実際これは任意の超極意曲線に対する の最大値である [15,23]。 の値がわずかに高い (必然的に非超特異) 楕円曲線での GDH 署名スキームのインスタンス化は署名検証に必要な作業を増加させるが、同等の署名ビット長での MOV-関連攻撃に対するセキュリティも向上させる。

個の点を持つ楕円曲線 、大きな素数 、次数 の部分群に対するセキュリティパラメータ 、次数 の 2 つの線形独立点 と を考慮する。ここで 、 である。 に線形独立な点 は を仮定する [2] によって存在しなければならないことに注意。そのような曲線の場合、 と の間をマッピングする自己同型者像は必ずしも存在しない。したがって 2 つの群を一緒にするために Gap 署名スキームをわずかに変更する。

ウェイルペアリングを使用してタプル が かどうかを決定することはたやすい。これを co-Decision Diffie-Hellman 問題と呼び、あるタプル が与えられると を計算するという明らかな計算上の変種を持つ。修正された (co-gap) 署名スキームは以下の通り。

鍵生成
, を上記のような素数位数 の 2 つの線形独立点とする。 を選択し を計算する。公開鍵は 、秘密鍵は である。
署名
秘密鍵 とメッセージ が与えられると を点 にマップするため を使用する。 を設定する。署名 は の元である の 座標である。
検証
公開鍵 、メッセージ 、想定される署名 が与えられ、 を 座標が 、 座標がある に対して (もしそのような点が存在しなければ署名は無効として拒否する) を持つ、次数 の 上の点とする。、 と設定する。もし または であれば署名を受け入れ、そうでなければ拒否する。

セクション 3.4 での推論に類似した推論より、検証フェーズのテストは または のいずれかが有効な co-Diffie-Hellman タプルであることを保証する。公開鍵 は の元であり、したがって長く、署名 は の元であり、したがって相対的に短い。このスキームのセキュリティは敵対者が co-Computational Diffie-Hellman 問題を -break しないという仮定に基づいている。

したがって課題は などより大きな の値を持つ楕円曲線を構築することである。現在、セキュリティ乗数 の楕円曲線ファミリーを構築することは未解決の問題である。

Galbraith [8] は "大きな" セキュリティ乗数を持つより高い種数の超特異曲線を作成する。例えば超特異曲線 は 上でセキュリティ乗数 12 を持つ。この種数 2 の曲線の Jacobian 上の点が の 2 つの値によって特徴づけられるため (削減された除数の 2 つの 座標) 署名の長さは ビットとなる。したがって有限体 の CDH を計算するセキュリティを備えた長さ の署名を得ることができる。署名の長さと有限体の次数の間のこの係数 6 は楕円曲線の場合と同じである。したがってこの種数 2 の曲線は署名のセキュリティを向上させないが、Table 1 で与えられたものより多くの署名長を提供する。個の曲線は特徴 2 の体上で定義されているため特徴 3 の体上で定義されている曲線より計算に適している。Galbraith は種数 2 超超特異曲線の Jacobian の最大セキュリティ乗数が 12 であることを示している。したがって種数 2 の超特異曲線はより高いセキュリティを持つ短い署名を与えないだろう。より高いセキュリティで短い署名を与える種数 3 の長楕円曲線ファミリーを構築できるかは未解決の問題である。

4 定理のセキュリティ証明

我々はランダムオラクルモデルにおいて GDH 群の GDH 署名は安全であることを証明する。証明は Coron [6] によるフルドメインハッシュ RSA 署名に対して与えられているものと似ているが表現が異なっている。この方法のポイントは署名スキームに対する破断確率 (break-probability) は偽造者が行うハッシュクエリーの回数に依存するのではなく、敵対者が行う署名クエリーの回数のみに依存する。

定理 (Gap Signature Security). が -GDH 群であるなら、 上の Gap 署名スキームは適応型選択メッセージ攻撃の実在的偽造に対して -secure である。ここでおよび は (実際には最大 2 の) 小さな定数である。

証明は段階的に行う。

4.1 概要

アルゴリズム が 上の Gap 署名スキームを -break すると仮定する。 を使用して の Computational Diffie-Hellman を break するアルゴリズム を構築してみよう。ここで と は前述の通りである。

GDH 群 に対する偽造者 が与えられた場合、 を使用して の CDH を解除するアルゴリズム を構築する。 はチャレンジ を与えられる。このチャレンジを使用して に提供する公開鍵を構築する。そして の実行を許可する。時々、 は 2 つのオラクルに対してクエリーを実行する。一つはメッセージのハッシュ化、もう一つはメッセージの署名である。これらのオラクルは の操り人形であり、建設的な方法で操作する。最後に、全てがうまく行けば が出力する偽造は によって CDH チャレンジの回答に変換される。

の署名を要求する前に のハッシュ化を要求し、その偽造として出力するメッセージ のハッシュを常に要求するという意味で は良い振る舞いをする (well-behaved) と想定する。この特性を持つように任意の偽造アルゴリズム を変更するのは簡単である。

は一定量の記帳を行う必要がある。特に、 がハッシュまたは署名を要求したメッセージのリストを維持する必要がある。 から到着する各メッセージ はインデックス が割り当てられる; は明らかに によって制限される。メッセージは に、署名は (可能であれば) に保存される。

4.2 の構築

の挙動を説明したり toto での有効性を証明するのでははなく、より洗練された 変種が を実行する一連の "ゲーム" で を構築する; 最後の は我々が求める である。

(各 変種は可能な限り最良の削減を行うための確率定数 に依存する。この定数は後に最適化する。 を に対する確率分布として定義する。ここで 1 は確率 で、0 は確率 で描かれる。)

Game 1. にチャレンジ が与えられる。セットアップでは を構築する。そして の各 に対して はランダムビット と乱数 を選択する。次に と を設定する。 は有効な Diffie-Hellman タプルであるため はハッシュが のメッセージの署名であることに注意。そして は公開鍵 で を実行する。

はメッセージ のハッシュを要求すると は で応答する; がメッセージ の署名を要求すると は で応答する。

最後に は失敗を認めるか、偽造した署名 を返すかして停止する。ここである ( が署名を要求しなかった) に対して である。 が偽造に成功すると は "" を出力する; そうでなければ "" を出力する。

ハッシュ は に均等に分布しているため のハッシュオラクルはランダムオラクルである。さらに署名 は全て有効である。従って、ランダムオラクルモデルにおいて は に実行されたとき単独で実行したのと全く同じ挙動をする。したがってここで最初の確率は と のコイントスと と の選択に対して取得される。 は , から均一に選択されるため、 が に提供する公開鍵は に均一に分散される。

Game 2. は一つの例外を除いて と同様に機能する。 が失敗すると は "" を出力する; が成功すると偽造 を出力する。ここで は のインデックスである。そして は のとき "" を出力し、 のとき "" を出力する。

明らかに は に関するどのような情報も取得できないため、その挙動はそれらの値には依存できない。したがって が実行する最終的なラウンドトリップテストはその時点までゲームとは無関係である。したがって、各 は から描画されるためとなる。

Game 3. は と同様に機能するがここでも変更が加えられている。 が偽造に失敗すると も失敗する。 が で偽造を発見することに成功すると は のときのみ成功を主張し、 は のメッセージ でのみ署名を要求する。

繰り返すが はどのような からも情報を取得できない。各署名要求は確率 で のにゲーム終了時に失敗を宣言させることができるが、ゲーム中にそれらのいずれかが失敗したかを知ることはできない。 は独立しているため、 による失格に関する限り の各署名要求はそれぞれ独立した試行である。さらに は が署名を要求するいずれの からも独立しているため、 が 1 と等しいというテストは独立した試行であり、ゲーム 2 の分析には影響しない。

いずれの署名要求でも が失格とならない確率は である。 が 個の署名オラクルクエリーを作成し ( は多くて )、さらにインデックス を持つメッセージに対してクエリーを実行する場合、となる。

Game 4. は と同様に機能する。ただし、 が に対するメッセージ の署名を要求するとき は失敗を宣言し直ちに停止する。

チャレンジと のランダムビット、および のランダムビットを修正することで の実行を完全に記述することができる; これらは集合的に各 の値と が署名を要求するインデックスを決定する。 が のある に署名を要求する実行を unlucky と呼ぶことにする。 が失敗を宣言した場合に もそうしたとき; が偽造を発見した場合に が unlucky な署名クエリーのために失敗したとき; はすでに unlucky な実行で失敗を宣言する。したがって と はすべての unlucky 実行で ("" の出力で) 一致する; また に対する の変更はこれらの実行時に呼び出されないため全ての lucky な実行でも一致する。したがってとなる。unlucky 実行の即時停止はショートカットであり、結果の分布には影響しない。

Game 5. は に基づいている。セットアップフェーズでは各 に対して の場合 は と およびプレースホルダー値を設定する; の場合は前述のように と を設定する。

は素数次数の巡回群であるため、 の任意の元、特に による乗算は の順列を引き起こす。したがって が で一様に分布している場合 と は に同じような一様分布を持つ。 は与えられた を調べても に関する情報を知り得ることができない。 は のメッセージの署名を提供できないが、 がそのような署名を要求する実行は直ちに失敗するため重要ではない。したがって、 は の下と全く同じように の下でも動作しとなる。

Game 6. は と同様に動作する。ただし、 が "" を出力するゲームでは は "" に加えて を出力する。ここで は が偽造署名 を出力したメッセージ のインデックスである。( は前の と同様に が成功した倍にのみ成功する。)

明らかに は と全く同じ確率で成功するためである。さらに は の場合にのみ成功する。これは を意味する。もし が の有効な署名であれば は有効な Diffie-Hellman タプルでなければならないため、 は と等しくなければならない。したがって が成功すると主張する全てのインスタンスでは も出力しなければならない。これは実際に提示される Diffie-Hellman チャレンジに対する答えである。

4.3 最適化と結論

したがってアルゴリズム は GDH 署名偽造者 を使用して CDH チャレンジを解く。残っているのは成功の最大確率を達成するためにパラメータ を最適化することである。関数 は で最大化され、以下の値を持つ (後者の等号は部分的な関数を取ることから得られる)。ここで の成功確率 は少なくともこれと同程度である。大きな に対して である。

の実行時間には の実行時間が含まれている。 によって課される追加のオーバーヘッドは からの署名とハッシュのぞれぞれの要求に対する群のべき乗を評価する必要性によって支配される。このようなべき乗の一つは最大 group action、したがって 上で最大 時間単位を使用して計算できる ([16] 参照)。 はこのような要求に 回の回答を行う必要があるため、全体の実行時間は である。ここで は の管理オーバーヘッドの残りを占める小さな定数である; 実際 は多くとも 2 である。

要約すると: 上で GDH 署名スキームを -break する偽造アルゴリズム が存在する場合、 上に GDH を -break するアルゴリズム が存在する。ここで逆に が -GDH 群なら GDH 署名スキームを -break するアルゴリズム は存在しない。ここで全ての正の に対して後者の方程式の基数は より大きいため、方程式は に書き換えられる。これで証明は完了する。

5 実験結果

5.1 実装の詳細

我々はセクション 3.4 のスキームを試した。署名は 上の曲線 での単一の乗算であることを思い出そう。署名を検証するには 上のヴェイユペアリング計算を必要とする。したがって検証は署名よりも時間がかかる。

効率のため、直接 で ( 次の多項式操作を伴う) 作業をするのではなく、 次の の拡張を使用する。 での演算を高速化するため、2 つの元を素早く乗算するための ( サイズの) ルックアップテーブルを構築する。 の元は選択された生成元に対する指数で表されるため、乗算と除算は を法とする加算に対応する。加算は恒等式 を介した乗算、除算およびテーブル検索を使用して行われる。自己同型 で使用される定数 , , も にあり、ブルートフォース検索で素早く見つけることができる。

我々は明らかな単射を使用して の元 を の元にマップする: は 内の係数を持つ 次の多項式で表され、我々は単純に 内の係数を持つ多項式として見るだけである。

我々は、類似した特性を持ち計算が簡単であることから、ヴェイユペアリングの代わりに Tate ペアリング [7] を使用する: ヴェイユペアリングは Miller のアルゴリズム [17] のイテレーションを 2 回と除算を 1 回が必要だが、Tate ペアリングは Miller のアルゴリズムを 1 回と追加のべき乗のみを必要とする。

Miller のアルゴリズムには様々な商の計算が含まれることから、分子と分母を任意の定数でスケールできるためいくつかの除算を回避することができる。我々はべき乗のような演算事にスライディングウィンドウを使用している。つまり のべき乗、Miller のアルゴリズム、曲線上の点の乗算である。符号付きスライディングウィンドウを使用し、重み付き射影座標変換に変換し (これは役に立たないかも知れない; 体の操作の実装に依存する)、いくつかの点がシステム全体で固定されているという事実を使用して、乗算をさらに高速化することができる。

Tate ペアリングの出力が の剰余類 (coset) 表現であることを思い出そう。このとき署名検証は 2 つの Tate ペアリングの出力が同じ剰余類にあることの確認から成る。これは出力から商を見つけ、それを適切な指数に挙げる (そして単位元と比較する) ことによって行われる。ただし、我々は Tate ペアリングの双線形性を利用して除算を乗算に置き換えることができる: で割ることは をかけることと等価である ( は 座標を反転することで から簡単に計算できる)。

座標は の元であり の係数を持つ最大 次の多項式として表される。出力では基数 3 の数値として表示され Base-64 でエンコードされる。923-bit 離散対数セキュリティを持つ では例示の署名は次のようになる: "KrpIcV0O9CJ8iyBS8MyVkNrMyE"。これは標準の 320-bit DSS 署名 (1024-bit 離散セキュリティを持つ) サイズの半分未満である。

5.2 実行時間

次の表は署名の検証に必要な時間を表している。2 つのペアリング計算が必要なため署名の検証は署名の生成より遙かに高価であることを思い出そう。このプログラムは 1GHz Pentium III コンピュータで動作する GNU/Linux 上で実行した。

sig-length
(bits)		 Dlog Security
[]		 curve Running Time
(seconds)
79 126 752 1.6
97 154 923 2.9
149 237 1417 9.6
163 259 1551 13.3
163 259 1551 13.4
163 265 1589 14.0

楕円曲線を使用して短い GDH 署名を得る場合、特性 3 (characteristic three) の体上の曲線を使用する必要がある。これにより曲線の計算が遅くなる。セクション 3.5 の終わりで説明したように、上記の実行時間は特性 2 の体上のより高次の種数の曲線 (genus curves) を使用して改善することができる。同様に 上の曲線 と 上の計算に対する [13] の手法はこれらの数字をわずかに改善することがある。

6 結論

我々はヴェイユペアリングに基づいた短い署名を提示した。署名の長さは有限体の 1 つの元である。DSA のような離散対数に基づく標準的な署名は 2 つの元を必要とする。 上の曲線 を使用する場合、MOV 攻撃はこの曲線の CDH 問題を の CDH 問題にマップする。したがって我々は 320-bit DSA のセキュリティに匹敵するセキュリティを持つ短い署名を小さな値の を使用して得ることができる。例えば長さ 154-bit 長の署名を取得すれば、スキームの break はサイズが約 の有限体内で Diffie-Hellman 問題を解くことになる。セクション 3.5 では同じ長さの署名を維持しながらより優れたセキュリティを実現できる未解決の問題について概説した。楕円曲線あるいはより高次の種数の曲線の構築に関する今後の研究がこの問題の解決に役立つことを期待する。

Acknowledgments

The authors thank Steven Galbraith, Alice Silverberg, and Moni Naor for helpful discussions about this work.

References

  1. ANSI X9.62 and FIPS 186-2. Elliptic Curve Digital Signature Algorithm, 1998.
  2. R. Balasubramanian and N. Koblitz. The Improbability That an Elliptic Curve Has Subexponential Discrete Log Problem under the Menezes-Okamoto-Vanstone Algorithm. Journal of Cryptology, 11(2):141–145, 1998.
  3. M. Bellare and P. Rogaway. The Exact Security of Digital Signatures: How to Sign with RSA and Rabin. In U. Maurer, editor, Proceedings of Eurocrypt ’96, volume 1070 of LNCS, pages 399–416. Springer-Verlag, 1996.
  4. D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. In J. Kilian, editor, Proceedings of Crypto ’2001, volume 2139 of LNCS, pages 213–229. Springer-Verlag, 2001.
  5. D. Chaum and T. Pederson. Wallet Databases with Observers. In E. Brickell, editor, Proceedings of Crypto ’92, volume 740 of LNCS, pages 89–105. SpringerVerlag, 1992.
  6. J.-S. Coron. On the Exact Security of Full Domain Hash. In M. Bellare, editor, Proceedings of Crypto ’2000, volume 1880 of LNCS, pages 229–235. Springer-Verlag, 2000.
  7. G. Frey, M. Muller, and H. Ruck. The Tate Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems. IEEE Tran. on Info. Th., 45(5):1717–1719, 1999.
  8. S. Galbraith. Supersingular curves in cryptography. In Proceedings of Asiacrypt ’2001, LNCS. Springer-Verlag, 2001.
  9. S. Galbraith and N. P. Smart. A Cryptographic Application of Weil Descent. In M. Walker, editor, Cryptology and Coding, volume 1746 of LNCS, pages 191–200. 532 D. Boneh, B. Lynn, and H. Shacham
  10. P. Gaudry, F. Hess, and N. P. Smart. Constructive and Destructive Facets of Weil Descent on Elliptic Curves. Technical Report CSTR-00-016, Department of Computer Science, University of Bristol, 2000.
  11. A. Joux. A One Round Protocol for Tripartite Diffie-Hellman. In W. Bosma, editor, Proceedings of ANTS IV, volume 1838 of LNCS, pages 385–394. Springer-Verlag, 2000.
  12. A. Joux and K. Nguyen. Separating Decision Diffie-Hellman from Diffie-Hellman in Cryptographic Groups. Cryptology ePrint Archive, Report 2001/003, 2001. http://eprint.iacr.org/.
  13. N. Koblitz. An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm. In H. Krawczyk, editor, Proceedings of Crypto ’98, volume 1462 of LNCS, pages 327–333. Springer-Verlag, 1998.
  14. S. Lang. Elliptic Functions. Addison-Wesley, Reading, MA, 1973.
  15. A. Menezes, T. Okamoto, and P. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory, 39(5):1639–1646, 1993.
  16. A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
  17. V. Miller. Short Programs for Functions on Curves. unpublished manuscript, 1986.
  18. I. Mironov. A Short Signature as Secure as DSA. Preprint, 2001.
  19. D. Naccache and J. Stern. Signing on a Postcard. In Proceedings of Financial Cryptography ’00, 2000.
  20. T. Okamoto and D. Pointcheval. The Gap Problems: A New Class of Problems for the Security of Cryptographic Primitives. In K. Kim, editor, Public Key Cryptography, PKC 2001, volume 1992 of LNCS, pages 104–118. Springer-Verlag, 2001.
  21. L. Pintsov and S. Vanstone. Postal Revenue Collection in the Digital Age. In Proceedings of Financial Cryptography ’00, 2000.
  22. J. H. Silverman. The Arithmetic of Elliptic Curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1986.
  23. W. C. Waterhouse. Abelian Varieties over Finite Fields. Ann. Sci. École Norm. Sup., 2:521–60, 1969.

翻訳抄

Gap Diffie-Hellman 群でのヴェイユペアリングを使用することで、一般的な RSA や DSA での署名と比べて同じ強度で短い署名を生成する方法を示す 2001 年の論文。

  1. Dan Boneh, Ben Lynn, and Havav Shacham (2004) "Short Signatures from the Weil Pairing"