Weil Pairing を用いた ID ベース暗号の仕組みと問題点
工藤麻美

1(指導教員: 金子 晃)

はじめに

Encrypt: params, ID と平文 M を入力すると暗号文C を返す．
Decrypt: params, ID，暗号文 C と秘密鍵 d を入力す
ると平文 M を返す．
このようなシステムを実現できる双線形写像のひとつの例を Weil Pairing を用いて作ることができる．

1984 年，Shamir は公開鍵暗号方式の公開鍵を，任意の文字列で作れないかと考えた．その当初の動機は，
e-mail システムの認証処理を簡単にするためだった．
例 え ば ，Alice が Bob の メ ー ル ア ド レ ス
bob@hotmail.com 宛 に メ ー ル を 送 る と き ，Alice
は文字列 “bob@hotmail.com” を Bob の公開鍵として使ってメッセージを暗号化する．そのとき Aliceは Bob の公開鍵の証明書を入手する必要はない．
Bob が暗号化されたメールを受け取ったら，Bob はPKG(Private Key Generator) と呼ばれる第三者に連絡を取り，彼の秘密鍵を入手する．そして Bob は暗号化されたメールを読むことができるようになる．既存の安全な e-mail 基盤とは異なり，Bob がまだ自分の公開鍵を setup していなくても，Alice は Bob に暗号化したメールを送ることができる．
ここでは，このようなシステムを有限体上の楕円曲線を用いて作る方法を紹介する．

24

安全性の概念公開鍵暗号の安全性の概念には色々あるが、ここでは暗号文単独攻撃に対する一方向性と，選択暗号文攻撃に対する強秘匿性を考える．これらは公開鍵暗号で一般的に認められている安全性の概念である．ただしID ベース暗号では更に選択 ID 攻撃というものを加えてこれらの安全性を考察する．

5

Weil Pairing を使った ID ベース暗号

5.1

Weil Pairing

ある素数 q に対して，p を p = 2 mod 3 と p = 6q−1を満たす素数とする．E を y 2 = x3 + 1 で定義されるFp 上の楕円曲線とする．この曲線に関するいくつかの事実を述べる．
Fact1: x3 +1 は Fp 上の置換なので Fp 上の楕円曲線 E
は p+1 個の点を持つ．O を無限遠点とする．P ∈ E/Fpを位数 q = (p + 1)/6 の点とする．この点が生成する群を Gq で表す．
Fact2: 1 6= ζ ∈ Fp2 を x3 − 1 = 0 mod p の解とする．そのとき，写像 φ(x, y) = (ζx, y) は曲線 E 上の点の群の自己同型写像である．P = (x, y) ∈ E/Fp のとき φ(P ) ∈ E/Fp2 だが，φ(P ) ∈/ E/Fp となる．したがって P ∈ E/Fp は φ(P ) ∈ E/Fp2 と線形独立である．
Fact3: 点 P と点 φ(P ) は線形独立なので，これらはZq × Zq と同型な群を生成する．この群の点を E[q] で表す．
µq を位数 q = (p + 1)/6 の全ての元を含む F∗p2 の部分群とする．曲線 E/Fp2 上の Weil Pairing とは楕
円曲線の因子と有理関数を用いて定義されるある写像
e : E[q] × E[q] → µq である．ここで Weil Pairing e を使って前述の条件を満たす写像 ê : Gq × Gq → µq を次のように定義することができる．

双線形 Diﬃe-Hellman 仮定

G1 , G2 を大きな素数 q を位数とする巡回群とし，G1 は加法的に，G2 は乗法的に表現する．また，ê :G1 × G1 → G2 という多項式時間で計算可能な非退化な双線形写像 ê が定義されているとする．すなわち，ê(aP, bQ) = ê(P, Q)ab ，更に非退化の仮定を強めて，P が G1 の生成元であるとき，ê(P, P ) は G2 の生成元になると仮定する．この写像を用いて，双線形 DiﬃeHellman 仮定が以下のように定義できる．
BDH 仮定: P を G1 の生成元とする．BDH 問題とは，
hP, aP, bP, cP i に対して ê(P, P )abc ∈ G2 を求める問題である．BDH 問題を多項式時間で解けるアルゴリズムが存在しないということを，BDH 仮定と呼ぶ．

ê(P, Q) = e(P, φ(Q))

3

写像 ê は次の性質を満たす：
1. 双線形：全ての P, Q ∈ Gq と全ての a, b ∈ Z に対して ê(aP, bQ) = ê(P, Q)ab となる．
2. 非退化：∀P 6= O に対して ê(P, P ) ∈ Fp2 は位数 qの元であり，µq の生成元である．
3. 計算可能：P, Q ∈ Gq が与えられたとき，ê(P, Q) を計算する確率的多項式時間のアルゴリズムが存在する．

ID ベース暗号の仕組み

BDH 仮 定 が 成 り 立 つ と い う 前 提 の 下 で ，ID
ベース暗号は次の４つの確率的アルゴリズム(Setup,Extract,Encrypt,Decrypt) の組で作れる．
Setup: セキュリティパラメータ k を選び，システムパラメータ params とマスターキー s を返す．(マスターキーは PKG だけが知っているものである．)
Extract: params とマスターキー s を入力すると，任意の文字列 ID ∈ {0, 1}∗ に対応する秘密鍵 d を生成する．

5.2

MapToPoint

この暗号システムは任意の文字列 ID ∈ {0, 1}∗ を位数 q の点 QID ∈ E/Fp へ写すためのハッシュ関数に依存した単純なアルゴリズムを使う．このアルゴリズムを MapToPoint と呼ぶ．

27

5.3

ここで，藤崎-岡本のテクニックとは次のようなものである．公開鍵 pk のもとで，ランダムビット r を使って平文 M を暗号化したものを εpk (M ; r) と表すとする．次で定義される εhy は，ε が一方向性を満たすとき，選択暗号文攻撃に対して強秘匿となる，というものである．ここで，σ はランダムに生成されたもので，H1 , G1 はハッシュ関数である．

BasicIdent

まず簡単のため，選択 ID 攻撃付き暗号文単独攻撃に対して一方向性を満たす簡単なシステムについて記述する．これを BasicIdent と呼ぶ．このシステムは４つのアルゴリズム Setup, Extract, Encrypt, Decryptから成る．
Setup:
Step 1: ある素数 q > 3 に対して p = 2 mod 3 と
p = 6q − 1 を満たす大きい k bit の素数 p を選ぶ．Eを y 2 = x3 + 1 で定義される Fp 上の楕円曲線とする．
位数 q の任意の点 P ∈ E/Fp を選ぶ．
Step 2: ランダムに s ∈ Z∗q を選び，Ppub = sP とおく．
Step 3: ハッシュ関数 H : Fp2 → {0, 1}n を選ぶ．ハッシュ関数 G : {0, 1}∗ −→ Fp を選ぶ．安全性解析では
H と G をランダムオラクルとして見る．
平文空間は M = {0, 1}n , 暗号文空間は C =E/Fp × {0, 1}n , システムパラメータは prams =hp, n, P, Ppub , G, Hi , マスターキーは s ∈ Zq となる．
Extract: 与えられた ID ∈ {0, 1}∗ に対して，このアルゴリズムは秘密鍵 d を次のようにして作る．
Step 1: MapToPointG を使って ID を位数 q の点QID ∈ E/Fp に移す．
Step 2: 秘密鍵 dID を dID = sQID とおく．ここで s はマスターキーである．
Encrypt: 公開鍵 ID のもとで次のように M ∈ M を暗号化する．
(1)MapToPointG を用いて ID を位数 q の点 QID ∈E/Fp に写す．
(2)r ∈ Zq をランダムに選ぶ．
(3) 暗号文を次のようにおく．

εhypk (M ) = εpk (σ; H1 (σ, M )) || G1 (σ) ⊕ M
BasicIdent にこのテクニックを適用すると，システムは次のようになる．
Setup: BasicIdent の手続きに加え，ハッシュ関数 H1 :{0, 1}n × {0, 1}n → Fq とハッシュ関数 G1 : {0, 1}n →{0, 1}n を選ぶ．
Extract: BasicIdent と同じようにする．
Encrypt: 公開鍵 ID を用い，平文 M ∈ {0, 1}n を暗号化する．
1. MapToPointG を使って ID を位数 q の点 QID ∈ E/Fpに写す．
2. σ ∈ {0, 1}n をランダムに選ぶ．
3. r = H1 (σ, M ) とおく．
4. 暗号文を次のようにおくr
C = hrP, σ ⊕ H(gID), G1 (σ) ⊕ M i

ここで，gID = ê(QID , Ppub ) ∈ Fp2 , r = H1 (σ, M )．
Decrypt: C = hU, V, W i を公開鍵 ID を使って暗号化した暗号文とする．秘密鍵 dID を使って C を復号するために次のようにする．
1. V ⊕ H(ê(dID , U )) = σ を計算する．
2. W ⊕ G1 (σ) = M を計算する．
3. r = H1 (σ, M ) とおく．U = rP となるか試し，もし違ったら暗号文を拒絶する．
4. M を C の復号として出力する．

r
C = hrP, M ⊕ H(gID)i

ここに，gID = ê(QID , Ppub ) ∈ Fp2
Decrypt: C = hU, V i ∈ C を公開鍵 ID を使って作成した暗号文とする．もし U ∈ E/Fp が位数 q の点でなかったら，その暗号文を拒絶する．そうでなければ，秘密鍵 dID を使って次の計算により，C を復号する．

6Weil Pairing を使った ID ベース暗号の仕組と安全性などを紹介し，C 言語による実装を行った．今後は最近活発に研究されている ID ベース暗号の具体的な応用について，新たな試みを行いたい．また，新しい効率的なペアリングの探求も行いたい．

V ⊕ H(ê(dID , U )) = M
まず始めに健全性を証明する．全てが上のように計算できたとき，次のようになっている．
1. 暗号化の際，M は gID のハッシュと XOR される．
2. 復号の際，V は ê(dID , U ) のハッシュと XOR される．

参考文献
[1] Dan Boneh, Matt Franklin, Identity-Based Encryption from the Weil Pairing, Springer-Verlag,
pp.213-229, 2001.
[2] E. Fujisaki and T. Okamoto, “Secure integration of asymmetric and symmetric encryption
scheme”, Springer-Verlag, pp.537-554, 1999.
[3] L. C. Washington, Elliptic Curves, Number Theory and Cryptography, CHAPMAN&HALL/CRC.
[4] Yasuyuki MURAKAMI, Ryuichi SAKAI, Masao
KASAHARA, A New Probabilistic ID-Based
Non-interactive Key Sharing Scheme, IEICE
Transaction Vol.E83-A No.1 pp.2-9, 2000.
[5] I.F.Blake, G.Seroussi, N.P.Smart, Elliptic Curves
in Cryptography, Cambridge Univ Pr.

ê(dID , U ) = ê(sQID , rP ) = ê(QID , P )srr= ê(QID , sP )r = ê(QID , Ppub )r = gID

したがって，暗号文に Decrypt を適用すると，もとの平文を復元できる．
BasicIdent は BDH 仮定が成り立つ限り，選択 ID 攻撃付き暗号文単独攻撃に対して一方向性を持つことが，BDH 仮定とランダムオラクルモデルの下で証明できる．

5.4

まとめと今後の課題

選択暗号文攻撃に対して安全な ID ベース暗号

BasicIdent に藤崎-岡本 [2] のテクニックを適用して選択暗号文攻撃に対しても強秘匿性を持つ暗号システ
ムを作る．
28