鍵更新効能付き検索可能暗号の概念と一般的構成

Key-Updatable Public-Key Encryption with Keyword Search :Concept and Generic Construction

代表研究者

松崎

なつめ

長崎県立大学情報システム学部情報セキュリティ学科

教授

共同研究者

穴田

啓晃

長崎県立大学情報システム学部情報セキュリティ学科教授

1 はじめに検索可能暗号は，クラウドの安全な利用を目的とした高機能暗号の一種であり，クラウドに預託した暗号文
から，暗号化したクエリを用いて所望の情報を検索可能とする．検索可能暗号は，預託時と検索時に同じ鍵を用いる共通鍵型（Symmetric Searchable Encryption: SSE）と，異なる鍵を用いる公開鍵型（Public Key

Encryption with Keyword Search：PEKS）に分類される．このうち公開鍵型は，境，大岸，笠原 [8] が 2000
年に，また，Boneh と Franklin[2] が 2001 年に提案した ID ベース暗号（Identity-Based Encryption：IBE）
を応用し，匿名 IBE 方式から一般的に構成されることが知られている [1]．
本研究では，公開鍵型の検索可能暗号における鍵の更新に着目する．検索可能暗号は，従来より，検索を行うクライアント側の安全な鍵管理を前提としたうえで，様々な方式が検討されてきた．しかし，IoT 機器のよ
うに，安全性の確保のためのコストがかけにくいクライアントでの適用を考えると，今までの研究に加え，クライアントデバイスからの鍵漏洩への対策を考慮する必要がある．本研究で着目するクライアント鍵の更新
は，鍵漏洩対策の一アプローチであり，万が一，鍵が漏洩しても，鍵更新により，古い鍵が無効化されて，新しい鍵が利用される．
本稿では，鍵更新機能付き検索可能暗号の概念と要件を示し，その一般的構成を提案する．提案する一般的構成は，PEKS と公開鍵暗号を組み合わせたものである．さらに，鍵更新機能付きの検索可能暗号の安全性を，PEKS の安全性定義を拡張することにより定義し，上記一般的構成の安全性を示した．また，ベースとす
る PEKS の特性により，それぞれ，ランダムオラクルモデルと，スタンダードモデルの鍵更新機能付き検索
可能暗号が構成される．なお，鍵更新機能付き検索可能暗号には，以下の２つのモデルを考えることができる．第 1 のモデルは，クライアントデバイスの（秘密）鍵更新に伴い，対応する公開鍵も更新されるモデルである．このモデルでは，構成がシンプルで実装容易である一方，更新した公開鍵を，広く公開する方法が別途必要となるため，運用において課題がある．第 2 のモデルは，公開鍵を一定としたまま，鍵更新するモデルである．公開鍵を一定とするため，運用において利点がある一方，第 1 のモデルに比べると計算が複雑になる．
この構成は，秘密鍵を復号用と復号用鍵を更新する更新用の 2 種類に分けて，更新用の鍵を隔離することにより，一定の安全性を保障する鍵隔離型の暗号研究（例えば，[3]）を拡張したものとなっている．本稿では，第1

1 のモデルについて説明する．なお，第 2 のモデルについては，[10] を参考にするとよい．
本稿の構成は次のとおりである．まず，第 2 章で方式や安全性定義を整理した上で，第 3 章で鍵更新機能付
き検索可能暗号のモデルと要件を定義する．そして第 4 章で，第 3 章で定義した，鍵更新機能付き検索可能暗号を，既存の公開鍵型検索可能暗号をベースとし，公開鍵暗号を組み合わせることにより，一般的に構成する．第 5 章では，IoT 機器での実装を見据えた評価結果を示す．

2 準備
2.1 公開鍵暗号
公開鍵暗号 (Public Key Encryption: PKE) PKE = (PG, G, E, D) は以下のように定義される．

• PG(1λ ) → parpke : セキュリティパラメータ 1λ を入力として，公開パラメータ parpke を出力する．
• G(parpke ) → (dk, ek): 公開パラメータ parpke を入力として，鍵ペア（復号鍵 dk と暗号化鍵 ek）を出力する．

• E(ek, m) → ct: 暗号化鍵 ek と平文 m ∈ Mpke を入力して，暗号文 ct を出力する．M はセキュリ
ティパラメータによって決まる平文集合である．

• D(dk, ct) → m or ⊥: 復号鍵 dk と暗号文 ct を入力として，m または復号失敗を表す ⊥ を出力する．
上記モデルは以下の正当性を要求する．全ての λ ∈ N, parpke ← PG(1λ ), (dk, ek) ← G(parpke ), 任意のm ∈ M に対して，D(dk, E(ek, m)) = m.
本 稿 で 扱 う 安 全 性 で あ る 選 択 平 文 攻 撃 に 対 す る 識 別 不 可 能 性 (IND-CPA) に つ い て ，以 下 の 試 行
λExpCPA
PKE,A (1 ) を考える．
λ
ExpCPA
PKE,A (1 )parpke ← PG(1λ ), (dk, ek) ← G(parpke )(m∗0 , m∗1 , state) ← A(parpke , ek) s.t. |m∗0 | = |m∗1 |b ← {0, 1}, ct∗b ← E(ek, m∗b )$b′ ← A(state, ct∗b )If b′ = b return 1 else return 0

λ
定義 2.1 (IND-CPA) 任 意 の 確 率 的 多 項 式 時 間 攻 撃 者 A に 対 し て ，PKE が AdvCPA
PKE,A (1 ):=λ| Pr[ExpCPA
PKE,A (1 ) = 1] − 1/2| < ϵ(λ) を満たすとき，PKE は IND-CPA を満たすという．

2.2 検索可能暗号
検索可能暗号 (Public Key Encryption with Keyword Search: PEKS) PEKS = (Setuppeks , KeyGenpeks , Encpeks ,Trapdoorpeks , Testpeks ) は以下のように定義される．
• Setuppeks (1λ ) → parpeks : セキュリティパラメータ 1λ を入力として，公開パラメータ parpeks を出力する．

2

• KeyGenpeks (parpeks ) → (msk, mpk): 公開パラメータを parpeks を入力として，鍵ペア（秘密鍵 mskと公開鍵 mpk）を出力する．

• Encpeks (mpk, w) → ctw : 公開鍵 mpk と検索キーワード w ∈ W を入力として，検索用の暗号文（暗号 index）ctw を出力する．W はセキュリティパラメータによって決まるキーワード集合である．

• Trapdoorpeks (msk, w′ ) → tdw′ : 秘密鍵 msk と検索キーワード w′ ∈ W を入力として，トラップドア
tdw′ を出力する．
• Testpeks (tdw′ , ctw ) → 1 or 0: 暗号文 ctw とトラップドア tw′ を入力として，もし w = w′ であれば1 を出力する．そうでなければ 0 を出力する．
上記モデルは以下の正当性を要求する．全ての λ ∈ N, 全ての parpeks ← Setuppeks (1λ ), 全ての (msk, mpk) ←KeyGenpeks (parpeks ), 全ての w ∈ W に対して，
Testpeks (Trapdoorpeks (msk, w), Encpeks (mpk, w)) = 1.
本稿で扱う安全性である選択キーワード攻撃に対する識別不可能性 (IND-CKA) について，次の試行
λ
ExpCKAPEKS,A (1 ) を考える．
λ
ExpCKAPEKS,A (1 )parpeks ← Setuppeks (1λ )(msk, mpk) ← KeyGenpeks (parpeks )(w0∗ , w1∗ , state) ← AOtd (parpeks , mpk)

s.t. |w0∗ | = |w1∗ |b ← {0, 1}, ct∗wb∗ ← Encpeks (mpk, wb∗ )$b′ ← AOtd (state, ct∗wb∗ )If b′ = b return 1 else return 0A はオラクル Otd にアクセスできる．Otd は，A から w を受け取り，tdw ← Trapdoorpeks (msk, w) を返す
オラクルであり，w ∈/ {w0∗ , w1∗ } でなくてはならない．これは，A が可能な限りトラップドアを手に入れられること，すなわち攻撃者とクラウドの結託を想定していることを意味する．
定義 2.2 (IND-CKA [1])λ任意の確率的多項式時間攻撃者 A に対して，PEKS が AdvCKA
PEKS,A (1 ) :=λ| Pr[ExpCKA
PEKS,A (1 ) = 1] − 1/2| < ϵ(λ) を満たすとき，PEKS は IND-CKA を満たすという．
λまた，以下の計算量的一貫性 (Computational Consistency) を考える．以下の試行 ExpCons
PEKS,A (1 ) を考える．
λExpCons
PEKS,A (1 )parpeks ← Setuppeks (1λ )(msk, mpk) ← KeyGenpeks (parpeks )(w0∗ , w1∗ ) ← AOtd (parpeks , mpk) s.t. |w0∗ | = |w1∗ |ct∗w0∗ ← Encpeks (mpk, w0∗ )tdw1∗ ← Trapdoorpeks (msk, w1∗ )If Testpeks (tdw1∗ , ctw0∗ ) = 1 and w0∗ ̸= w1∗ return 1else return 03ଛਦ崗嵑崌崊嵛崰

 ౲౏
崽崏嵤崢

崌嵛崯崫崗崡
आഇ
崕嵤嵗嵤崱

พಀધ

พಀ৲

พಀધ

ਁ৫ჶ

؆Ԇ̉

̉؆Ԇ

 ̉؆Ԇ
崽崏嵤崢
 आഇ
崽崏嵤崢

崗嵑崎崱

आഇ
嵗嵤崱

7UDSGRRU

崰嵑崫崿崱崊

෸ഡჶ

พಀધ
؆Ԇ

7HVW
आഇഇ‫܆‬

ਭਦ崗嵑崌崊嵛崰

図 1 鍵更新機能付き検索可能暗号（KU-PEKS）の概念モデル

IND-CKA 同様，A はオラクル Otd に同様の制限の下でアクセスできる．
定義 2.3 (Computational Consistency[1]) 任 意 の 確 率 的 多 項 式 時 間 攻 撃 者 A に 対 し て ，PEKS がConsλλ
AdvCons
PEKS,A (1 ) := Pr[ExpPEKS,A (1 ) = 1] < ϵ(λ) を満たすとき，PEKS は Computational Consistency を満たすという．

3 鍵更新機能付き検索可能暗号
3.1 概念と要件
本節では，鍵更新機能付き検索可能暗号（Key Updatable Public Key Encryption with Keyword Search:

KU-PEKS) の概念モデルと要件を概説する．
図１に KU-PEKS の概念モデルを示す．KU-PEKS は送信クライアント，受信クライアント，クラウドの３つのエンティティからなる．また，通常の検索可能暗号における (1) 預託フェーズと，(3) 検索フェーズに加え，(2) 鍵更新フェーズを備える．鍵更新フェーズでは，受信クライアント側で鍵ペアを更新して更新鍵を生成し，クラウド側で更新鍵を用いて，暗号文を更新する．なお，ここでは検索キーワードを含むインデックスの暗号化と検索キーワードの暗号化について焦点をあて，ドキュメント自身の暗号化と復号については省略するものとする．

KU-PEKS Π = (Setup, KeyGen, ReKeyGen, Enc, ReEnc, Trapdoor, Test) は，以下の７個のアルゴリズムからなる．更新可能期間を T とし |T | = poly(λ) とする．

• Setup(1λ ) → pp: セキュリティパラメータ 1λ を入力として，公開パラメータ pp を出力する．公開
パラメータ pp は以降のすべてのアルゴリズムの入力となるが，簡単のため省略する．

• KeyGen(ski−1 , pki−1 ) → (ski , pki ): 期間 i − 1 ∈ T の鍵ペア (ski−1 , pki−1 ) を入力として，期間
i ∈ T の鍵ペア（秘密鍵 ski と公開鍵 pki ）を出力する．
• ReKeyGen(pki , ski , pki+1 ski+1 ) → rki→i+1 : 隣り合ったバージョンの鍵ペア (pki , ski ), (pki+1 , ski+1 )から，更新鍵 rki→i+1 を出力する．鍵の添字は，バージョン番号を示す．

4

(0)

• Enc(pki , w) → cw,i : バージョン i の公開鍵 pki と検索キーワード w ∈ W を入力して検索用の暗号文(0)（暗号 index）cw,i を出力する．暗号文の上の添え字は，更新の回数を示し，この時点では 0 である．
(k)

(k+1)

(k)

• ReEnc(rki→i+1 , cw,j ) → cw,j : 更新鍵 rki→i+1 を用いて，j + k = i であるような暗号文 cw,j を更(k+1)

新し，cw,jを出力する．

• Trapdoor(ski , w′ ) → tw′ ,i : バージョン i の秘密鍵 ski と検索キーワード w′ ∈ W を入力として，ト
ラップドア tw′ ,i を出力する．
(k)

(k)

• Test(tw′ ,i , cw,j ) → 1 or 0: j + k = i となるようなトラップドア tw′ ,i と暗号文 cw,j を入力として，もし w = w′ であれば 1 を出力する．そうでなければ 0 を出力する．

KU-PEKS の要件は以下の４点である．
要件 1：受信クライアントの新しい秘密鍵は，古い鍵，および公開の情報から導出困難であること．
要件 2：古い鍵は受信クライアントデバイスから速やかに削除すること．
要件 3：クラウドでは，更新前の古い公開鍵で暗号化された暗号文を対象に，更新後の新しい鍵で生成したトラップドアで検索できること．この要件は，可用性を目的としたものであり，受信クライアント
が，デバイスに保持する新しい鍵だけで，古い暗号文（更新前の古い公開鍵で暗号化された暗号文）を対象として検索可能とする．
要件 4：クラウドでは，更新後の新しい公開鍵で暗号化された暗号文を対象に，古い鍵で生成したト
ラップドアで検索できないこと．この要件は，漏洩の可能性のある古い鍵を無効化する意味を持つ．古い鍵で生成したトラップドアを用いて，古い公開鍵で暗号化された暗号文を対象とした検索を抑止することは難しい．しかし，本要件により，更新後の新しい公開鍵で暗号化された暗号文を対象とした検索は不可能となる．

3.2 安全性定義
正 当 性.

KU-PEKS Π は 以 下 の 復 号 の 正 当 性 を 要 求 す る ．全 て の λ ∈ N, 全 て の i = j + k と
i個

z
}|
{
な る よ う な i, j, k, pp ← Setup(1 ), (ski , pki ) ← KeyGen(KeyGen(· · · KeyGen( pp) · · · )) に つ い て ，
λ

(k)

(ℓ)

(ℓ−1)

Test(Trapdoor(ski , ω), cw,j ) → 1. ただし，cw,j ← ReEnc(ReKeyGen(skj+ℓ−1 , skj+ℓ ), cw,j ) (1 ≤ ℓ ≤ k) であり，i, j, k は λ の多項式である.
安全性. 以下の試行 ExpKU-CKA(1λ ) を考える．
Π,A
ExpKU-CKA
(1λ )
Π,A



ctr := 0, pp ← Setup(1λ )(sk1 , pk1 ) ← KeyGen(pp)(w0∗ , w1∗ , state) ← AO1 (pp, pk1 ) s.t. |w0∗ | = |w1∗ |b ← {0, 1}, c∗wb∗ ← Enc(pkctr , wb∗ )$b′ ← AO2 (state, c∗wb∗ )

If b′ = b return 1 else return 0A は以下のオラクル O1 = {Okg , Okl , Ork , Otd }, O2 = {Okl , Ork , Otd } にアクセスできる．各オラクルの5説明は次の通りである．

Okg : A からクエリを受け取り，ctr := ctr + 1 とし，(skctr , pkctr ) ← KeyGen(skctr−1 , pkctr−1 ) を実行，pkctr
を A に返すオラクル．skctr は保持しておく．

Okl : A から i を受け取り，ski を返すオラクル．
Ork : A から i を受け取り，rki−1→i ← ReKeyGen(ski−1 , ski ) を返すオラクル．
Otd : A から (i, w) を受け取り，tw,i ← Trapdoor(ski , w) を返すオラクル．
A がチャレンジ後は Okg にアクセスできないことに留意する．また，A は以下の制限を除き，自由にオラク
ルにアクセスできる．

• Okl にクエリする i は i < ctr でなくてはならない．これは，現在の期間以外であれば，任意の過去の期間の秘密鍵漏洩を許していることを意味する．

• Ork にクエリする i は i ≤ ctr でなくてはならない．これは，A が全ての再暗号化鍵を手に入れられること，すなわち攻撃者とクラウドの結託も想定していることを意味する．

• Otd にクエリする (i, w) は i ≤ ctr, かつ w ∈/ {w0∗ , w1∗ } でなくてはならない．これは，A が可能な限りトラップドアを手に入れられること，すなわち攻撃者とクラウドの結託も想定していることを意味する．
定義 3.1 (IND-KU-CKA)

任意の確率的多項式時間攻撃者 A に対して，KU-PEKS Π が AdvKU-CKA(1λ ) :=
Π,A(1λ ) = 1] − 1/2| < ϵ(λ) を満たすとき，Π は IND-KU-CKA を満たすという．
| Pr[ExpKU-CKA
Π,A(1λ ) を考える．
計算量的一貫性. 以下の試行 ExpKU-Cons
Π,A

(1λ )
ExpKU-ConsΠ,A

ctr := 0, pp ← Setup(1λ )(sk1 , pk1 ) ← KeyGen(pp)(w0∗ , w1∗ ) ← AO (pp, pk1 ) s.t. |w0∗ | = |w1∗ |c∗w0∗ ← Enc(pkctr , w0∗ )tw1∗ ← Trapdoor(skctr , w1∗ )If Test(tdw1∗ , cw0∗ ) = 1 and w0∗ ̸= w1∗ return 1∗else return 0

∗|w | = |w̃ | であり，A は IND-KU-CKA と同様の制限の下，同様のオラクル O = {Okg , Okl , Ork , Otd } に
アクセスできる．
定義 3.2 (KU-Computational Consistency)

任意の確率的多項式時間攻撃者 A に対して，KU-PEKS Π が

AdvKU-Cons(1λ ) := Pr[ExpKU-Cons(1λ ) = 1] < ϵ(λ) を満たすとき，Π は計算量的一貫性 (KU-Computational
Π,AΠ,AConsistency) を満たすという．

6

4 構成
本 節 で は ，任 意 の PKE（ 公 開 鍵 暗 号 ）と PEKS（ 検 索 可 能 暗 号 ）を 用 い た KU-PEKS の 一 般 的 構成を提案する．具体的には，PKE PKE = (PG, G, E, D), 及び PEKS PEKS = (Setuppeks , KeyGenpeks ,Encpeks , Trapdoorpeks , Testpeks ) を用いて，KU-PEKS Π = (Setup, KeyGen, ReKeyGen, Enc, ReEnc, Trapdoor, Test)
を以下のように構成する．以下では，キーワード集合 W と PKE の平文集合 M を同一視する．

• Setup(1λ ) → pp: parpke ← PG(1λ ), parpeks ← Setuppeks (1λ ) を実行し，pp := (parpke , parpeks ) を出力する．

• KeyGen(ski−1 , pki−1 ) → (ski , pki ): ski−1 = (dki−1 , mski−1 ), pki−1 = (eki−1 , mpki−1 ) とする(i = 1 の時は空の文字列とする)．(dki , eki ) ← G(parpke ), (mski , mpki ) ← KeyGenpeks (parpeks ) を実行し，ski := (dki , mski ), pki := (eki , mpki ) を出力する．

• ReKeyGen(pki , ski , pki+1 ski+1 ) → rki→i+1 : ski = (dki , mski ), 及び ski+1 = (dki+1 , mski+1 ) とする．rki→i+1 := dki を出力する．
(0)

(0)

• Enc(pki , w) → cw,i : cti ← E(eki , w), 及び ctw,i ← Encpeks (mpki , w) を計算し，cw,i := (cti , ctw,i )を出力する，(k)(k+1)• ReEnc(rki→i+1 , cw,j ) → cw,j : i ̸= j + k であれば ⊥ を出力する．そうでなければ，rki→i+1 = dki(k)とし，cw,j = (cti , ctw,i ) とし，w ← D(dki , cti ) を計算する．cti+1 ← E(eki+1 , w) 及び ctw,i+1 ←(k+1)

Encpeks (mpki+1 , w) を実行し，cw,j:= (cti+1 , ctw,i+1 ) を出力する，′• Trapdoor(ski , w ) → tw′ ,i : ski = (dki , mski ) とし，tw′ ,i := tdw′ ,i ← Trapdoorpeks (mski , w′ ) を出力
する．
(k)

(k)

• Test(tw′ ,i , cw,j ) → 1 or 0: i ̸= j + k であれば ⊥ を出力する．cw,j = (cti , ctw,i ) とし，Testpeks (tw′ ,i ,
ctw,i ) の結果を出力する．
定理 4.1 PKE が IND-CPA を満たし，PEKS が IND-CKA を満たすならば，上記構成法による KU-PEKS

Π は IND-KU-CKA を満たす．
= 1 となることを S0 と書く．次の G1 , G2 , G3 を考え，同様に
証明. ExpKU-CKA
を G0 とし，ExpKU-CKA
Π,AΠ,A
S1 , S2 , S3 とする．
G1 : G0 において，チャレンジャーがランダムに i∗ ∈ T を推測するゲーム．チャレンジフェーズ時点 (A が(w0∗ , w1∗ ) を出力する時点) において，ctr ̸= i∗ であるイベントを Fail とする．S1 と Fail は独立事象であるから，Pr[S1 | ¬Fail] = Pr[S1 ] であり，この変更は A に何の影響も与えないので，Pr[S1 ] = Pr[S0 ] である．

G2 : G1 において，Fail が起きた場合に A の出力 b′ をランダムビットに置き換えるゲーム．Pr[Fail] =(|T | − 1)/|T |, Pr[S2 | ¬Fail] = Pr[S1 | ¬Fail] = Pr[S1 ]，及び Pr[S2 | Fail] = 1/2 であるから，
Pr[S2 ] −1
1
= Pr[S2 ∧ ¬Fail] + Pr[S2 ∧ Fail] −2
2
1|T | − 1 1 1=· Pr[S1 | ¬Fail] +
· −
|T |
|T |
2 2
1
1
=
Pr[S1 ] − .
|T |
2
7

G3 : G2 において，チャレンジ暗号文 cw∗ ,ctr = (ct∗i , ct∗w∗ ,i ) を作成する際に，ct∗i ← E(ekctr , wb∗ ) とす
(0)

b

b

るところをランダムな暗号文とする (すなわち ct∗i ← Cλ ) ゲーム．ctr (= i∗ ) 番目の鍵ペアにおける$(dkctr , ekctr ) を ExpCPA
PKE,B における鍵ペアとし，PKE の IND-CPA 安全性を破る攻撃者 B を構成することで，|Pr[S3 ] − Pr[S2 ]| ≤ AdvCPA
PKE,B であることを証明できる．
また，ctr (= i∗ ) 番目の鍵ペアにおける (mskctr , mpkctr ) を ExpCKA
PEKS,B における鍵ペアとし，PEKS のIND-CKA 安全性を破る攻撃者 B を構成することで，|Pr[S3 ] − 1/2| ≤ AdvCKA
PEKS,B であることを証明できる．
()
CKA
従って，AdvKU-CKA≤ |T | AdvCPA
Π,A
PKE,B + AdvPEKS,B .
定理 4.2 PKE が IND-CPA を満たし，PEKS が Computational Consistency を満たすならば，上記構成法による KU-PEKS Π は KU-Computational Consistency を満たす．
証明. 定理 4.1 と同様に証明可能であるため省略．
上記構成法は一般的構成法であるため，それぞれベースとする PEKS（検索可能暗号）の特性により，ランダムオラクルモデルの KU-PEKS，スタンダードモデルの KU-PEKS を実現可能である．例えば，Boneh-Franklin (Anonymous) IBE [2] を基にした PEKS (+ PKE として ElGamal 暗号等を組み合わせる) を適用することで，ランダムオラクルモデルの KU-PEKS が得られ，Jutla-Roy Anonymous IBE [4, 6] を基にした PEKS(+ PKE として ElGamal 暗号等を組み合わせる) を適用することで，スタンダードモデルの

KU-PEKS が実現できる．

5 実装性能の見積もり
本章では，4 章で説明した KU-PEKS の実装性能を見積もる参考として，Boneh-Franklin の PEKS（非対称ペアリング版）[2] をソフトウェアライブラリ TEPLA [5] を用いて実装した結果を示す．TEPLA は，筑波大学が開発を行ったオープンソースの C 言語暗号ライブラリである．楕円曲線暗号の演算や，ペアリング演算などを含む．表１に，PEKS の各関数ごとの処理時間を示す．計測の環境は，CPU:Intel Core

i7-3770(3.40GHz)，RAM:31 GB，OS:Linux(Ubuntu 15.04, kernel 3.19.0-15-generic) である．また，性能評価には，電子メールデータでの利用を想定し，Enron データセット [7] を用いている．Enron データセット
は，約 50 万個のメールを備えたデータセットであり，各メールの平均サイズは 2.68kB である．
表1

PEKS[2] の関数ごとの処理時間
関数

処理時間 (msec)

Enc

11.20

Trapdoor

1.04

Test

4.71

TEPLA のような通常のペアリング演算ライブラリは並列処理は想定していない．そのため処理時間は直接
プロセッサの周波数に依存する．例えば，IoT 組み込みデバイスとして利用される ARM の Cortex-M7 の周
波数が 300MHz であることを考慮すれば，Enc と Trapdoor の処理時間は，表の数値の約 11.3 倍となる．つまり，Enc は 127msec，Trapdoor は 11.8msec と換算される．この数値は，IoT デバイスを想定している我々

8

のシナリオでは十分実現可能な処理時間であると考えられる．

6 まとめ
本稿では，IoT 機器を想定し，クライアントデバイスからの鍵漏洩に対策した，鍵更新機能付き検索可能
暗号について概念と一般的構成を示した．一般的構成は，公開鍵が更新されるモデルにおいて，IND-CKA 安
全性を持つ既存検索可能暗号と，IND-CPA 安全性を持つ公開鍵暗号を組み合わせている．また，構成の主な構成要素である Enc と Trapdoor について実装評価し，IoT デバイスにおいて十分実用的な方法であることを示した．
謝辞 本報告書は，主に文献 [9] の内容となっている．本報告書の報告者 2 名は，[9] の共著である，東邦大学
大学院理学部情報科学科の金岡晃氏，および電気通信大学大学院情報理工学研究科の渡邉洋平氏に感謝の意を
表する．

参考文献
[1] M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven,
P. Paillier, and H. Shi. Searchable encryption revisited: Consistency properties, relation to anonymous ibe, and extensions. J. Cryptology, 21(3):350–391, 2008.
[2] D. Boneh and M. K. Franklin. Identity-based encryption from the weil pairing. In Proceedings of the
21st Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’01, pages
213–229, London, UK., 2001. Springer-Verlag.
[3] Y. Dodis, J. Katz, S. Xu, and M. Yung. Key-insulated public key cryptosystems. In Proceedings ofthe International Conference on the Theory and Applications of Cryptographic Techniques: Advancesin Cryptology, EUROCRYPT ’02, pages 65–82, London, UK, UK, 2002. Springer-Verlag.
[4] C. S. Jutla and A. Roy. Shorter quasi-adaptive NIZK proofs for linear subspaces. In K. Sako and
P. Sarkar, editors, Advances in Cryptology – ASIACRYPT 2013, volume 8269 of Lecture Notes in
Computer Science, pages 1–20. Springer Berlin Heidelberg, 2013.
[5] U. of Tsukuba. Tepla: University of Tsukuba Elliptic, curve and Pairing Libraary, Jan.2013 Released
TEPLA 1.0, Dec-2015 Released TEPLA 2.0. http://www.cipher.risk.tsukuba.ac.jp/tepla/.
[6] S. C. Ramanna and P. Sarkar. Eﬃcient (anonymous) compact HIBE from standard assumptions.
In S. Chow, J. Liu, L. Hui, and S. Yiu, editors, Provable Security, ProvSec 2014, volume 8782 ofLecture Notes in Computer Science, pages 243–258. Springer International Publishing, 2014.
[7] C. M. University. Enron email dataset, May 7, 2015. http://www.cs.cmu.edu/ enron/.
[8] 境隆一, 大岸聖史, and 笠原正雄. Cryptosystems based onpairing. Symposium on Cryptography andInformation Security (SCIS2000), 2000.
[9] 松崎なつめ, 穴田啓晃, 金岡晃, and 渡邉洋平. 鍵更新機能付き検索可能暗号の一般的構成. Symposiumon Cryptography and Information Security (SCIS2018), 2018.
[10] 渡邉洋平, 穴田啓晃, and 松崎なつめ. 鍵更新機能付き検索可能暗号：鍵隔離暗号モデルによる実現.
Computer Security Symposium 2017, 2017.

9

＜発表資料＞
題名
鍵更新可能な検索可能暗号の一提案

掲載誌・学会名等
電子情報通信学会信学技報

vol. 117, no. 25, ISEC2017-1
鍵更新機能付き検索可能暗号：コンピュータセキュリティシンポジウム

公開鍵更新モデルによる実現

2017 論文集

鍵更新機能付き検索可能暗号：コンピュータセキュリティシンポジウム

鍵隔離モデルによる実現

2017 論文集

鍵更新機能付き検索可能暗号の一般的構成

暗号と情報セキュリティシンポジウム

2018 論文集10

発表年月2017 年 5 月
2017 年 10 月
2017 年 10 月
2018 年 1 月