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 2008 does not prevent future
submissions to any journals or conferences with proceedings.

SCIS 2008
The 2008 Symposium on
Cryptography and Information Security
Miyazaki, Japan, Jan. 22-25, 2008
The Institute of Electronics,
Information and Communication Engineers

任意の頑強な ID ベース暗号に基づく CCA 安全な公開鍵暗号の効率的構成方法
Simple CCA-Secure Public Key Encryption from Any Non-Malleable
ID-based Encryption
松田 隆宏 ∗
Takahiro Matsuda

花岡 悟一郎 †Goichiro Hanaoka

松浦 幹太 ∗
Kanta Matsuura

今井 秀樹 †
Hideki Imai

あらまし 本稿では、頑強性を持つ ID ベース暗号から CCA 安全性を持つ公開鍵暗号の構成法を示す。
2005 年に提案された Boneh と Katz による方法 (BK 変換) では、構成要素として MAC と特殊なコミッ
トメント方式が必要であり、暗号文サイズの変換によるオーバーヘッドが 704 ビット程度生じてしまう。
これに対し本稿で提案する方法では、ID ベース暗号に従来の変換で用いられる識別不可能性よりも強い
頑強性を仮定することで、構成要素は、一方向性及びターゲット衝突困難性を同時に満たす一つのハッシュ関数のみとでき、暗号文サイズのオーバーヘッドは 256 ビット程度である。これまで、安全性の帰着をある種の暗号方式の頑強性に帰着させるような方式はあまり提案されていないが、本稿での証明は、新しい証明技法として、他の暗号技術の安全性をある種の暗号方式の頑強性へと帰着する必要がある場
合に有用な可能性がある。
キーワード 公開鍵暗号、ID ベース暗号、IND-CCA 安全性、頑強性、NM-sID-CPA 安全性

1(128 ビット安全性を得るためにおよそ 704 ビット)。IBEの構成に対し一般性を犠牲にすることで、さらなる効率性を目指した研究もある [5, 1, 9]。以上の研究において共通していることは、IBE に選択平文攻撃に対する識別不可能性 (IND-(s)ID-CPA) を仮定している点である。

はじめに効率的な選択暗号文攻撃 (CCA) に対する安全性を持
つ公開鍵暗号方式 (Public Key Encryption, PKE) の構
成法についての研究は、暗号研究の分野の一つの主流となっている。その中で一つのパラダイムとして、選択平
文攻撃 (CPA) に対する安全性しか持たない様な ID ベース暗号 (Identity-based Encryption, IBE) から CCA 安
全性を持つ PKE を構成しようとする IBE-PKE 変換の研究が近年盛んである。

IBE の頑強性 暗号方式での頑強性 (Non-Malleability,NM) とは、概略を言えば、暗号文 χ を与えられた攻撃者
が、その平文 m とある関係 R を満たすことが分かる平文
m0 に復号できてしまう様な暗号文 χ0 を作りだすことができないという安全性の概念である。IBE において、選択平文攻撃に対する頑強性 (NM-(s)ID-CPA) と識別不可
能性 (IND-(s)ID-CPA) の間には差があると考えられているが、選択暗号文攻撃に対する頑強性 (NM-(s)-ID-CCA)
は、同攻撃に対する識別不可能性 (IND-(s)ID-CCA) と等価であることが示されている [2]。

IBE-PKE 変換 2004 年に Canetti ら [6] により、CPA
安全な任意の IBE を用いた PKE への一般的構成方法が提案された (CHK 変換)。この構成法は One-Time 署名を用いるものであり、暗号文サイズ及び暗号文作成の際の計算コストのオーバーヘッドが大きい。その後、OneTime 署名のオーバーヘッドを改善するため、2005 年にBoneh ら [4] は MAC と特殊なコミットメント方式 (実体はターゲット衝突困難ハッシュ関数及び汎用ハッシュ関
数 (Universal Hash Function)) を用いた構成法を提案した (BK 変換)。しかし、Leftover Hash Lemma [8] を用いるため、大きなサイズの乱数を用いる必要があり、暗号文作成の計算コストのオーバーヘッドは改善されるものの、依然として暗号文サイズのオーバーヘッドは大きい

本研究の成果 本稿では、識別不可能性よりも強い安全性である頑強性を持つ任意の IBE から一般的に CCA 安
全な PKE を構成する方法を提案する。より具体的には、
IBE において、頑強性を持つものの中で最も弱い安全性
である選択的 ID 及び選択平文攻撃に対する頑強性 (NMsID-CPA) を持つ IBE と、一方向性及びターゲット衝突
困難性を同時に満たすハッシュ関数一つを用いて、CCA
安全な PKE の効率的な構成法を示し、その安全性証明を示す。残念なことに、これまで、IND-sID-CCA 以上の安全性を持っていると証明されている方式を除けば、
NM-sID-CPA 安全性を持つ実用的な IBE の構成法は知られていない。しかしながら今後、NM-sID-CPA 安全性を持つと示される (あるいは仮定できる) ような効率∗

東京大学 生産技術研究所, 〒 153-8505 東京都目黒区駒場 4-61, Institute of Industrial Science, The University of Tokyo,
4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan. Email:tmatsuda@iis.u-tokyo.ac.jp† 産業技術総合研究所 情報セキュリティ研究センター, 〒 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

Phase 2. A は Phase 1 と同様 q2 回の復号クエリを発行することができる。ただし、Challenge の際受け取った暗号文 χ∗ を復号クエリとすることはできない。

的な IBE あれば、我々の構成法によりただちに効率的なCCA 安全性を持つ PKE を得ることができる。
また、現在まで、ある方式の安全性をある種の暗号の頑強性に帰着する証明は、PKE 間及び IBE 間などの安全性の定義間の関係性の議論などの研究 ([3]、[2] など)
を除いては行われていない。実際の証明の構成についても、攻撃者の振舞いやシミュレータ自身のランダムコイ
ンによって、シミュレータの対応が多様に変化しており、CHK 変換や、BK 変換の安全性証明とは非常に異なった
新しいものとなっている。そのため、安全性を IBE の頑強性に帰着できるような方式を証明と共に示したことも本研究の理論的な成果である。今後、暗号技術の安全性を、ある種の暗号方式の頑強性に帰着する場合は、本稿での安全性の証明技法が有用である可能性がある。

2

Guess. A は C の選んだ b の予測として b0 を出力する。
qD = q1 + q2 を A が発行することができる復号クエリの回数とする。ここで、ある公開鍵暗号 Π における Aの IND-CCA アドバンテージを以下の様に定義する。
AdvIND-CCA= | Pr[b0 = b] − 1/2|
Π,A
定義 1. 復号クエリを最大 qD 回発行する全ての動作時
間 t のアルゴリズム A に対し、AdvIND-CCA≤ ² を満たΠ,Aすとき、Π は (t,qD ,²)-IND-CCA 安全であるという。また、² が無視できる値のとき、単に Π は IND-CCA 安全
であるという。

準備

本節では、本稿で使用する言葉や安全性の定義を行う。
本稿では、x ← y と書くとき、y が集合ならばそこから一様ランダムに要素を取り出し x に代入する操作を、yがアルゴリズムまたは関数ならば x を出力する操作を表す。“x||y” は x と y の連結を表す。

2.1

2.2

ID ベース暗号

ID ベース暗号 Π は以下の 4 つのアルゴリズムからなる。
セットアップ IBE.Setup: 確率的アルゴリズム。セキュ
リティパラメータ 1κ を入力とし、マスター秘密鍵
msk と公開パラメータ prm の対を出力する。

公開鍵暗号

公開鍵暗号 Π は以下の 3 つのアルゴリズムからなる。

鍵導出 IBE.Ext: 確率的あるいは決定的アルゴリズム。公開パラメータ prm、マスター秘密鍵 msk、ID ∈ I
を入力とし、ID に対する復号鍵 dID を出力する。

鍵生成 PKE.KG: 確率的アルゴリズム。セキュリティパ
ラメータ 1κ を入力とし、秘密鍵 sk と公開鍵 pk の対を出力する。
暗号化 PKE.Enc: 確率的アルゴリズム。公開鍵 pk 、平文 m ∈ M を入力とし、暗号文 χ ∈ X を出力する。

暗号化 IBE.Enc: 確率的アルゴリズム。公開パラメータ
prm、ID ∈ I 、平文 m ∈ M を入力とし、暗号文
χ ∈ X を出力する。

復号 PKE.Dec: 決定的アルゴリズム。秘密鍵 sk 、暗号文
χ を入力とし、平文 m (あるいは ⊥) を出力する。

復号 IBE.Dec: 決定的アルゴリズム。復号鍵 dID 、暗号文
χ を入力とし、平文 m (あるいは ⊥) を出力する。

ただし、M、X はそれぞれ、Π の平文空間、暗号文空間である。

ただし、I 、M、X はそれぞれ、Π の ID 空間、平文空
間、暗号文空間である。

IND-CCA 安全性 公開鍵暗号の適応的選択暗号文攻撃に対する識別不可能性 (Indistinguishability against
Adaptive Chosen-Ciphertext Attacks, IND-CCA) は、以下の攻撃者 A と IND-CCA Challenger C 間の INDCCA game を用いて定義される。

NM-sID-CPA 安全性 本稿で用いる IBE の NM-sIDCPA 安全性の定義は、Attrapadung ら [2] による。ID
ベース暗号の選択的 ID 及び選択平文攻撃に対する頑強性(Non-Malleability against selective-ID Chosen-Plaintext
Attacks, NM-sID-CPA) は、以下の攻撃者 A と NM-sIDCPA Challenger C 間の NM-sID-CPA game を用いて定義される。

Setup. C は PKE.KG(1κ ) を実行する。出力された pk をA に渡し、sk を保持しておく。

Init. A は初めに攻撃対象とする ID∗ を宣言する。

Phase 1. A は Challenger に対し、q1 回の復号クエリ(χ1 , χ2 , . . . , χq1 ) を発行することができる。C はそれぞれのクエリ χi に対し、正しい復号結果 mi ←PKE.Dec(sk, χi ) (mi ∈ M ∪ {⊥}) を返す。

Setup. C は IBE.Setup(1κ ) を実行する。出力された prm
を A に渡し、msk を保持しておく。
Phase 1. A は C に対し、q1 回の鍵導出クエリ(ID1 , ID2 , . . . , IDq1 ) を発行することができる。C はそれぞれのクエリ IDi に対し、正しい復号鍵 dIDi ←IBE.Ext(prm, msk, IDi ) を返す。ただし、A は ID∗を鍵導出クエリとすることはできない。

Challenge. A は 2 つの任意の平文 m0 , m1 を選び、Cに送る。C はランダムにコイン b ∈ {0, 1} を振り、mb の暗号文 χ∗ ← PKE.Enc(pk, mb ) を計算し、χ∗を A に渡す。

2

Challenge. A は M∗ ⊂ M となるような M∗ を選び、C に送る。C は M∗ から一様ランダムに、m∗ 及
び m∗¯ を選ぶ。χ∗ ← IBE.Enc(prm, ID∗ , m∗ ) を計算し、A に渡す。

定義 4. 全ての動作時間 t のアルゴリズム A に対し、
AdvTCRH,A ≤ ² を満たすとき、H は (t,²)-TCRHF であるという。また、² が無視できる値のとき、H を単に TCRHF
であるという。

Phase 2. A は Phase 1 と同様 q2 回の復号クエリを発行することができる。

3

本節では、我々の提案方式及びその安全性について議論する。
Π = (IBE.Setup, IBE.Ext, IBE.Enc, IBE.Dec) を NMsID-CPA 安全な ID ベース暗号とする。また、H : K ×{0, 1}γ → I (定義域のうち K がハッシュ鍵空間、{0, 1}γが H の入力空間) をターゲット衝突困難性かつ一方向性を持つハッシュ関数とする。このとき公開鍵暗号方式 Π0 を図 1 の様に構成する。Π0 の平文空間を MΠ0 とすると、内部の ID ベース暗号 Π の平文空間は MΠ はMΠ0 × {0, 1}γ となっている必要がある。

Output. A は C の選んだ m∗ とある関係 R を満たすよ→うな平文ベクトル −m 0 = (m01 , m02 , . . . , m0t ) の暗号−→
0文ベクトル χ = (χ01 , χ02 , . . . , χ0t )(χ0i ← IBE.Enc(prm, ID∗ , m0i )i∈{1,...,t} ) とその関係−→
R の具体的記述を C に出力する1 。C は χ0 を全て
IBE.Dec(dID∗ , ·) (dID∗ ← IBE.Ext(prm, msk, ID∗ ))→を用いて復号し、−
m 0 を得る。
qE = q1 + q2 を A が発行することができる鍵導出ク→→→
エリの回数とする。R(m, −χ 0 ) を χ∗ ∈/ −
χ0 ∧ ⊥ ∈/ −m0 ∧→R(m, −m 0 ) = true が起こるイベントと定義する。R∗ :=→∗ −R(m , →
χ 0 )、R∗¯ := R(m∗¯ , −χ 0 ) と定義する。ここで、ある ID ベース暗号 Π における A の NM-sID-CPA アドバ
ンテージを以下の様に定義する。
AdvNM-sID-CPA= Pr[R∗ ] − Pr[R∗¯ ]
Π,A

3.1

証明 A を、公開鍵暗号方式 Π0 の (t, qD , ²cca ) -INDCCA 安全性を破る攻撃者とする。すなわち、A は確率
1/2 + ²cca で Π0 を破るとする。このとき A と、(t, ²tcr )TCRHF かつ (t, ²ow )-OWHF である H を用いて ID ベース暗号方式 Π の (t, qD , 2q1D (1 − ²tcr )²cca − 41 (²ow + 21γ ))-NM-sID-CPA 安全性を破ることができるシミュレータ
S を構成する。一般性を失わずに、qD > 0 とする。S は
A に対して以下の様に IND-CCA game のシミュレートを行いつつ利用して自身の NM-sID-CPA Challenger Cとの間で NM-sID-CPA game を行う。

ハッシュ関数H : K × Min → Mout を鍵付きハッシュ関数とする。
ただし、Min 、Mout 、K をそれぞれ、H の入力空間、
出力空間、ハッシュ鍵空間とする。
2.3.1

安全性

定理 1. 構成要素である Π が (t, qD , 2q1D (1 − ²tcr )²cca −1
1
4 (²ow + 2γ )) -NM-sID-CPA 安全な ID ベース暗号方式、
H が (t, ²ow )-OWHF かつ (t, ²tcr )-TCRHF のとき、提案
方式 Π0 は (t, qD , ²cca )-IND-CCA 安全な公開鍵暗号方式である。

定義 2. 鍵導出クエリを最大 qE 回発行する全ての動作
時間 t のアルゴリズム A に対し、AdvNM-sID-CPA≤²をΠ,A満たすとき、Π は (t,qE ,²)-NM-sID-CPA 安全であるという。また、² が無視できる値のとき、単に Π は NMsID-CPA 安全であるという。

2.3

提案方式

一方向ハッシュ関数

攻撃者 A の一方向ハッシュ関数 (One-Way Hash Function, OWHF) H に対するアドバンテージを以下の様に
定義する。
AdvOW
H,A = Pr[k ← K; m ← Min ; h ← Hk (m);m0 ← A(k, h) : Hk (m0 ) = h]

Setup. S は k ∈ K 及び r∗ ∈ {0, 1}γ をそれぞれ一様ランダムに選び、ID∗ ← Hk (r∗ ) を計算する。ID∗ を自身の NM-sID-CPA game での攻撃対象 ID として宣言し、C から prm を受け取る。S は P K = (prm, k)
を A に渡す。

定義 3. 全ての動作時間 t のアルゴリズム A に対し、AdvOW
H,A ≤ ² を満たすとき、H は (t,²)-OWHF であるという。また、² が無視できる値のとき、H を単に OWHF
であるという。

Phase 1. S は A の発行する復号クエリ
χi = hIDi , yi ii∈{1,...,q1 } に対し、IDi の値により以下の様に mi を作成し応答する。
• IDi = ID∗ のとき: mi = ⊥ を返す。
• それ以外のとき: IDi を鍵導出クエリとして C に問い合わせ、dIDi を受け取る。IBE.Dec(dIDi , yi ) を計算しこの結果が ⊥ ならば mi = ⊥ を返し、そうでなければ復号結果 mi ||ri の mi を返す。

2.3.2

ターゲット衝突困難ハッシュ関数

本稿で用いる TCRHF の定義は Cramer ら [7] による。
攻撃者 A のターゲット衝突困難ハッシュ関数 (Target
Collision Resistant Hash Function, TCRHF) H に対す
るアドバンテージを以下の様に定義する。
AdvTCR
H,A = Pr[k ← K; m1 ← Min ; m2 ← A(k, m1 ) :Hk (m1 ) = Hk (m2 ) ∧ m1 6= m2 ]Challenge. A が (m0 , m1 ) を出力したとき、S は以下の様にしてチャレンジ暗号文 χ∗ を作成して応答する。コイン bS ∈ {0, 1} を振る。m0 ∈ MΠ0 (mbSと長さの等しい乱数) と r0 ∈ {0, 1}γ をそれぞれ一様ランダムに選ぶ。MbS = mbS ||r∗ , M1−bS =m0 ||r0 ∈ MΠ とする。M∗Π = (M0 , M1 ) を自身の1 t は κ に関し多項式倍程度の大きさの自然数であり、A によって決められる。t = 1 の場合も考えることができる。その場合、R は二項関係となる。本稿では 3 節以降、R が二項関係の場合のみを取り扱っているが、ここでは一般的に記述するためにこのように記す。

3

PKE.KG(1κ ) :(prm, msk) ← IBE.Setup(1κ )k←K
SK = msk, P K = (prm, k)
Output (SK, P K).

PKE.Enc(P K, m) :r ← {0, 1}γ ; ID ← Hk (r)y ← IBE.Enc(prm, ID, m||r)χ = hID, yi
Output χ.

PKE.Dec(SK, χ) :Parse χ as hID, yi; dID ← IBE.Ext(prm, msk, ID)
m||r ← IBE.Dec(dID , y)
(If this decrypts to ⊥ then output ⊥ and stop.)
Output m if Hk (r) = ID. Otherwise output ⊥.

図 1: 提案する公開鍵暗号方式 Π0

Challenge として C に対し出力し、y ∗ を受け取る。
χ∗ = hID∗ , y ∗ i を A に渡す。

Case 6: bA 6= bS ∧ bS 6= bC
これら Case は、全ての場合を網羅している。°
i を Case
i が起こるイベントと定義する。Case i における S のア
ドバンテージ Advi を以下の様に定義する。
Advi := Pr[R∗ ∧ °i ] − Pr[R∗¯ ∧ °i]= Pr[°i ] · (Pr[R∗ |°i ] − Pr[R∗¯ |°i ])NM-sID-CPA アドバンテージの定義により、
P6
AdvNM-sID-CPA= i=1 Advi
Π,Sは明らかである。以下、各場合のアドバンテージを見積もっていく。

Phase 2. Phase 1 と同様の処理を行う。
Guess. A が bA を出力する。R :=“下位 γ ビットが等しい” という 2 項関係とする。bA の値により S は
y 0 を以下の様に作成する。
• bA = bS のとき: m00 ∈ MΠ0 (mbS と長さの等しい乱数) と r00 ∈ {0, 1}γ をそれぞれ一様ランダムに選ぶ。バイアスがかかったコインを振り、確率 α
で y 0 ← IBE.Enc(prm, ID∗ , m00 ||r∗ )、確率 (1 − α)で y 0 ← IBE.Enc(prm, ID∗ , m00 ||r00 ) とする。
• それ以外のとき: A の復号クエリ
χj = hIDj , yj ij∈{1,...,qD } の中からランダムに一つの yj を選び、y 0 とする。

Case 1 : bA = bS ∧ bS = bC ∧ Valid
この場合、M ∗ = mbS ||r∗ 、M ∗¯ = m0 ||r0 となっている。
bA = bS ということは、A が guess に成功し、S にとってのチャレンジ暗号文 y ∗ の平文 mbS ||r∗ を当てるということである。この状況下で A の出力 bA を信用する場合
は、S は自身のチャレンジ暗号文の平文を知ることになる。従って確率 α で S は M ∗ = mbS ||r∗ と下位 γ ビットが等しい平文の暗号文 y 0 を出力できる。また、A の出力を信用しない場合はランダムな平文 m00 ||r00 の暗号文を出力するが、この平文の下位 γ ビット r00 と r∗ が等しくなる確率は (1 − α) · 1/2γ (以下簡単のため、1/2γ = Pγ
とおく)。従って、
Pr[R∗ |°
1 ] = α + (1 − α) · Pγ0
また、r と r∗ 及び r0 と r00 は独立に選ばれているため、y ∗ の平文として選ばれなかった平文 m0 ||r0 の下位 γ ビットと S の出力する暗号文 y 0 の平文の同部分が等しくなる確率は下記の様に評価できる。
Pr[R∗¯ |°1 ] = Pγ
次に、Pr[°
1 ] を評価する。
Pr[°
1 ] = Pr[bA = bS ∧ bS = bC ∧ Valid]= Pr[bA = bS |bS = bC ∧Valid]·Pr[Valid|bS = bC ]· Pr[bS = bC ]ここで、以下が成り立つ。
Pr[bA = bS |bS = bC ∧ Valid] = 1/2 + ²cca
なぜならば、S にとってのチャレンジ暗号文 y ∗ は ID∗ を用いた mbS ||r∗ の暗号であり、A に対する Challenge のシミュレーションは完全であり、Valid も起こらず復号クエリに対するシミュレーションも完全なため、A の View は実際に Π0 を攻撃しているときと同一になるからである。従って A は通常の成功確率で動作する。Pr[Valid|bS = bC ] は
この時点では (1 − Pv ) とおく (すなわち、Pr[Valid|bS =bC ] = Pv )。また、Pr[bS = bC ] = 1/2。以上により、Case 1 の S のアドバンテージは、
Adv1 = Pr[°
1 ] · (Pr[R∗ |°1 ] − Pr[R∗¯ |°1 ])= (1/2+²cca )·(1−Pv )·1/2·(α+(1−α)·Pγ −Pγ )= 1/2 · α · (1/2 + ²cca ) · (1 − Pv ) · (1 − Pγ )S は C に対し (R, y 0 ) を出力する。
以上が S の構成である。確率 α については今は未知数としておき、後で議論する。次に、S の NM-sID-CPAを計算する。
アドバンテージ AdvNM-sID-CPA
Π,S
我々の S の構成法では、NM-sID-CPA の Challenge として C に送る M∗Π は必ず 2 つの平文からなる。NM-sIDCPA game の定義により、M∗Π からチャレンジとして選ばれる M ∗ は、S の作る M0 か M1 のどちらかでありその確率は等しく 1/2 の確率であるため、便宜上 NM-sIDCPA Challenger も自身のコイン bC ∈ {0, 1} を振って、MbC をチャレンジのための平文 M ∗ として決定していると考えることにする。bC は S のコイン bS とは完全に独立に選ばれるため、Pr[bS = bC ] = Pr[bS 6= bC ] = 1/2 である。bS 6= bC が起こる場合、S の A に対する Challengeのシミュレーションが完全ではなくなる。
暗号文 χ が提案方式 Π0 の復号手順を実行すると ⊥ を返さず正しく復号される場合、χ を “正当” であると呼ぶ。Valid を A が χ = hID∗ , yi という形でかつ正当な暗号文を復号クエリとして一回以上発行するイベントと定義する。Valid が起こる場合、A の復号クエリに対する
S の応答のシミュレーションが完全ではなくなる。
bS と bC が一致するかどうか及び Valid が起こっているかどうかを S は知ることができない。
以下、bA 、bS 、bC 、及び Valid について、6 通りの場合を考える。
Case 1: bA = bS ∧ bS = bC ∧ Valid
Case 2: bA = bS ∧ bS = bC ∧ Valid
Case 3: bA = bS ∧ bS 6= bC
Case 4: bA 6= bS ∧ bS = bC ∧ Valid
Case 5: bA 6= bS ∧ bS = bC ∧ Valid4

Case 2 : bA = bS ∧ bS = bC ∧ Valid
この場合も Case 1 と同様に M ∗ = mbS ||r∗ 、M ∗¯ = m0 ||r0となっているため以下の評価ができる。
Pr[R∗ |°
2 ] = α + (1 − α) · Pγ
Pr[R∗¯ |°2 ] = Pγ
次に Pr[°
2 ] を評価する。
Pr[°
2 ] = Pr[bA = bS ∧ bS = bC ∧ Valid]= Pr[bA = bS |bS = bC ∧Valid]·Pr[Valid|bS = bC ]· Pr[bS = bC ]Case 1 で定義した様に、Pr[Valid|bS = bC ] = Pv 。Pr[bA =bS |bS = bC ∧ Valid] は、A にとっての復号クエリに対す
るシミュレーションが Valid によって完全でなくなったにも関わらず A が S のアドバンテージを伸ばすような行動をする確率である。ここではこれを Pk とおいて未知のままにしておく。また、Pr[bS = bC ] = 1/2。
以上より、Case 2 の S のアドバンテージは、
2 ] − Pr[R∗¯ |°2 ])Adv2 = Pr[°
2 ] · (Pr[R∗ |°= 1/2 · Pk · Pv · α · (1 − Pγ )· Pr[Valid|bS = BC ] · Pr[bS = bC ]= (1 − (1/2 + ²cca )) · (1 − Pv ) · 1/2= 1/2 · (1/2 − ²cca ) · (1 − Pv )ただし Pr[bA = bS |bS = bC ∧ Valid] = 1/2 + ²cca 、Pr[Valid|bS = bC ] = Pv 、Pr[bS = bC ] = 1/2 を用いた。
以上により、Case 4 の S のアドバンテージは、
Adv4 = Pr[°
4 ] · (Pr[R∗ |°4 ] − Pr[R∗¯ |°4 ])≥ −1/2 · (1/2 − ²cca ) · (1 − Pv ) · Pγ
Case 5 : bA 6= bS ∧ bS = bC ∧ Valid
この場合、M ∗ および M ∗¯ は Case 1 と同様である。Validが起こり復号クエリの応答のシミュレーションが完全でなくなるため、A は S に対してどのようにも振舞うことができる。しかし Valid が起こるとき、A は少なくとも一つ、Hk (rA ) = ID∗ となるような平文 MA = mA ||rAの暗号文 yA が含まれるような復号クエリ hID∗ , yA i を発行している。bA 6= bS のため、S は A が発行した一
つの復号クエリを qD 個の中から選んで y 0 として出力する。Pr[R∗ |°5 ] は、S が、qD 個の復号クエリの中から
Hk (rA ) = ID∗ となるような平文 MA = mA ||rA の暗号
文 yA を選び、なおかつその平文 mA ||rA が rA = r∗ を満たす確率である。
Pr[R∗ |°
5 ] ≥ 1/qD · Pr[rA = r∗ |°5]= 1/qD · (1 − Pr[rA 6= r∗ |°5 ])ここで、[rA 6= r∗ |°5 ] というイベントを考えると、Case
5 の場合 S のシミュレーション中に A に与えられる r∗の情報は IBE.Enc(prm, Hk (r∗ ), mbS ||r∗ ) という暗号文と
Hk (r∗ )(= ID∗ ) であり、r∗ と k はいずれも S により前
もってそれぞれ一様ランダムに選ばれている。この状況
で A が rA 6= r∗ ∧ Hk (rA ) = Hk (r∗ ) = ID∗ となる rA を平文に持つような復号クエリを送っている確率は、ランダムに選んだ r∗ そのものを与えられ、ランダムに選ばれたハッシュ鍵 k のもと rA 6= r∗ ∧Hk (rA ) = Hk (r∗ ) = ID∗となる rA を見つける確率か、それよりも小さくなり、その確率は H のターゲット衝突困難性により、高々²tcr となる。従って、Pr[R∗ |°
5 ] ≥ 1/qD · (1 − ²tcr )また、Case 4 の場合と同様の議論により、
Pr[R∗¯ |°5 ] ≤ Pγ
Pr[°5 ] は以下の様に計算される。
Pr[°5 ] = Pr[bA 6= bS ∧ bS = bC ∧ Valid]= (1 − Pr[bA = bS |bS = bC ∧ Valid])· Pr[Valid|bS = bC ] · Pr[bS = bC ]= (1 − Pk ) · Pv · 1/2
ただし、Pr[bA = bS |bS = bC ∧Valid] = Pk 、Pr[Valid|bS =bC ] = Pv 、Pr[bS = bC ] = 1/2 を用いた。
以上により、Case 5 の S のアドバンテージは、
Adv5 = Pr[°
5 ] · (Pr[R∗ |°5 ] − Pr[R∗¯ |°
5 ])≥ (1 − Pk ) · Pv · 1/2 · {1/qD · (1 − ²tcr ) − Pγ }Case 3 : bA = bS ∧ bS 6= bC
この場合、M ∗ = m0 ||r0 、M ∗¯ = mbS ||r∗ となっており、Pr[R∗ |°
3 ] と Pr[R∗¯ |°3 ] の評価は Case 1 の場合と入れ替わる。すなわち、以下の様になる。
Pr[R∗ |°
3 ] = Pγ
Pr[R∗¯ |°3 ] = α + (1 − α) · Pγ
また、Pr[°
3 ] については、以下の様になる。
Pr[°3 ] = Pr[bA = bS ∧ bS 6= bC ]= Pr[bA = bS |bS 6= bC ] · Pr[bS 6= bC ]bS 6= bC の場合、A に与えられるチャレンジ暗号文 χ∗
は A の選んだ平文 m0 、m1 のどちらの暗号文でもない
ため、A にとっての Challenge のシミュレーションは完
全ではない。そのため、A は S に対してどのようにも振舞えるが、Case 3 の場合 bS は A に対して完全に隠されているため、bA と bS が等しくなる確率は情報理論的に 1/2 である。従って、Pr[bA = bS |bS 6= bC ] = 1/2。また、Pr[bS 6= bC ] = 1/2。
以上により、Case 3 の S のアドバンテージは、
Adv3 = Pr[°
3 ] · (Pr[R∗ |°3 ] − Pr[R∗¯ |°3 ])= 1/2 · 1/2 · {Pγ − α − (1 − α) · Pγ }= −1/4 · α · (1 − Pγ )Case 4 : bA 6= bS ∧ bS = bC ∧ Valid
この場合、M ∗ および M ∗¯ は Case 1 と同様である。bA 6=
bS のため、S は y 0 を、A の発行した復号クエリから一つ選ぶことになる。Valid が起こっていないため、A の復号クエリの中には、一つも r∗ と等しくなるような下位 γ ビットを持つものが存在しない。従って、
Pr[R∗ |°4]=0
また、この場合の A は M ∗¯ = m0 ||r0 に関する情報を何も得ることができない。よって A が R(M ∗¯ , yi ) の起こる
yi を含む暗号文を復号クエリとして発行している確率は
高々Pγ である。
Pr[R∗¯ |°4 ] ≤ Pγ
Pr[°4 ] は以下の様に計算できる。
Pr[°4 ] = Pr[bA 6= bS ∧ bS = bC ∧ Valid]= Pr[bA 6= bS |bS = bC ∧ Valid]

Case 6 : bA 6= bS ∧ bS 6= bC
この場合、M ∗ および M ∗¯ は Case 3 と同様である。Pr[R∗ |°6]については
Pr[R∗ |°
6]≥0と評価する。次に P r[R∗ |°6 ] について考える。Case 6 の場合、bS 6= bC のため、A にはチャレンジ暗号文として
5

ID∗ と ID∗ の下で暗号化された m0 ||r0 の暗号文 y ∗ が与えられる。y ∗ は r∗ の情報を含まないため、A が r∗ に関して得る情報は、ID∗ = Hk (r∗ ) のみである。この状況の下、r∗ と等しくなる下位 γ ビットを持つ平文の暗号文を復号クエリとして一つ以上問い合わているということは、ID∗ = Hk (r∗ ) のみ与えられて r∗ を求めたことになる。その確率は、ID∗ のみを与えられて r∗ も含めた集合{r|ID∗ = Hk (r)}(3 r∗ ) の元をいずれか一つを求める確率以下であり、このような確率は H の一方向性により
高々²ow となる。従って、以下の様に評価できる。
Pr[R∗¯ |°6 ] ≤ ²ow
Pr[°
6 ] については、Pr[°
3 ] と全く同様の議論により、°
Pr[ 6 ] = 1/4
以上により、Case 6 の S のアドバンテージは、
Adv6 = Pr[°
6 ] · (Pr[R∗ |°6 ] − Pr[R∗¯ |°6 ]) ≥ −1/4 · ²ow

ならば十分である。
暗号文サイズのオーバーヘッド 提案した公開鍵暗号 Π0の、内部の ID ベース暗号 Π からの暗号文サイズのオーバーヘッドは、平文と共に暗号化されている乱数 r のサイズと、ID = Hk (r) のサイズの和、すなわちハッシュ関
数 H の入力長及び出力長の和である。提案方式の安全性
証明には H の一方向性及びターゲット衝突困難性しか使用していない。これらの性質は、誕生日攻撃の脅威にさらされないため、κ ビット安全性の達成のためには入力長、出力長それぞれ κ ビット程度あればよい。従って、暗号文サイズのオーバーヘッドはおよそ 2κ ビット、128
ビット安全性達成のためにはおよそ 256 ビットとなる。

IND と NM の溝 我々の構成法は、BK 変換 [4] から、
MAC 及び汎用ハッシュ関数を取り除いた形になっている。この構成法で CCA 安全性を証明できるということ
は、IND-sID-CPA と NM-sID-CPA の間には大きな差があることを暗に示していると考えることができる。

アドバンテージの評価 以上の議論で、全ての Case のア
ドバンテージを評価した。これらを用いて AdvNM-sID-CPA
Π,Sを計算する。
P6
AdvNM-sID-CPA= i=1 Advi
Π,S
≥ 1/2 · (1/2 + ²cca ) · (1 − Pv ) · α · (1 − Pγ )+ 1/2 · Pk · Pv · α · (1 − Pγ )− 1/4 · α · (1 − Pγ )− 1/2 · (1/2 − ²cca ) · (1 − Pv) · Pγ
+ (1 − Pk ) · Pv · 1/2 · {1/qD · (1 − ²tcr ) − Pγ }− 1/4 · ²ow
このうち第 2 項と第 5 項に注目し、
α = {1/qD · (1 − ²tcr ) − Pγ }/(1 − Pγ )とおくと、Pk に関する項が消える。以降この α を用いて計算していく。
AdvNM-sID-CPA
Π,S≥ 1/2 · (1/2 + ²cca ) · (1 − Pv ) · {1/qD · (1 − ²tcr ) − Pγ }− 1/4 · {1/qD · (1 − ²tcr ) − Pγ }− 1/2 · (1/2 − ²cca ) · (1 − Pv) · Pγ
+ 1/2 · Pv · {1/qD · (1 − ²tcr ) − Pγ )− 1/4 · ²ow(αに上記値を代入)= 1/2 · 1/qD · Pv · (1/2 − ²cca ) · (1 − ²tcr )+ 1/2 · 1/qD · (1 − ²tcr ) · ²cca − 1/4 · Pγ − 1/4 · ²ow(Pv に関する項とそうでない項に分類し、整理)最後の等式の第 1 項について、IND-CCA 安全性、ターゲット衝突困難性それぞれの定義により (1/2−²cca ≥ 0)、(1 − ²tcr ) ≥ 0、確率の定義により Pv ≥ 0 なので、(第 1項)≥ 0 である。従って、以下が得られる。
AdvNM-sID-CPA
Π,S≥ 1/2 · 1/qD · (1 − ²tcr ) · ²cca − 1/4 · (²ow + 1/2γ )以上の議論から、A が ²cca のアドバンテージで Π0 を破り、H が (t, ²tcr )-TCRHF かつ (t, ²ow )-OWHF である
場合、前述の α を A を信用する確率として用いること
で、S は上記のアドバンテージで Π の NM-sID-CPA 安
全性を破ることができる。

4

まとめ

本稿では、任意の頑強性を持つ IBE に基づく CCA 安
全性を持つ PKE の構成法を示した。構成要素として、
IBE 以外には一方向性とターゲット衝突困難性を併せ持つ一つのハッシュ関数しか必要とせず、構成法は効率的である。安全性証明は、これまでの IBE-PKE 変換の方法とは本質的に異なり、IBE の頑強性に帰着するが、暗号技術の安全性をある種の暗号方式の頑強性に帰着する様な方式はこれまでほとんど存在しないため、本稿での証明は新しい証明技法として興味深い。現在まで NMsID-CPA 安全性を持つと示されている IBE は本質的には存在しないため、我々の結果は理論的な意味合いが強
いが、今後、頑強性についての研究、議論が進めば、我々の結果が実用的にも大きな意味を持つ可能性が出てくることが期待できる。

参考文献[1] M. Abe, Y. Cui, H. Imai, E. Kiltz, “Efficient Hybrid Encryption from ID-Based Encryption,” Available ateprint.iacr.org/2007/023/[2] N. Attrapadung, Y. Cui, D. Galindo, G. Hanaoka, I. Hasuo, H. Imai, K. Matsuura, P. Yang, R. Zhang, “Relations
Among Notions of Security for Identity Based Encryption
Schemes,” Proc. of LATIN’06, LNCS 3887, pp. 130-141,
2006.
[3] M. Bellare, A. Desai, D. Poincheval, P. Rogaway, “Relations
among Proc. of CRYPTO’98, LNCS 1462, pp. 26-45, 1998.
[4] D. Boneh, J. Katz, “Improved Efficiency for CCA-Secure
Cryptosystems Built Using Identity-Based Encryption,”
Proc. of CT-RSA’05, LNCS 3376, pp.87-103, 2005.
[5] X. Boyen, Q. Mei, B. Waters, “Direct Chosen Ciphertext
Security from Identity-Based Techniques,” CR-RSA’05,
LNCS 3376, pp. 87-103, 2005.
[6] R. Canetti, S. Halevi, J. Katz, “Chosen-Ciphertext Security from Identity-Based Encryption,” Proc. of EUROCRYPT’04, LNCS 3027, pp. 207-222, 2004.
[7] R. Cramer, V. Shoup, “Design and Analysis of Practical
Public-Key Encryption Schemes Secure against Adaptive
Chosen Ciphertext Attack,” SIAM Journal on Computing ，Vol. 33, pp. 167-226, 2003.
[8] J. Håstad, R. Impagliazzo, L. Levin, M. Luby, “Construction of a Pseudorandom Generator from any One-Way Function,” SIAM J. Comp. 28(4):1364-1396, 1999.
[9] R. Zhang, “Tweaking TBE/IBE to PKE Transforms with
Chameleon Hash Functions,” Proc. of ACNS’07, LNCS
4521, pp. 323-339, 2007.

ハッシュ関数のターゲット衝突困難性 今回の構成法で用いるハッシュ関数では、本質的な意味でのターゲット衝
突困難性、すなわち ²tcr が無視できる値であることは必要としていない。定理 1 が成り立つためには、(1 − ²tcr )が無視できない値を持つと保障できる様なハッシュ関数6