All rights are reserved and copyright of this manuscript belongs to the authors.
This manuscript has been published without reviewing and editing as received
from the authors: posting the manuscript to SCIS 2007 does not prevent future
submissions to any journals or conferences with proceedings.

SCIS 2007
The 2007 Symposium on
Cryptography and Information Security
Sasebo, Japan, Jan. 23-26, 2007
The Institute of Electronics,
Information and Communication Engineers

スタンダードモデルでの CDH 仮定に基づく衝突困難ハッシュ関数を用いない
強偽造不可能性を持つ署名方式
A CDH-based Strongly Unforgeable Signature in the Standard Model
without Collision Resistant Hash Function
松田 隆宏∗
Takahiro Matsuda

ナッタポン アッタラパドゥン ∗Nuttapong Attrapadung松浦 幹太 ∗
Kanta Matsuura

花岡 悟一郎†Goichiro Hanaoka

今井 秀樹 †
Hideki Imai

あらまし 電子署名において、入力が任意長の衝突困難ハッシュ関数を用いてハッシュ値に対し署名を付ける Hash-and-Sign パラダイム [4] を用いる方式は、ハッシュ関数の衝突困難性が破れると安全ではなくなってしまう。また、実用の際は計算時間などを考慮し、SHA-1 などの標準ハッシュ関数を衝突困難であるとして利用することが多いが、近年それらの標準ハッシュ関数に対する衝突発見攻撃の報告が相次いでおり、実際には標準ハッシュ関数を使うとしても、ハッシュ関数に必要な仮定を弱めることは重要なことである。そこで衝突困難ハッシュ関数の代わりとして汎用一方向ハッシュ関数の利用を考える。Hash-and-Sign パラダイムに代わる一般的な方式 [6] は存在するが、署名長が長くなるという問題がある。また、任意長のメッセージの署名を可能にする用途以外には使えるかどうか分からない。本稿では、2006 年 Boneh らによって提案された署名方式 [3] に変形を加え、安全性の証明に必要とされる衝突
困難ハッシュ関数を用いずに、それより弱い仮定で実現できる汎用一方向ハッシュ関数を利用し、署名長を伸ばすことなく、元の方式と同じ CDH 仮定で適応的選択文書攻撃に対し強存在的偽造不可能性を持つ方式を示した。
キーワード 電子署名、強存在的偽造不可能性、汎用一方向ハッシュ関数、スタンダードモデル

1

そこで、CRHF の代わりとして、ハッシュ関数を汎用一方向ハッシュ関数 (Universal One-Way Hash Function,
UOWHF) として用いることを考える。UOWHF は Naorら [7] により導入され、後に Bellare ら [2] により、ター
ゲット衝突困難ハッシュ関数 (Target Collision Resistant
Hash Function, TCRHF) とも名付けられた鍵付きハッシュ関数である (以下本稿では汎用一方向ハッシュ関数
を TCRHF と略す)。TCRHF の性質は、メッセージを決めてから、ハッシュ鍵が与えられ、その鍵の元、メッセージと衝突を起こす他のメッセージを見つけることが難しいというもので、CRHF より弱い仮定である [8]。
TCRHF は、その安全性の定義から、Hash-and-Sign
パラダイムを利用する署名方式において単に CRHF と置き換えただけでは安全性の証明ができなくなる場合が多い。一般的な手法 [6] が存在するが、メッセージのハッ
シュ値とハッシュ鍵の連結に対して署名を作成し、さらに署名データにハッシュ鍵を追加しなければならず、署名のエレメント数が増えるという問題がある。また、この手法はハッシュ関数を Hash-and-Sign パラダイムの役割として使用しているときには利用できるが、それ以外の目的では一般的に使用できない。
Boneh らは [3] において、あるクラスにあてはまる署

はじめに

電子署名においてハッシュ関数は、安全性の証明、及び任意長のメッセージに対する署名を可能にするという目的で使われることが多い。特に、任意長のメッセージに対する署名のために、入力が任意長の衝突困難ハッシュ関数 (Collision Resistant Hash Function, CRHF) を用いて、ハッシュ値に対し署名を付ける Hash-and-Sign パ
ラダイム [4] を用いる方式は、ハッシュ関数の衝突困難性が破れると安全ではなくなってしまう。さらに、そのよ
うな署名方式の実用を考えると、計算時間等を考慮し、SHA-1 などの標準ハッシュ関数が衝突困難であるとして用いるのが普通であるが、近年それらの標準ハッシュ関数に対する衝突発見攻撃の報告が相次いでいる。従って、実際には同様に標準ハッシュ関数を使うにしても、方式
設計の際に CRHF より弱い仮定のハッシュ関数を用いることは意義のあることである。
∗

東京大学 生産技術研究所 〒 153-8505 東京都目黒区駒場 4-6-1,
Institute of Industrial Science, The University of Tokyo, 4-6-1
Komaba, Meguro-ku, Tokyo 153-8505, Japan.
† 産業技術総合研究所 情報セキュリティセンター 〒 101-0021 東
京都千代田区外神田 1-18-13, Research Center for Information
Security, National Institute of Advanced Industrial Science andTechnology, 1-18-13 Sotokanda, Chiyoda-ku, Tokyo 101-0021,
Japan.

1

呼ばれる)、以下の EUF-CMA Challenger と攻撃者 A
間の EUF-CMA game を用いて定義する [5]。

名方式の、適応的選択文書攻撃に対し強存在的偽造不可能性を持つ署名方式への変換と、具体的な CDH 仮定に基づく従来までより効率的な署名方式を示した。その方式では、CRHF をの入力空間を任意長とすると、結果的に任意長のメッセージに対する署名が可能となる。
本稿ではこの署名方式に対し、[6] のアイデアを参考に、CRHF を用いないでかつ署名のエレメント数が同じ方式を提案する。まず、あるクラスに当てはまる弱偽
造不可能性を持つ電子署名に対する強偽造不可能性を持
つ署名への変換方式を示す。そして CDH 仮定に基づく
Waters による署名方式 [9] がそのクラスに当てはまることを示し、[3] と同様 CDH 仮定で強偽造不可能性を持つ
署名方式を示す。

2

Setup. と Queries. sEUF-CMA game と同内容。
Output. Queries が終了すると、A は (m̂, σ̂) のペアを出力する。Verify(pk, m̂, σ̂) = accept かつ 1 ≤ ∀i ≤q, m̂ 6= mi ならば A の勝利となる。
定義 2 ² より大きな確率で EUF-CMA game に対し勝利できる動作時間 t のアルゴリズムが存在しない場合、電子署名 Σ は (t, q, ²)-EUF-CMA 安全性を持つという。

2.3

位数 p の有限巡回群 G における Computational DiffieHellman (CDH) 問題を解くとは、a, b ∈ Zp , g ∈ G について、g, g a , g b を与えられて g ab を出力することである。

準備
本節では、本稿で使用する言葉や安全性の定義を行う。

2.1

定義 3 ² より大きな確率で G における CDH 問題を解ける動作時間 t のアルゴリズムが存在しない場合、G において (t, ²)-CDH 仮定が成り立つという。

電子署名

電子署名 Σ は以下の 3 つのアルゴリズムからなる。

同様に、位数 p の有限巡回群 G における離散対数 (Discrete Logarithm, DL) 問題を解くとは、a ∈ Zp , g ∈ Gについて、g, g a を与えられて a を出力することである。

鍵生成 KeyGen: セキュリティパラメータ 1k を入力とし、公開鍵 pk と秘密鍵 sk の対を出力する。
署名 Sign: 秘密鍵 sk 、メッセージ m ∈ M を入力とし、正しい署名 σ を出力する。
検証 Verify: 公開鍵 pk 、メッセージ m、署名 σ を入力とし、σ がメッセージ m に対する正しい署名ならばaccept、そうでないならば reject を出力する。

2.2

Computational Diffie-Hellman 仮定と離散対数仮定

定義 4 ² より大きな確率で G における DL 問題を解ける動作時間 t のアルゴリズムが存在しない場合、G において (t, ²)-DL 仮定が成り立つという。

2.4

強存在的偽造不可能性と (弱) 存在的偽造不可能性

衝突困難ハッシュ関数と汎用一方向性ハッシュ関数

H : K × Min → Mout を鍵付きハッシュ関数、k ∈K を H のハッシュ鍵とする。ただし、Min :入力空間、Mout :出力空間、K:ハッシュ鍵空間とする。
CRHF は、CR Challenger からランダムに選ばれた
k ∈ K を与えられた攻撃者 A が、Hk (m1 ) = Hk (m2 )かつ、m1 6= m2 ∈ Min となる任意のメッセージの組(m1 , m2 ) を見つけ出すと勝利となる CR game を用いて以下の様に定義する。

電子署名の適応的選択文書攻撃に対する強存在的偽造
不可能性 (Strong Existential Unforgeability under Adaptive Chosen Message Attack, sEUF-CMA) は、以下の
sEUF-CMA Challenger と攻撃者 A 間の sEUF-CMA
game を用いて定義する [1]。

Setup. Challenger はセキュリティパラメータ 1k を入力として KeyGen を実行する。生成した pk を A に渡し、sk を保持しておく。
Queries. A は Challenger に対し、最大で q 回のクエリ
m1 , m2 , . . . , mq を発行する。Challenger はそれぞれのクエリ mi に対し、正しい署名 σi を返す。クエリ mi は過去のクエリ (m1 , . . . , mi−1 ) に対する
Challenger の返答 (σ1 , . . . , σi−1 ) に依存して適応的に発行される。
Output. Queries が終了すると、A は (m̂, σ̂) のペアを出力する。Verify(pk, m̂, σ̂) = accept かつ 1 ≤ ∀i ≤q, (m̂, σ̂) 6= (mi , σi ) ならば A の勝利となる。

定義 5 ² より大きな確率で CR game に対し勝利できる動作時間 t のアルゴリズムが存在しない場合、H は(t, ²)-CRHF であるという。

TCRHF の定義は、以下の様な TCR Challenger と攻撃者 A 間の TCR game を用いて記述される。
Step 1. A は m1 ∈ Min を出力する。
Step 2. A は、Challenger からランダムに選ばれた k ∈K を受け取る。
Step 3. Hk (m1 ) = Hk (m2 ) かつ、m2 6= m1 となるメッ
セージ m2 ∈ Min を出力すると A の勝利となる。

定義 1 ² より大きな確率で sEUF-CMA game に対し勝利できる動作時間 t のアルゴリズムが存在しない場合、電子署名 Σ は (t, q, ²)-sEUF-CMA 安全性を持つという。

定義 6 ² より大きな確率で TCR game に対し勝利できる動作時間 t のアルゴリズムが存在しない場合、H は(t, ²)-TCRHF であるという。

同様に、電子署名の適応的選択文書攻撃に対する存在的
偽造不可能性 (Existential Unforgeability under Adaptive Chosen Message Attack,EUF-CMA) は (強偽造不可能性との違いを明確にするため、弱偽造不可能性とも

2.5

2Bilinear map

本稿での Biliniar map とは以下の性質を持つものとする。G と G1 を位数が素数 p の有限巡回群とし、e は

G×G → G1 となる写像であり、1.bilinear: 全ての g ∈ G
および全ての a, b ∈ Z に対し、e(g a , g b ) = e(g, g)ab 、
2.non-degenerate: e(g, g) 6= 1、3.computable: 全てのg ∈ G に対して e を効率よく計算できる。

3

3.1

TCR-BSW 変換

次に、本稿で提案する変換方式 TCR-BSW 変換について記述する。Σ = (KeyGen, Sign, Verify) を EUF-CMA
安全性を持つ Simulatable Partitioned な署名方式とする。すなわち、Sign は S1 , S2 に分割することができ、定義 7 の性質 3 を満たすような KeyGen0 , S01 が存在する。pを十分大きな素数とし、G を位数 p の有限巡回群とする。
H : S2 ×{0, 1}∗ → Zp , G : K×S2 → Zp , F : K×G → M
をそれぞれ TCRHF とする。ただし、M, R, S1 , S2 , Kはそれぞれ本稿の 2 章、3 章の各定義で述べたものが当てはまるとする。提案する変換により得られる新しい署名方式 Σnew の記述は以下である。

提案方式

本節では、Boneh らによる “Partitioned” という概念[3] を少し強めた概念である “Simulatable Partitioned”という概念を定義する。そして、[3] において示された
変換法 (BSW 変換) に変更を加え、EUF-CMA 安全性を持つ Simulatable Partitioned な署名方式に対して本節で述べる変換 (TCR-BSW 変換と呼ぶことにする) を適応すると、BSW 変換では必要だった入力空間が任意長の CRHF を用いず、代わりに TCRHF を用いて sEUFCMA 安全性を持つ署名方式への一般的な変換ができる
ことを示す。

KeyGennew (1k ) : ランダムに g, h1 , h2 ∈ G と k 0 ∈ K を選ぶ。KeyGen(1k ) を実行し、(sk, pk) を得る。KeyGennew
に対する秘密鍵 sk 0 , 公開鍵 pk 0 はそれぞれ、
sk 0 = (sk), pk 0 = (pk, g, h1 , h2 , k 0 )定義 7 署名方式 Σ が以下の 3 つの性質を満たすとき、
Σ は Simulatable Partitioned であるという。

Signnew (sk 0 , M ) : M ∈ {0, 1}∗ に対する署名 σ は以下の様に生成する。
1. ランダムに s ∈ Zp と r ∈ R を選ぶ。
2. σ2 = S2 (sk, r) ∈ S2 を計算する。
G (σ )
3. m = g Hσ2 (M ) hs1 h2 k0 2 ∈ G を計算する。
4. σ1 = S1 (sk, Fk0 (m), r) ∈ S1 を計算する。
5. σ = (σ1 , σ2 , s) を出力する。

• 性質 1: メッセージ入力 m ∈ M に対し、署名アルゴ
リズム Sign が以下の二つの決定的アルゴリズム S1と S2 に分けることができ、sk を用いて以下の様に記述される。
1. ランダムに r ∈ R
2. σ1 = S1 (sk; m, r) ∈ S1 ,σ2 = S2 (sk; r) ∈ S2 を計算する。
3. σ = (σ1 , σ2 ) を出力する。
ただし、S1 は S1 の、S2 は S2 の出力空間、R は
S1 と S2 に使われる乱数の空間である。
• 性質 2: σ2 と m が与えられると、Verify(pk, m, (σ1 , σ2 ))= accept となるような σ1 は高々1 つしか存在しない。
• 性質 3: 以下の 2 つのアルゴリズムが存在する。
– KeyGen0 : セキュリティパラメータ 1k が与えられると、KeyGen の出力 (sk, pk) と分布が等しく、Σ に対する正しい鍵ペアである (sk 0 , pk 0 )と共に、S01 のためのトラップドア T D を出力する。すなわち、(sk 0 , pk 0 , T D) ← KeyGen0 (1k )– S01 : 決定的アルゴリズムであり、sk, σ2 , mと、KeyGen0 から出力された T D が与えられると、r を用いずに Verify(pk, m, (σ10 , σ2 )) =accept となるような正しい σ10 を出力する。
すなわち、
σ10 = S01 (sk, m, σ2 , T D) ∈ S1

Verifynew (pk 0 , M, σ) : M に対する署名 σ = (σ1 , σ2 , s)は以下の様に検証する。
G (σ )
1. m = g Hσ2 (M ) hs1 h2 k0 2 を計算する。
2. Verify(pk, Fk0 (m), (σ1 , σ2 )) を出力する。
3.2

提案方式の証明

Σnew = (KeyGennew , Signnew , Verifynew ) を 3.1 節の様に構成したとする。このとき、Σnew は、sEUF-CMA
安全性を持つことを証明する。
定理 1 以下の条件が成り立つとき、Σnew は (t, q, ²)sEUF-CMA 安全性を持つ。
• 基となっている Σ は (t, q, ²/6)-EUF-CMA 安全性を持つ Simulatable Partitioned な署名方式である• G において (t, ²/3)-DL 仮定が成り立つ• H, G, F はそれぞれ、(t, ²/6q), (t, ²/6q), (t, ²/6q)-TCRHF
証明 A を Σnew の (t, q, ²)-sEUF-CMA 安全性を破る攻撃者とする。A は最初に公開鍵 pk 0 = (pk, g, h1 , h2 , k 0 )を与えられる。
攻撃者 A は sEUF-CMA game の Queries. の段階において、1 ≤ ∀i ≤ q に対し、i 回目のクエリに Mi を発行し、σi = (σi,1 , σi,2 , si ) を受け取るとする。mi =定義 8 署名方式 Σ が定義 7 のうち性質 1 と性質 2 を満たすとき、Σ は Partitioned であるという [3]。

G 0 (σ)g Hσi,2 (Mi ) hs1i h2 k i,2 であると定義する。また、攻撃者 A は sEUF-CMA game の Output. の段階において、G (σˆ )(M̂ , σ̂ = (σˆ1 , σˆ2 , ŝ)) を出力するとし、m̂ = g Hσˆ2 (M̂ ) hŝ1 h2 k0 2
であると定義する。
以下の 6 タイプを考える。攻撃者 A が sEUF-CMA
game に勝利する場合、必ず以下のタイプ 1 からタイプ
6 のどれかにあてはまる。

“Simulatable Partitioned” という名前は、安全性証明のときにシミュレータの構成の際に必要となる性質であることから名付けた。

3

タイプ 1: 1 ≤ ∀i ≤ q, Fk0 (m̂) 6= Fk0 (mi )タイプ 2: 1 ≤ ∃i ≤ q, Fk0 (m̂) = Fk0 (mi ) ∧ m̂ 6= mi
タイプ 3: 1 ≤ ∃i ≤ q, Fk0 (m̂) = Fk0 (mi ) ∧ m̂ = mi ∧Gk0 (σˆ2 ) 6= Gk0 (σi,2 )タイプ 4: 1 ≤ ∃i ≤ q, Fk0 (m̂) = Fk0 (mi ) ∧ m̂ = mi ∧Gk0 (σˆ2 ) = Gk0 (σi,2 ) ∧ σˆ2 6= σi,2
タイプ 5: 1 ≤ ∃i ≤ q, Fk0 (m̂) = Fk0 (mi ) ∧ m̂ = mi ∧Gk0 (σˆ2 ) = Gk0 (σi,2 ) ∧ σˆ2 = σi,2 ∧ Hσˆ2 (M̂ ) 6=
Hσi,2 (Mi )タイプ 6: 1 ≤ ∃i ≤ q, Fk0 (m̂) = Fk0 (mi ) ∧ m̂ = mi ∧Gk0 (σˆ2 ) = Gk0 (σi,2 ) ∧ σˆ2 = σi,2 ∧ Hσˆ2 (M̂ ) =Hσi,2 (Mi )以下、それぞれのタイプに対する、シミュレータの構成を示す。最初にシミュレータ B はランダムに、どのタイプの偽造が来るのかを予想することとする。
タイプ 1: A1 がタイプ 1 攻撃者で、Σnew の (t, q, ²)sEUF-CMA 安全性を破れると仮定する。このとき、Σ
の (t, q, ²)-EUF-CMA 安全性を破れるシミュレータ B1 を構成する。B1 は公開鍵 pk を与えられ、B1 自身の EUFCMA game に勝利することが目的である。シミュレー
トは以下である。

Setup. B1 は公開鍵 pk 0 を以下の様に作る。
1. ランダムに g ∈ G, k 0 ∈ K を選ぶ。
2. ランダムに a, b ∈ Z∗p を選び、h1 = g a , h2 = g b とする。
3. pk 0 = (pk, g, h1 , h2 , k 0 ) を出力する。
Queries. B1 は A1 のクエリ Mi に対し、以下の様に答える。
1. ランダムに wi ∈ Zq を選び、mi = g wi とする。
2. B1 自身の Challenger に対し、Fk0 (mi ) をクエリとして尋ね、(σi,1 , σi,2 ) を得る。
3. si = (wi − Hσi,2 (Mi ) − bGk0 (σi,2 ))/a を計算する。
4. σi = (σi,1 , σi,2 , si ) を出力する。

4. ランダムに a, b ∈ Z∗p を選び、h1 = g a , h2 = g b とする。
5. ランダムに w̄ を選び、m̄ = g w̄ とする。
6. B 自身の Challenger に m̄ を出力し、k 0 ∈ K を得る。
7. pk 0 = (pk, g, h1 , h2 , k 0 ) を出力する。sk 0 = sk は保持しておく。
Queries. B2 は A2 のクエリ Mi に対し、
i 6= j のときは、σi = Signnew (sk 0 , Mi ) を出力する。
i = j のときは、以下を実行する。
1. (σj,1 , σj,2 ) = Sign(sk, Fk0 (m̄)) を計算する。
2. sj = (w̄ − Hσi,2 (Mj ) − bGk0 (σj,2 ))/a を計算する。
3. σj = (σj,1 , σj,2 , sj ) を出力する。
Output. Queries. が終了すると、A2 は偽造 (M̂ , (σˆ1 , σˆ2 , ŝ))を出力する。B2 は自身の Challenger に対し、G (σˆ )m̂ = g Hσˆ2 (M̂ ) hŝ1 h2 k0 2 を出力する。
タイプ 2 の条件より、1 ≤ ∃i ≤ q, Fk0 (m̂) = Fk0 (mi ) ∧m̂ 6= mi であり、B2 が Setup. の段階にそのような i を jとして選ぶ確率は、少なくとも 1/q である。従って、B2
は、A2 がタイプ 2 の偽造に成功するときは少なくとも1/q の確率で F についての TCR game に勝利することができる。
タイプ 3: A3 がタイプ 3 攻撃者で、Σnew の (t, q, ²)sEUF-CMA 安全性を破れると仮定する。このとき、Gにおける (t, ²)-DL 仮定を破れるシミュレータ B3 を構成する。B3 は DL 問題 (g, X) を与えられ、logg X を出力することが目的である。B3 は A3 を以下の様に走らせる。

Setup. B3 は公開鍵 pk 0 を以下の様に作る。
1. KeyGen を実行し、sk, pk を得る。
2. ランダムに a ∈ Z∗p を選び、h1 = g a , h2 = X とする。
3. ランダムに k 0 ∈ K を選ぶ。
Output. Queries. が終了すると、A1 は偽造 (M̂ , (σˆ1 , σˆ2 , ŝ))
4. pk 0 = (pk, g, h1 , h2 , k 0 ) を出力する。sk 0 = sk はを出力する。B1 は以下の様にして自身の Challenger に保持しておく。
対し、偽造を出力する。
Queries. B3 は A3 のクエリ Mi に対し、G (σˆ )
1. m̂ = g Hσˆ2 (M̂ ) hŝ1 h2 k0 2 を計算する。
σi = Signnew (sk 0 , Mi ) を出力する。
2. (Fk0 (m̂), σˆ1 , σˆ2 ) を出力する。
Output. Queries. が終了すると、A3 は偽造 (M̂ , (σˆ1 , σˆ2 , ŝ))
ここで、Σnew の定義より、Verifynew (M̂ , (σˆ1 , σˆ2 , ŝ)) =を出力する。B3 は自身の Challenger に対し、logg X =accept ならば、Verify((Fk0 (m̂), (σˆ1 , σˆ2 )) = accept であ{(Hσˆ2 (M̂ )+aŝ)−(Hσi,2 (Mi )+asi )}/(Gk0 (σi,2 )−Gk0 (σˆ2 ))り、タイプ 1 の条件より、1 ≤ ∀i ≤ q, Fk0 (m̂) 6= Fk0 (mi )を出力する。
なので、B1 は、A1 がタイプ 1 の偽造に成功するときは
これは、m̂ = mi 、すなわち、g Hσˆ2 (M̂ )+aŝ X Gk0 (σˆ2 ) =いつも EUF-CMA game に勝利することができ、Σ に対
g Hσi,2 (Mi )+asi X Gk0 (σi,2 ) という等式の両辺の logg をとっする正しい署名を偽造できる。
て整理して得られた式である。Gk0 (σˆ2 ) 6= Gk0 (σi,2 ) よタイプ 2: A2 がタイプ 2 攻撃者で、Σnew の (t, q, ²)り、分母は 0 ではない。従って、B3 は、A3 がタイプ 3
sEUF-CMA 安全性を破れると仮定する。このとき、(t, ²/q)の偽造に成功するときはいつも DL 問題を解ける。
TCRHF である F の TCR game に勝利できるシミュレー
タイプ 4: A4 がタイプ 4 攻撃者で、Σnew の (t, q, ²)タ B2 を構成する。B2 は A2 を以下の様に走らせる。
sEUF-CMA 安全性を破れると仮定する。このとき、(t, ²/q)Setup. B2 は公開鍵 pk 0 を以下の様に作る。
TCRHF である G の TCR game に勝利できるシミュレー
1. ランダムに j ∈ {1 . . . q} を選ぶ。
タ B4 を構成する。B4 は A4 を以下の様に走らせる。
2. KeyGen を実行し、sk, pk を得る。
Setup. B4 は公開鍵 pk 0 を以下の様に作る。
3. ランダムに g ∈ G を選ぶ。
4

1. ランダムに j ∈ {1 . . . q} を選ぶ。
2. KeyGen を実行し、sk, pk を得る。
3. ランダムに g, h1 , h2 ∈ G を選ぶ。
4. ランダムに r̄ ∈ R を選び、σ¯2 = S2 (sk, r̄) とする。
5. B 自身の Challenger に σ¯2 を出力し、k 0 ∈ K を得る。
6. pk 0 = (pk, g, h1 , h2 , k 0 ) を出力する。sk 0 = sk は保持しておく。
Queries. B4 は A4 のクエリ Mi に対し、
i 6= j のときは、 σi = Signnew (sk 0 , Mi ) を出力する。
i = j のときは、以下を実行する。
1. ランダムに sj ∈ Zp を選ぶ。
s G (σ¯ )2. mj = g Hσ¯2 (Mj ) h1j h2 k0 2 を計算する。
3. σj,1 = S1 (sk, Fk0 (mj ), r̄) を計算する。
4. σj,2 = σ¯2 とする。
5. σj = (σj,1 , σ¯2 , sj ) を出力する。

Setup. B6 は公開鍵 pk 0 を以下の様に作る。
1. ランダムに j ∈ {1 . . . q} を選ぶ。
2. KeyGen0 を実行し、sk, pk, T D を得る。
3. ランダムに g, h1 , h2 ∈ G, k 0 ∈ K を選ぶ。
4. pk 0 = (pk, g, h1 , h2 , k 0 ) を出力する。sk 0 = sk は保持しておく。
Queries. B6 は A6 のクエリ Mi に対し、
i 6= j のときは、 σi = Signnew (sk 0 , Mi ) を出力する。
i = j のときは、以下を実行する。
1. B6 自身の Challenger に Mj を出力し、σ¯2 ∈ S2 を得る。σj,2 = σ¯2 とする。
2. ランダムに sj ∈ Zp を選ぶ。
s G (σ¯ )3. mj = g Hσ¯2 (Mj ) h1j h2 k0 2 を計算する。
4. σj,1 = S01 (sk, Fk0 (mj ), σ¯2 , T D) を計算する。
5. σj = (σj,1 , σj,2 , sj ) を出力する。

Output. Queries. が終了すると、A6 は偽造 (M̂ , (σˆ1 , σˆ2 , ŝ))
Output. Queries. が終了すると、A4 は偽造 (M̂ , (σˆ1 , σˆ2 , ŝ)) を出力する。B6 は自身の Challenger に対し、M̂ を出力を出力する。B4 は自身の Challenger に対し、σˆ2 を出力する。
する。
A6 が sEUF-CMA game に勝利する条件により、1 ≤タイプ 4 の条件より、1 ≤ ∃i ≤ q, Gk0 (σˆ2 ) = Gk0 (σi,2 ) ∧σˆ2 6= σi,2 であり、B4 が Setup. の段階にそのような i を
j として選ぶ確率は、少なくとも 1/q である。従って、
B4 は、A4 がタイプ 4 の偽造に成功するときは少なくとも 1/q の確率で G についての TCR game に勝利できる。
タイプ 5: A5 がタイプ 5 攻撃者で、Σnew の (t, q, ²)sEUF-CMA 安全性を破れると仮定する。このとき、Gにおける (t, ²)-DL 仮定を破れるシミュレータ B5 を構成する。B5 は DL 問題 (g, X) を与えられ、logg X を出力することが目的である。B5 は A5 を以下の様に走らせる。

Setup. B5 は公開鍵 pk 0 を以下の様に作る。
1. KeyGen を実行し、sk, pk を得る。
2. h1 = X とする。
3. ランダムに h2 ∈ G, k 0 ∈ K を選ぶ。
4. pk 0 = (pk, g, h1 , h2 , k 0 ) を出力する。sk 0 = sk は保持しておく。
Queries. B5 は A5 のクエリ Mi に対し、
σi = Signnew (sk 0 , Mi ) を出力する。

∀i ≤ q, (M̂ , σˆ1 , σˆ2 , ŝ) 6= (Mi , σi,1 , σi,2 , si ) であり、タイプ 5 の条件と同様にタイプ 6 でも、σˆ2 = σi,2 ∧ ŝ = si 。
また、Simulatable Partitioned の性質 2 より、σˆ2 = σi,2ならば、σˆ1 = σi,1 。これらとタイプ 6 の条件を合わせて、
1 ≤ ∃i ≤ q, M̂ 6= Mi ∧ σˆ2 = σi,2 ∧ Hσˆ2 (M̂ ) = Hσi,2 (Mi )となる。B6 が Setup. の段階にそのような i を j として選ぶ確率は、少なくとも 1/q である。従って、B6 は、A6がタイプ 6 の偽造に成功するときは少なくとも 1/q の確率で H についての TCR game に勝利することができる。
以上、全てのタイプに対するシミュレータの構成法を示した。全ての A に対するシミュレートは完全である。
タイプ 1 は基となる署名 Σ の EUF-CMA 安全性を、タ
イプ 3,5 は離散対数仮定を、タイプ 2,4,6 は TCRHF の安全性を、それぞれ破るのに使用できることを示した。
以上により、定理 1 は証明された。

3.3

備考

離散対数系の仮定に基づく方式の場合、鍵生成の際に群 G(位数 p) の元を複数作成する必要があるときは、先に一つの元をランダムに生成し、残りの元は離散対数を Zp
Output. Queries. が終了すると、A5 は偽造 (M̂ , (σˆ1 , σˆ2 , ŝ))から選んでから作ることができる。定義 7 の Simulatableを出力する。B5 は自身の Challenger に対し、Partitioned の性質 3 の T D としては、例えばそのようlogg X = (Hσˆ2 (M̂ ) − Hσi,2 (Mi ))/(si − ŝ) を出力する。
な値があてはまる。この場合、性質 1 と性質 2 を満たす
ここで、m̂ = mi ∧ σˆ2 = σi,2 より、ならば、性質 3 を満たす S01 が存在するような方式も少Hσi,2 (Mi ) si
Hσˆ2 (M̂ ) ŝg
X =g
X である。また、タイプ 5 のなくないと考えられる。
条件 Hσˆ2 (M̂ ) 6= Hσi,2 (Mi ) より、必ず ŝ 6= si である。
よって、等式の両辺の logg を取って整理すると、Output.
4 CDH 仮定に基づく具体的な署名方式
での B5 の出力する値が得られる。従って、B5 は、A5
Waters 署名 [9] は、G において (t, ²/8(n + 1)q)-CDH
がタイプ 5 の偽造に成功するときはいつも DL 問題を解仮定が成り立つとすると、スタンダードモデルで (t, q, ²)くことができる。
EUF-CMA 安全性を持つ署名方式である [3]。以下に KeyGen
タイプ 6: A6 がタイプ 6 攻撃者で、Σnew の (t, q, ²)アルゴリズムを示す。
sEUF-CMA 安全性を破れると仮定する。このとき、(t, ²/q)KeyGen :TCRHF である H の TCR game に勝利できるシミュレー
1. ランダムに g, g2 ∈ G を選ぶ。
タ B6 を構成する。B6 は A6 を以下の様に走らせる。
5

2. ランダムに α ∈ Zp を選び、g1 = g α を計算する。
3. ランダムに u0 , u1 , u2 , . . . , un ∈ G を選ぶ。
4. sk = g2α , pk = (g, g1 , g2 , u0 , u1 , u2 , . . . , un ) を出力する。

2. m0 = Fk0 (m) を計算する。
m0i を m0 の i 番目のビット (i ∈ {1, . . . , n}) とする。
Qn?
m0
3. e(σ1 , g) = e(σ2 , u0 i=1 ui i ) · e(g1 , g2 )が成りたつならば accept, そうでないならば rejectを出力する。

このとき、3. 以降を
3. ランダムに β 0 , β1 , β2 , . . . , βn ∈ Zp を選び、u0 =0g β , u1 = g β1 , u2 = g β2 , . . . , un = g βn を計算する。
4. sk = g2α , pk = (g, g1 , g2 , u0 , u1 , u2 , . . . , un ), T D =(β 0 , β1 , β2 , . . . , βn ) を出力する。

系 1 以下の条件が成り立つとき、上記署名方式は (t, q, ²)sEUF-CMA 安全性を持つ。
• G において (t, ²/48(n + 1)q)-CDH 仮定が成り立つ• H, G, F はそれぞれ、(t, ²/6q), (t, ²/6q), (t, ²/6q)-TCRHFとしたアルゴリズムを KeyGen0 とすると、KeyGen0 から出力された sk, pk の対は KeyGen から出力された sk, pkの対と同一視することができるのは明らかである。
Waters 署名が Partitioned な署名であることは [3] で示されており、その際の S1 と S2 は以下である。
Qni r
σ1 = S1 (sk, m, r) = sk · (u0 i=1 um∈Gi )rσ2 = S2 (sk, r) = g ∈ G

証明 Waters の署名が G における (t, ²/8(n+1)q)-CDH
仮定が成り立つと、スタンダードモデルで (t, q, ²)-EUFCMA 安全性を持つ署名方式であり、かつ Simulatable
Partitioned であることは既に示した。このとき、G において明らかに (t, ²/3)-DL 仮定は成り立っている。従って、定理 1 の条件を満たしたので、上記署名方式が sEUFCMA 安全性を持つことが示された。

ただし、mi ∈ {0, 1} は m ∈ {0, 1}n の i 番目のビット、
u0 , u1 , . . . , un ∈ G, r ∈ Zp , sk ∈ G である。ここで、先ほどの T D と σ2 を用いて σ1 を変形すると、
Qn
Qn
rβ 0
i r
σ1 = sk · (u0 i=1um(g rβi mi ))i ) = sk · (g
i=1
P
0 Pn
β0 + nr β + i=1 βi mi
i=1 βi mi= sk · (σ2 )= sk · (g )5

本稿では、まず署名方式に対する Simulatable Partitioned の概念を定義した。そして、その概念にあてはまる
EUF-CMA 安全性を持つ署名方式に対する sEUF-CMA
安全性を持つ署名方式へのスタンダードモデルでの一般的な変換法とその安全性証明を示した。我々の方式は、
任意長入力の CRHF を必要としない。さらに、CDH 仮定に基づく Waters の署名 [9] が Simulatable Partitionedにあてはまることを示し、我々の提案方式を適用することでスタンダードモデルで CDH 仮定に基づき、任意長
入力の CRHF を用いずに強存在的偽造不可能性を持つ
署名方式を示した。

と書くことができ、r を使わずに sk, m, σ2 , T D の関数
として σ1 を表せ、正しい σ1 を作ることができる。この等式の最後の式で S01 (sk, m, σ2 , T D) を定義すれば、S01 、
KeyGen0 、そして T D は定義 7 の性質 3 を満たすので、Waters 署名が Simulatable Partitioned であることを示すことができた。
従って、定理 1 をそのまま Waters の署名に当てはめれば、目標である CDH 仮定に基づき、衝突困難ハッシュ関数は用いずに、sEUF-CMA 安全性を持つ署名方式が得られる。構成は以下の通りである。
p を十分大きな素数とし、G を位数 p の有限巡回群とする。H : G×{0, 1}∗ → Zp , G : K×G → Zp , F : K×G →{0, 1}n をそれぞれ TCRHF とする。e : G × G → G1
を Bilinear map とする。

参考文献
[1] J.H.An, Y.Dodis, T.Rabin, “On the Security of Joint Signature and Encryption,” In L.R.Knudsen, editor, Proceedingsof EUROCRYPT 2002, LNCS 2332, pp. 83-107, SpringerVerlag, 2002.
[2] M.Bellare, P.Rogaway, “Collision-Resistant Hashing: Towards Making UOWHFs Practical,” In Buston S.Kaliski Jr.,
editor, Advances in Cryptology — CRYPTO 1997, LNCS
1294, pp. 320-335,1997.
[3] D.Boneh, E.Shen, B.Waters, “Strongly Unforgeable Signatures Based on Computational Diffie-Hellman,” In Proceedings of PKC 2006, LNCS 3958, pp. 229-240, SpringerVerlag, 2006.
[4] I.Damgard, “Collision Free Hash Functions and Public Key
Signature Schemes,” In Proceedings of EUROCRYPT’87,
LNCS 304, pp. 203-216, Springer-Verlag, 1988.
[5] S.Goldwasser, S.Micali, R.Rivest, “A Digital Signature
Schemes Secure Against Adaptive Chosen-Message Attacks,” SIAM J. Computing, 17(2):281-308, 1988.
[6] I.Mironov, “Collision Resistant No More: Hash-and-Sign
Paradigm Revisited,” In Proceedings of PKC 2006, LNCS
3958, pp. 140-156, Springer-Verlag, 2006.
[7] M.Naor, M.Yung, “Universal One-Way Hash Functions andtheir Cryptographic Applications,” In Proceedings of theTwenty First Annual ACM Symposium on Theory of Computing, pp. 33-43, 15-17 May 1989.
[8] D.R.Simon, “Finding Collision on One-Way Street: Can
Secure Hash Functions Be Based on General Assumptions?,” In K.Nyberg, editor, Advances in Cryptology — EUROCRYPT 1998, LNCS 1403, pp. 334-345, Springer, 1998.
[9] B.Waters, “Efficient Identity-Based Encryption without
Random Oracles,” In R. Cramer, editor, Advances in EUROCRYPT 2005, LNCS 3494, pp. 114-127, Springer-Verlag,
2005.

KeyGennew : ランダムに g ∈ G を選ぶ。ランダムにα ∈ Zp を選び、g1 = g α を計算する。ランダムに
g2 , h1 , h2 , u0 , u1 , . . . , un ∈ G と k 0 ∈ K を選ぶ。U =(u1 , . . . , un ) とおく。以下を出力する。
sk = g2α , pk = (g, g1 , g2 , h1 , h2 , u0 , U, k 0 )Signnew : M ∈ {0, 1}∗ に対する署名 σ は以下の様に生成する。
1. ランダムに s, r ∈ Zp を選ぶ。
2. σ2 = g r ∈ G を計算する。
G (σ )
3. m = g Hσ2 (M ) hs1 h2 k0 2 ∈ G を計算する。
4. m0 = Fk0 (m) を計算する。
m0i を m0 の i 番目のビット (i ∈ {1, . . . , n}) とする。
Qnm0
5. σ1 = g2α · (u0 i=1 ui i )r ∈ G を計算する。
6. σ = (σ1 , σ2 , s) を出力する。
Verifynew : M に対する署名 σ = (σ1 , σ2 , s) は以下の様に検証する。
G (σ )
1. m = g Hσ2 (M ) hs1 h2 k0 2 ∈ G を計算する。

まとめ

6