NNモデル掲示板

Pairing による暗号プロトコルの効率化例
古川 潤
日本電気株式会社
[email protected]
ID ベース暗号とペアリング
1984 年
2000 年
2001 年
2001 年
2007 年
Shamir
境, 大岸, 笠原
Cocks
Boneh, Franklin
Boneh,Gentry,Hamburg
アイディア
ペアリング
平方剰余問題
ペアリング
平方剰余問題
1125 + |m|
2048 · |m|
1125 + |m|
1025 + |m|(計算大)
暗号文長, 計算量共に効率的な ID ベース暗号はペアリングを使っ
たものしか考案されていない.
ID ベース暗号以外の暗号プロトコルに於ても, ペアリングはプロ
トコルの効率を上げるのに極めて有効な道具である.
目次
ペアリング
ペアリングに関係する計算量的仮定
Gap co-Diffie-Hellman 仮定と短い署名
q-strong Diffie-Hellman 仮定と短い署名
q-SDH に類似の仮定
合成数位数のペアリングを持つ楕円曲線
MNT 曲線
ペアリング
双線形写像を持つ群
1. G1 , G2 , と GT を, 素数位数 p の巡回群とする.
2. e : G1 × G2 → GT は, 効率的に計算できる写像で,
2.1 双線形性: 全ての u ∈ G1 , v ∈ G2 , と α, β ∈ Z/pZ に関して,
e(u α , v β ) = e(u, v )αβ が成り立つ.
2.2 非縮退性: もし g1 ∈ G1 , g2 ∈ G2 が, それぞれ, G1 , G2 の生成
子であるならば,e(g1, g2 ) は GT の生成子である.
効率的に計算できる準同型写像
1. φ : G1 → G2 , φ−1 .
2. σ : G2 → G1 .
が知られているかは曲線による.
ペアリングに関係する計算量的仮定
多くの仮定が使われている. 例えば,
1. bilinear Diffie-Hellman 仮定
2. Gap co-Diffie-Hellman 仮定
3. q-Strong Diffie-Hellman 仮定
4. Decision -bilinear Diffie-Hellman exponent 仮定
5. Decision weak -bilinear Diffie-Hellman inversion 仮定
6. Subgroup decision 仮定
7. Asymmetric external decisional Diffie-Hellman 仮定
8. Symmetric external decisional Diffie-Hellman 仮定
等, その他多数ある.
Gap co-Diffie-Hellman 仮定と短い署名
Definition
準同型写像 σ : G2 → G1 は効率的に計算可能である.
α ∈ Z/pZ, h ∈ G1 がランダムに選ばれた上で, (g2 , g2α , h) が与え
られたときに, hα を計算する事が難しい.
一方, ペアリングが計算できるので, ある β ∈ Z/pZ に関して,
(g2 , g2α , h, hβ ) が与えられたとき, α = β が成り立つかは,
e(hβ , g2 ) = e(h, g2α ) が成り立つかを確認すれば簡単に判別できる.
短い署名 - ランダムオラクルモデルで
署名方式 (鍵生成, 署名生成, 検証): G1 , G2 , GT , e, g1 , g2 , 暗号学的
なハッシュ関数 H : {0, 1}∗ → G1 が与えられているとする.
鍵生成: ランダムに χ ∈ Z/pZ を選ぶ. 秘密鍵 χ と公開鍵
v = g2χ を出力する.
署名生成: メッセージ M と秘密鍵 χ が入力される. 署名
s = H(M)χ を出力する.
署名検証: メッセージと署名の組 (M, s), 公開鍵 v が入力され
る. e(s, g2 ) = e(H(M), v ) ならば署名は正当とする.
G1 の要素の表現が 172 ビット程度で, 妥当な安全性が確保でき
る. よって, 署名長を 172 ビット程度に押さえることができる.
アグリゲート署名
先の短い署名方式では, 複数の署名をまとめて一つの署名とで
きる.
アグリゲート署名方式 (鍵生成, 署名生成, 検証, アグリゲート, ア
グリゲート検証):
アグリゲート: 公開鍵 vi を持つ署名者 i の, メッセージ Mi に対
する署名を si とする. 署名者の集合 U に対して,
si )i ∈U が与えられる. アグリゲート署名
(Mi ,
s = i ∈U si を出力する.
アグリゲート検証: 署名者集合, メッセージの集合, アグリゲート
署名の組 (U, {Mi }i ∈U , s) と公開鍵の集合 {vi }i ∈U が
与えられる. e(s, g2 ) = i ∈U e(H(Mi ), vi ) ならば署
名は正当とする.
署名の長さが, 署名者の人数によらない.
q-strong Diffie-Hellman 仮定と短い署名
Definition
準同型写像 σ : G2 → G1 は効率的に計算可能であり, g1 = σ(g2 ).
2
q
α ∈ Z/pZ がランダムに選ばれた上で, (g1 , g2 , g2 α , g2 α , . . . , g2 α )
が与えられたときに,
組 (b, γ) ∈ G1 × Z/pZ で, b α+γ = g1 を満たすものを計算する事
が難しい.
q は攻撃者の動作時間程度を想定している. この仮定は次の
strong-RSA 仮定の類似物として考案された.
Definition
素数 p, q がランダムに選ばれ, n = pq として, g ∈ (Z/nZ)∗ もラ
ンダムに選ばれた上で, n, g が与えられたときに,
組 (b, γ) ∈ (Z/nZ)∗ × Z で, b γ = g を満たすものを計算する事が
難しい.
短い署名
署名方式 (鍵生成, 署名生成, 検証): G1 , G2 , GT , e, g2 , g1 = σ(g1 )
が与えられているとする.
鍵生成: ランダムに χ, ψ ∈ Z/pZ を選ぶ. 秘密鍵 χ, ψ と公開
χ
ψ
鍵 u = g2 , v = g2 を出力する.
署名生成: メッセージ μ ∈ Z/pZ と秘密鍵 χ, ψ が入力される.
ランダムに ρ ∈ Z/pZ を選び, 署名
(ρ, s = g1 1/χ+μ+ψρ ) を計算して出力する.
署名検証: メッセージと署名の組 (μ, (ρ, s)), 公開鍵 u, v が入力
μ
される. e(s, u · g2 v ρ ) = e(g1 , g2 ) ならば署名は正当
とする.
その長さが 341 ビット程度の署名で, 妥当な安全性が確保できる.
グループ署名
グループ署名システムは, 管理者, メンバー, 検証者が存在する.
管理者はグループのメンバーの登録を行う.
グループのメンバーは, グループを代表する署名「グループ
署名」を生成できる.
誰でも検証者として, グループ署名を検証する事ができる.
管理者は, グループ署名から署名者を特定することができる.
そして, 以下の要件を満たす.
管理者以外は, グループ署名から, それを生成したメンバーを
特定することができない.
各グループメンバー本人以外は, この本人が管理者により特
定されるグループ署名を生成することができない.
管理者以外は, いずれの既存のグループメンバーの署名とも
特定されなく, かつ検証者が正当と見做すグループ署名を生
成できない.
管理者
メンバ登録
メンバ追跡
署名生成
メンバー
署名
署名検証
検証者
短いグループ署名
ハッシュ関数を用いない署名方式があると, これを用いて効率的
なグループ署名が構成できる可能性が高い.
構成方法の概要:
管理者は, 署名方式と暗号方式の, 公開鍵-秘密鍵対をそれぞ
れ (pks , sks ), (pkc , skc ) を生成し, (pks , pkc ) を公開する.
メンバーの登録は, 管理者が sks を用いてメンバーの ID に対
する署名を発行する.
グループ署名は, メンバーの ID の pkc の暗号文 C と, “ある
ID が存在し, C が ID の暗号文で, ID に対する sks の署名の
知識がある” 事の非対話的零知識証明 P とする.
署名者の追跡は, 暗号文 C を復号すれば良い.
署名方式がハッシュ関数を用いないと, P が効率的に構成できる場
合が多い. 二つ目の短い署名はハッシュ関数を用いていなかった.
具体的な構成例に, Boneh-Boyen-Shacham [BBS,04],
Nguyen-Naini [NN,04], Furukawa-Imai [FI,05] 等がある.
Strong-RSA と q-strong Diffie-Hellman (q-SDH)
Strong-RSA にその安全性を依拠するプロトコルは, 次のような特
徴を持って q-strong Diffie-Hellman にその安全性を依拠するプロ
トコルで代替構成可能であることが多い. 両者はプロトコルの外
観, その安全性の証明方法にある種の類似性を持ち, 代替構成され
たプロトコルの方が効率的となる.
例えば, 以下の方式に上記代替構成の例を見ることができる.
1. ランダムオラクルを必要としない署名
2. グループ署名
3. Dynamic Accumulator (グループ署名においてメンバーを失
効するのに有効な道具)
q-SDH に類似の仮定
Decision -bilinear Diffie-Hellman exponent 仮定.
Definition
準同型写像 φ : G2 → G1 , φ−1 は効率的に計算可能.
α ∈ Z/pZ, h ∈ G1 がランダムに選ばれた上で,
2
+2
2
(h, g2 , g2 α , g2 α , . . . , g2 α , g2 α , . . . , g2 α ) が与えられたときに,
+1
e(h, g1 )α とランダムに選ばれた T ∈ GT を識別する事が難しい.
放送型暗号
暗号化は, メッセージと鍵と受信者集合から暗号文を生成
する.
復号は, 暗号文と対応する受信者集合と, 受信者集合に属する
受信者の秘密鍵から, メッセージを復元する.
暗号文と受信者の秘密鍵の長さが, 受信者集合に依存せずにどち
らも定数となる方式はペアリングが現われるまで存在しなかった.
放送型暗号の一方式 [BGW,05]
鍵生成:
公開鍵 = (h, h1 , . . . , h ,
α
h+2 , . . . , h2 , d0 )
+2
= (h, hα , . . . , h , hα
2
, . . . , hα , hβ )
(受信者 i の秘密鍵)i =1,..., = (d1 , . . . , d )
= (h1 β , . . . , h β )
暗号化: 受信者集合 S が与えられる.
配付鍵 = e(h1 , h )τ = e(h, h+1 )τ
暗号文S
= (c1 , c2 )
⎛
= ⎝hτ , (d0
⎞
h+1−j )τ ⎠
j∈S
暗号文も, 各自の秘密鍵も定数長であり, S は制限されない.
復号:
⎛
⎝hτ , (d0
i
⎝hτ /α , (di
i
⎞
i
h+1−j+i )τ /α ⎠
⎝hiτ , hτ /α · (di
+1
⎝e(hiτ , di
⎝e(hiτ , di
⎞
h+1−j+i )τ ⎠
j∈S,j=i
j∈S,j=i
⎛
=
i
⎛
⇒
h+1−j )τ ⎠
j∈S
⎛
=
⎞
j∈S
⎛
=
j∈S,j=i
i
τ /α
h+1−j+i ), e(hi , h+1 ) · e(hi , (di
h+1−j+i ), e(h, h+1 )τ · e(hiτ , di
j∈S,j=i
j∈S,j=i
⎞
h+1−j+i )τ )⎠
⎞
h+1−j+i )⎠
その他の q-SDH に類似の仮定
Decision weak -bilinear Diffie-Hellman inversion 仮定
Definition
準同型写像 φ : G2 → G1 , φ−1 は効率的に計算可能.
α ∈ Z/pZ, h ∈ G1 がランダムに選ばれた上で,
2
(h, g2 , g2 α , g2 α , . . . , g2 α ) が与えられたときに,
+1
e(h, g2 )α とランダムに選ばれた T ∈ GT を識別する事が難しい.
上記仮定に安全性が依拠する, 暗号文が定数長さの階層型 ID ベー
ス暗号が知られている [BBG,05].
合成数位数のペアリングを持つ楕円曲線
1. G と GT を, p, q を素数とする合成数位数 n = pq の巡回群と
する.
2. e : G × G → GT は, 効率的に計算できる写像で,
2.1 双線形性: 全ての u, ∈ G, と α, β ∈ Z/nZ に関して,
e(u α , u β ) = e(u, u)αβ が成り立つ.
2.2 非縮退性: もし g ∈ G が, G の生成子であるならば,e(g , g ) は
GT の生成子である.
性質と仮定
G, GT の位数 p の部分群を Gp , GTp , 位数 q の部分群を Gq , GTq と
し, それぞれの生成子を gp , gTp , gq , gTq とする. すると,
e(gp , gq ) = 1 であり,
e(gp , gp ), e(gq , gq ) はそれぞれ GT の位数 p, q の部分群の生
成子となる.
また, 次の様な仮定が考えられる
Definition
(Subgroup decision 仮定) 素数 p, q がランダムに選ばれてたうえ
で, さらにランダムに選ばれた g ∈ Gp が与えられたときに, ラン
ダムに与えられた h ∈ G と h ∈ Gp を識別する事が難しい.
0 か 1 のコミットメントである事の非対話的零知識証明
与えられた c に関して, m ∈ {0, 1}, w ∈ Z/pZ なる m, w が存在
して c = g m hw が成り立つ事の非対話的零知識証明.
共通パラメタ: ランダムに選ばれた g ∈ G, h ∈ Gp .
共通入力 / 証明者の証拠: c / m, w .
証明生成: r ∈ (Z/nZ)∗ をランダムに選び,
π1 = hr , π2 = (g 2m−1 hw )w /r , π3 = g r .
検証: e(c, c/g ) = e(π1 , π2 ), (π1 , g ) = e(h, π3 ) を確認.
正当性:
h
⇒ “π ∈ G .
∈ Gp ⇒ “e(h, π3 ) = e(π1 , g ) ∈ GTp
1
p
⇒ “e(π1 , π2 ) = e(c, c/g ) ∈ GTp
⇒ “c ∈ Gp or c/g ∈ Gp .
零知識: 略.
効率的な非対話的零知識証明
任意の回路 C が与えられた時に, C (w ) = 1 なる w が存在するこ
とを証明できれば良い. 任意の回路 C は高々定数倍の NAND
ゲートで表現できるので, C の NAND ゲート表現の各ゲートの入
出力を暗号化し, ゲートの演算が正しく行われている事を証明す
れば良い.
Lemma
b0 , b1 , b2 ∈ {0, 1} とし, b2 = b0 NAND b1 ならば，
b0 + b1 + 2b2 − 2 ∈ {0, 1}.
b0 , b1 , b2 の暗号文が c0 , c1 , c2 の場合, c0 c1 c22 g −2 が 0 か 1 の暗号
文であることを証明すれば良い.
その他の応用
1. ランダムオラクルモデルによらない比較的効率的なグループ
署名 Boyen-Waters [XBW,06].
2. 不正者のブラックボックス追跡が可能な, 受信者が複数の暗
号方式 Boneh-Gentry-Waters[BGW,05].
3. 不正者のブラックボックス失効が可能な放送型暗号方式.
Boneh-Waters [BW,06], Furukawa-Attrapadung [FA,07].
4. 暗号化された数値の大きさ問い合わせプロトコル
Boneh-Waters [BW,07].
MNT 曲線
MNT (Miyaji-Nakabayashi-Takano) 曲線 [MNT,00] では効率的に
計算できる σ : G2 → G1 は知られているが逆の関数は知られてい
ない. ペアリングは G1 の元と G2 の元から計算する為, 次の仮定
も現在の知識では成り立つ.
Definition
(Asymmetric external decisional Diffie-Hellman 仮定)
G1 上の Diffie-Hellman 判別問題が難しいとする.
σ(G2 ) = 1 となるように G2 を選ぶ事ができる. この時，次の仮定
も現在の知識では成り立つ.
Definition
(Symmetric external decisional Diffie-Hellman 仮定)
G1 , G2 上の Diffie-Hellman 判別問題が難しいとする.
Asymmetric external DDH 仮定の利用例
グループ署名システムでは, 管理者には署名者が特定可能で
なければならない. そのため, 署名者の ID の暗号文をグルー
プ署名に含ませるのが, 方式の典型的な構成方法である.
暗号方式として使いやすいのは ElGamal 暗号であるが, これ
は Diffi-Hellman 判別方式が難しい事が要求される.
Boneh-Boyen-Shacham [BBS,04] の主な方式, Nguyen-Naini
[NN,04] の方式等ではペアリングを持つ楕円曲線を使い,
Diffi-Hellman 判別方式が易しい事を想定しているため, 暗号
文が複雑なものとなっており, 効率を落とす原因となって
いる.
Boneh-Boyen-Shacham [BBS,04] の副方式では, Asymmetric
external DDH 仮定の元で ElGamal 暗号文を使い効率を上げ
る方法も提案している.
Symmetric external DDH 仮定の利用例
ランダムオラクルモデルによらないが, generic group model
で証明可能なグループ署名
Ateniese-Camenisch-Hohenberger-Medeiros [ACHM,05].
管理者の鍵対 (PK , SK ), メンバーの鍵対 (pk, sk) と鍵証明書
SignSK (pk), 文書 m とした時のグループ署名を,
(SignSK (pk) , pk , Signsk (m) とする. ここで, SignSK (pk) , pk は SignSK (pk), pk を変換して, 管理者以外はオリジナルにリ
ンクすることが困難にしたもの.
(PK , SK ) = ((g2s , g2t ), (s, t)). ランダムに選んだ a ∈ G1 に対
して, SignSK (sk) = (a, at , as+st(sk) , a(sk) , a(sk)t ).
(pk, sk) = (g , g (sk) ).
Signsk (m) = (g1v , g2 1/((sk)+v ) , g2 1/(v +m) ).
リンクできない変換をするため G1 上での DH 判別問題は難しい
必要がある.
引用文献
[ACHM,05] Giuseppe Ateniese, Jan Camenisch, Susan Hohenberger,
Breno de Medeiros: Practical Group Signatures without Random
Oracles. Cryptographic eprint archive 2005/385
[BB,04] Dan Boneh, Xavier Boyen: Short Signatures Without
Random Oracles. EUROCRYPT 2004: 56-73
[BBG,05] Dan Boneh, Xavier Boyen, Eu-Jin Goh: Hierarchical
Identity Based Encryption with Constant Size Ciphertext.
EUROCRYPT 2005: 440-456
[BBS,04] Dan Boneh, Xavier Boyen, Hovav Shacham: Short Group
Signatures. CRYPTO 2004: 41-55
[BF,01] Dan Boneh, Matthew K. Franklin: Identity-Based
Encryption from the Weil Pairing. CRYPTO 2001: 213-229
[BGH,07] D. Boneh, C. Gentry and M. Hamburg: Space-Efficient
Identity Based Encryption Without Pairings.
[BGLS,03] Dan Boneh, Craig Gentry, Ben Lynn, Hovav Shacham:
Aggregate and Verifiably Encrypted Signatures from Bilinear Maps.
EUROCRYPT 2003: 416-432
[BGW,05] Dan Boneh, Craig Gentry, Brent Waters: Collusion
Resistant Broadcast Encryption with Short Ciphertexts and Private
Keys. CRYPTO 2005: 258-275
[BLS,01] Dan Boneh, Ben Lynn, Hovav Shacham: Short Signatures
from the Weil Pairing. ASIACRYPT 2001: 514-532
[BSW,06] Dan Boneh, Amit Sahai, Brent Waters: Fully Collusion
Resistant Traitor Tracing with Short Ciphertexts and Private Keys.
EUROCRYPT 2006: 573-592
[BW,06] Dan Boneh, Brent Waters: A fully collusion resistant
broadcast, trace, and revoke system. ACM Conference on Computer
and Communications Security 2006: 211-220
[BW,07] Dan Boneh, Brent Waters: Conjunctive, Subset, and Range
Queries on Encrypted Data. TCC 2007: 535-554
[XBW,06] Xavier Boyen, Brent Waters: Compact Group Signatures
Without Random Oracles. EUROCRYPT 2006: 427-444
[C,01] Clifford Cocks: An Identity Based Encryption Scheme Based
on Quadratic Residues. IMA Int. Conf. 2001: 360-363.
[FA,07] Jun Furukawa, Nuttapong Attrapadung: Fully Collusion
Resistant Black-Box Traitor Revocable Broadcast Encryption with
Short Private Keys. ICALP 2007: 496-508
[FI,05] Jun Furukawa, Hideki Imai: An Efficient Group Signature
Scheme from Bilinear Maps. ACISP 2005: 455-467
[GOS,06] Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect
Non-interactive Zero Knowledge for NP. EUROCRYPT 2006:
339-358
[MNT,00] Atsuko Miyaji, Masaki Nakabayashi, Shunzo Takano:
Characterization of Elliptic Curve Traces under FR-Reduction. ICISC
2000: 90-108
[NN,04] Lan Nguyen, Reihaneh Safavi-Naini: Efficient and Provably
Secure Trapdoor-Free Group Signature Schemes from Bilinear
Pairings. ASIACRYPT 2004: 372-386
[SOK,00] Ryuichi Sakai, Kiyoshi Ohgishi, Masao Kasahara:
Cryptosystems based on pairing. In SCIS 2000.