クラウドストレージサービスにおける安全なキー ワード検索 How to Keyword-search securely in Cloud Storage Service 黒澤 馨 Kaoru KUROSAWA アブストラクト クラウドストレージサービスは既に商用化されており グーグル アマゾンなど多

クラウドストレージサービスにおける安全なキー

ワード検索

How to Keyword-search securely in Cloud Storage Service

黒澤 馨

Kaoru KUROSAWA アブストラクト クラウドストレージサービスは既に商用化されており，グーグル，アマゾンなど多くの IT 企業によってサー ビスが提供されている．各ファイルは暗号化した上で保存した方が安全であるが，その反面，暗号化するとキーワード検 索すらできなくなってしまう．この相反する二つの問題を解決する手段として，近年，共通鍵暗号に基づく検索可能暗号 (SSE)方式が活発に研究されている．本稿では，最も基本的な単一キーワード検索 SSE 方式の原理について解説するとと もに，その安全性の定義及び構成法に関する最近の研究成果について紹介する． キーワード クラウド・ストレージ・サービス，共通鍵暗号，キーワード検索，検索可能暗号

Abstract Cloud storage service is now cowcommercially available. Major Internet enterprises such as Google and Amazon are providing these services. A searchable symmetric encryption scheme is a symmetric-key encryption scheme by which a client can efficiently retrieve encrypted files containing (or indexed by) specific keywords, keeping the keywords them-selves secret. In this survey, we review the security definitions and efficient constructions of single-keyword Searchable Symmetric Encryption (SSE) schemes.

Key words Cloud storage service, symmetric-key encryption, keyword search, searchable symmetric encryption

1.

は じ め に

インターネットを利用したクラウド・ストレージ・サービス において，以下のようなモデルを考える．格納フェーズにおい て，クライアントはサーバに，共通鍵暗号で暗号化したファイ ルの集合を格納する．検索フェーズにおいて，クライアントは， 検索キーワードを秘密にしたまま，そのキーワードを含むファ イルを取り出す．このように，情報セキュリティと利便性の双 方を両立させるキーワード検索方式を，Searchable Symmetric Encryption(SSE)方式という．

最初の SSE 方式は，2000 年に Song, Wagner, Perrig によっ

て提案された（1）_{．その後，ファイルの更新や追加を伴わない静} 的単一キーワード検索 SSE 方式に関する研究（2）∼（6）_{，ファイル} の更新や追加を可能とする動的単一キーワード検索 SSE 方式に 関する研究（7）∼（9）_{，静的複数キーワード検索 SSE 方式に関する} 研究（10）∼（16）_{，ある種の限界}（17）_{など，様々な側面にわたって活} 発に研究されている（表 1 参照）．また，そのクラウド世界にお ける重要性から，アメリカ国防高等研究計画局 (DARPA) のレ ポートにも取り上げられている（18）_． 本稿では，最も基本的な静的単一キーワード検索 SSE 方式の 黒澤 馨 正員：フェロー 茨城大学工学部情報工学科 E-mail [email protected]

Kaoru KUROSAWA, Fellow, Member (Department of Computer and Information Sciences, College of Engineering, Ibaraki University, Hitachi-shi, 316-8511 Japan).

電子情報通信学会 基礎・境界ソサイエティ

Fundamentals Review Vol.9 No.1 pp.47–57 2015年 7 月 c ⃝電子情報通信学会 2015 表 1 SSE 方式の研究動向 静的 動的 単一キーワード検索 SSE 方式 （1）∼（6） （7）∼（9） 複数キーワード検索 SSE 方式 （10）∼（16） – 原理について解説するとともに，その安全性の定義及び構成法 に関する最近の研究成果について紹介する．動的単一キーワー ド検索 SSE 方式に関する研究及び静的複数キーワード検索に関 する研究については，筆者の解説スライドを参照されたい（19）_．

2. SSE

方式とは

2. 1

モ デ ル

ファイルの集合をD = {D1,· · · , Dn}，キーワードの集合を W = {w1,· · · , wm} とし，索引 Index = {ei,j} を以下のよう な m× n の２値行列とする． ei,j=    1 ifキーワード wiがファイル Djに含まれる 0 otherwise .(1) また，D(w) によってキーワード w を含むファイル Diの集合 を，C(w) によってキーワード w を含むファイル Diの暗号文 Ci= E(Di)の集合を，List(w) によってキーワード w を含む ファイル Diのファイル番号 i の集合を表す． 例を示そう．D = {D1,· · · , D5}，W = {w1, w2} 及び

Index =   1 0 1 0 1 0 1 0 1 0   (2) とすると， List(w1) = {1, 3, 5}   D(w1) = {D1, D3, D5} C(w1) = {C1, C3, C5} である．同様に， List(w2) = {2, 4} D(w2) = {D2, D4} C(w2) = {C2, C4} となる． このとき，以下のように振る舞う確率的多項式時間アルゴリ ズムの組（クライアント，サーバ）を認証可能 SSE 方式という． （図 1）． （格納フェーズ） （ 1 ） クライアントは，まず，外部入力として (D, W, Index) を受け取り，秘密鍵 K をランダムに生成する． 次に，各ファイルの暗号文の集合C，及び索引の暗号 文集合I を生成し，それらをサーバに送る． （ 2 ） サーバは，(C, I) を保管する． ここで，I は，各キーワード wiに関する認証子 T agiも含むも のとする． （検索フェーズ） （ 1 ） クライアントは，検索キーワード w を入力として受け 取り，秘密鍵 K を基にトラップドア情報 t(w) を求め， t(w)をサーバに送る． （ 2 ） サーバは，受け取った t(w) と保管してある (C, I) か ら (C(w), T ag) を求め，(C(w), T ag) をクライアントに 返す．ただし，T ag は認証子である． （ 3 ） クライアントは，(t(w), C(w), T ag) の正しさを秘密鍵 Kを基に検証する．もし正しければ，各暗号文 Ci∈ C(w) を復号し，D(w) を外部へ出力する．そうでなければ，re-jectを外部へ出力する． 以上の記述から認証子 T ag に関する部分を取り除くと，通常の SSE方式のモデルとなる．（認証可能 SSE 方式は，筆者らによっ て導入された（5），（6）_．） 図 1 認証可能 SSE 方式（文献 (6) より引用）

2. 2

通常の

SSE

方式の構成

文献（7）において筆者らが示した通常の SSE 方式を示そう．f を出力が 128bit の擬似ランダム関数，g を出力が n = 5bit の 擬似ランダム関数（20），（21）_{とする．また，SKE = (E, E}−1_)を 共通鍵暗号方式（20），（21）_{とする．ただし，E は暗号化アルゴリ} ズム，E−1は復号アルゴリズムである．理解の容易さのため， 2.1の例を使って説明する． （格納フェーズ）クライアントは，以下のように動作する． （ 1 ） f の秘密鍵 k，g の秘密鍵 k′，SKE の秘密鍵 keをラ ンダムに生成する． （ 2 ） ファイル D1, . . . , D5の暗号文 C1= Eke(D1), . . . , C5= Eke(D5) を計算し，C = (C1, . . . , C5)と置く． （ 3 ） 索引の暗号文として index1 = (10101)⊕ gk′(w1) index2 = (01010)⊕ gk′(w2) を計算する．ただし，⊕ は bit ごとの XOR を表す． （ 4 ） 集合{1, 2} 上の置換 σ をランダムに選び，索引の暗号 文集合を I =   fk(wσ(1)), indexσ(1) fk(wσ(2)), indexσ(2)   と置く．例えば，σ(1) = 2, σ(2) = 1 とすると， I =   fk(w2), index2 fk(w1), index1   である． （ 5 ） (C, I) をサーバに格納し，秘密鍵 K = (k, k′, ke)を秘 密に保持する． （検索フェーズ） （ 1 ） 簡単のため，検索キーワードを w1とする．このとき， クライアントは，トラップドア情報 t(w1) = (fk(w1), gk′(w1)) を計算し，t(w1)をサーバに送る． （ 2 ） サーバは，まず，fk(w1)を含むI の行を求める．次 に，その行に含まれる index1から， index1⊕ gk′(w1) = (10101) を計算する．これを基に， C(w1) = (C1, C3, C5) をクライアントに返す． （ 3 ） クライアントは，(C1, C3, C5)を復号し，

D(w1) = (D1, D3, D5) を出力する．

3.

安全性の定義

本章では，認証可能 SSE 方式の安全性概念であるプライバシー と信頼性について説明する．プライバシーは，(D, W, Index) に 関する情報がサーバに漏えいしないことを意味する．信頼性は， サーバが正しくない検索結果を返した場合，クライアントがそ れを検出できることを意味する．（通常の SSE 方式においては， プライバシーのみを考える．）

3. 1

プライバシー

どのような SSE 方式であっても，以下の情報がサーバに漏れ てしまう． • 格納フェーズにおいては，(C, I) から，ファイル数 n，各 ファイル Diの長さ|Di|，キーワードの個数 m がサーバに漏 れる． • 検索フェーズにおいては，検索キーワードが w の場合， List(w)がサーバに漏れる．なぜなら，そうでないと，サーバ は C(w) を返せないからである． 以上を，最小漏えい情報と呼ぼう．このとき，最小漏えい情 報以外の情報は何もサーバに漏れない，という概念がプライバ シーである．この概念は以下のように定式化される（2），（5），（22）_． （認証可能）SSE 方式（クライアント，サーバ）に対し，dis-tinguisher（識別者）B とチャレンジャー（挑戦者） の間の２ 通りのゲームを考える．B は，現実ゲーム（実際の（認証可能） SSE方式，図 2）かシミュレーションゲーム（最小漏えい情報だ けを含む模擬環境，図 5）のいずれかに属し，チャレンジャーと の対話によりいずれのゲームに属するかを推測する．B がゲー ムを正しく推測できないときに，（認証可能）SSE 方式はプライ バシーを満たすという． 正確な定義を見てみよう．B とチャレンジャーの間の現実ゲー ムを図 2 のように定義する（図 3，図 4 も参照のこと．）現実 ゲームでは，チャレンジャーはクライアントのアルゴリズムに 従って動作し，（認証可能）SSE 方式を正直に実行する． 現実ゲーム





（格納フェーズ） （ 1 ） distinguisher B は，(D, W, Index) を選び，チャレ ンジャーに送る． （ 2 ） チャレンジャーは，(C, I) を返す． （検索フェーズ） 以下を i = 1,· · · , q について実行する． （ 1 ） distinguisher B は，キーワード ˜wiを選び， チャレ ンジャーに送る． （ 2 ） チャレンジャーは，トラップドア情報 t( ˜wi)を返す． 最後に，distinguisher B は，b = 0 or 1 を出力する．





図 2 現実ゲーム（文献 (6) より引用） 図 3 現実ゲーム：格納フェーズ（文献 (6) より引用） ht] 図 4 現実ゲーム：検索フェーズ（文献 (6) より引用） シミュレーションゲーム





（格納フェーズ） （ 1 ） distinguisher B は，(D, W, Index) を選び，チャレ ンジャーに送る． （ 2 ） チャレ ン ジャー は ，最 小 漏 え い 情 報 で あ る ファイ ル 数 n，キ ー ワ ー ド 数 m，及 び 各 ファイ ル の サ イ ズ |D1|, · · · , |Dn| をシミュレータ S に送る． （ 3 ） S は，(C′,I′)を計算しチャレンジャーに返す． （ 4 ） チャレンジャーは，(C′,I′)を B に返す． （検索フェーズ） 以下を i = 1,· · · , q について実行． （ 1 ） B は，キーワード ˜wiを選び， チャレンジャーに送る． （ 2 ） チャレンジャーは，最小漏えい情報である List( ˜wi) をシミュレータ S に送る． （ 3 ） S は，t′( ˜wi)を計算しチャレンジャーに返す． （ 4 ） チャレンジャーは，t′( ˜wi)を B に返す． 最後に，distinguisher B は，b = 0 or 1 を出力する．





図 5 シミュレーションゲーム（文献 (6) より引用） 次に，B とチャレンジャーの間のシミュレーションゲームを 図 5 のように定義する．（図 6，図 7 も参照のこと．）シミュレー ションゲームでは，チャレンジャーは（認証可能）SSE 方式を 実行せず，B がゲームの識別に用いる情報をシミュレータ S を 利用して生成する． 上記において，distinguisher B 及びシミュレータ S は確率 的多項式時間アルゴリズムである．ここで，B が現実ゲームに おいて b = 1 を出力する確率を Preal，シミュレーションゲーム において b = 1 を出力する確率を Psimとする．（B は，自分が 現実ゲームにおいてプレーしていると思ったら b = 1 を出力し， 自分がシミュレーションゲームにおいてプレーしていると思っ たら b = 0 を出力する．） 更に，B のアドバンテージ Advpriv_S (B)を Advpriv_S (B) =|Preal− Psim|

図 6 シミュレーションゲーム：格納フェーズ（文献 (6) より引用）

図 7 シミュレーションゲーム：検索フェーズ（文献 (6) より引用）

と定義し，AdvprivS を

Advpriv_S = max

B AdvS(B)

と置く．（常に b = 1 を出力する B に対しては Advpriv_S (B) = 0 となるが，賢い B に対する AdvprivS (B)の値は大きくなるであ

ろう．そこで，B に関する AdvprivS (B)の最大値を考える．）

このとき，プライバシーは以下のように定義される． ［定義 3.1］ AdvprivS が negligible（注 1）となるようなシミュレー

タ S が存在するとき，（認証可能）SSE 方式はプライバシーを満

たすと定義する．

この定義は，直感的には以下のように解釈することができる．

|Preal− Psim| が negligible だとすると，シミュレータ S は最

小漏えい情報のみから (C, I) 及び t(w) を生成できた，という ことになる．ということは，(C, I)，t(w) からは，最小漏えい 情報しか漏れていない．したがって，サーバには最小漏えい情 報しか漏れていない．

3. 2

信 頼 性

認証可能 SSE 方式 (クライアント，サーバ) は，I の一部と して，キーワードに対する認証子 T ag をサーバに記憶させる． 認証可能 SSE 方式における信頼性は，サーバが正しくない検索 結果を返した場合，クライアントは認証子 Tag を利用してそれ を検出できる概念である（5）_． 認 証 可 能 SSE 方 式 の 信 頼 性 を ，ク ラ イ ア ン ト と 敵 A = (A1, A2)との対話で定義する．ここで，敵 A は確率的多項 式時間アルゴリズムである．A1はクライアントにプロトコルの （注 1）：任意の多項式 p(λ) の逆数 1/p(λ) より速く減衰する関数 ϵ(λ) を negli-gibleと呼ぶ．ただし，λ はセキュリティ・パラメータであり，鍵サイズを表す． 入力を与え，出力を受け取り 0 または 1 を出力する．A2は不 正なサーバとして振る舞う．以下のような実験を考える． （格納フェーズ） （ 1 ） A1は，(D, W, Index) を選び，クライアントに送る． （ 2 ） クライアントは，秘密鍵 K を生成して (C, I) を求め， (C, I) を A2に送る． （検索フェーズ）i = 1, . . . , q に対し，以下を実行する． （ 1 ） A1は，検索キーワード ˜wiを選び，クライアントに 送る． （ 2 ） クライアントは，トラップドア情報 t( ˜wi)を求め，t( ˜wi) を A2に送る． （ 3 ） A2は，(C( ˜wi)′, T ag′i)をクライアントに返す． （ 4 ） クライアントは，D( ˜wi)′または reject を計算し，A1 に返す． A1が D( ˜wi)′ |= D( ˜wi) となる D( ˜wi)′を受け取ったとき，敵 (A1, A2)は攻撃に成功し た，ということにしよう．このとき，敵 (A1, A2)のアドバン テージを

Advauth(A1, A2) = Pr((A1, A2)が攻撃に成功)

と定義する．更に Advauth= max

(A1,A2)

Advauth(A1, A2)

と置き，信頼性を以下のように定義する．

［定義 3.2］ Advauth_{が negligible であるとき，認証可能 SSE}

方式は信頼性を満たすと定義する． 次に，強信頼性を定義する．クライアントが (C( ˜wi)′, T ag′i) |= (C( ˜wi), T agi) となる (C( ˜wi)′, T agi′)を accept したとき，敵 (A1, A2)は強い 攻撃に成功した，ということにしよう． このとき，敵 (A1, A2)のアドバンテージを

Advsauth(A1, A2) = Pr((A1, A2)が強い攻撃に成功)

と定義する．更に Advsauth_{= max}

(A1,A2)

Advsauth_(A

1, A2)

と置き，強信頼性を以下のように定義する．

［定義 3.3］ Advsauth_{が negligible であるとき，認証可能 SSE}

方式は強信頼性を満たすと定義する． 認証可能 SSE 方式は，強信頼性を満たせば信頼性も満たすこ とになる．強信頼性の意義を理解するために，信頼性を満たす 認証可能 SSE 方式に対して，強信頼性を破る攻撃者 A を考えよ う．A は，クライアントがキーワード ˜wiに対応する暗号文とし てサーバに登録した (C( ˜wi), Tagi)と異なる (C( ˜wi)′, Tagi)′

をクライアントに受理させる．このとき，認証可能 SSE 方式が 信頼性を満たすため，D( ˜wi)′ = D( ˜wi)であり，クライアント が復元するファイルは同一となる．すなわち，A の攻撃は現実 的には意味がないが，後述する UC 安全性（定理 6.1）を議論 する上で必要になる．すなわち，認証可能 SSE 方式を上位シス テムの構成要素として利用するためには信頼性よりも強い安全 性が必要となる．

4.

認証可能

SSE

方式の構成

本章では，2. 2 で示した SSE 方式を認証可能 SSE 方式に拡 張し，それがプライバシーと強信頼性を満たすことを証明する．

4. 1

方

式

2. 2で示した SSE 方式に対し以下の変更を加えることによ り，認証可能 SSE 方式が得られる．（図 8 参照．）ただし，MAC を出力が 128bit の擬似ランダム関数とする．（擬似ランダム関数 は，鍵を固定すれば確定的な関数である．） （格納フェーズ）クライアントの動作に，以下の変更を加える （ 1 ） (k, k′, ke)に加え，MAC の秘密鍵 ktをランダムに選ぶ． （ 2 ） 2. 2 の方式と同様に，共通鍵暗号方式 SKE を使って ファイルの暗号文の集合C を計算する． （ 3 ） T ag1, T ag2を以下のように計算する． T ag1 = MACkt(t(w1), C(w1)) T ag2 = MACkt(t(w2), C(w2)) （ 4 ） I を以下のように変更する． I =   fk(wσ(1)), indexσ(1), T agσ(1) fk(wσ(2)), indexσ(2), T agσ(2)   （ 5 ） (C, I) をサーバに格納し，鍵 K = (k, k′, ke, kt)を秘 密に保持する． （検索フェーズ） （ 1 ） 検索キーワードが w1のとき，クライアントは，2. 2 の方式と同様に t(w1)を計算し，サーバに送る． （ 2 ） サーバは，2. 2 の方式と同様に C(w1) = (C1, C3, C5) を求める．更に，T ag1も求め，(C(w1), T ag1)をクライ アントに返す． （ 3 ） クライアントは，秘密鍵 ktを使い， T ag1= MACkt(t(w1), C(w1)) が 成 り 立 つ か ど う か チェック す る ．成 り 立 て ば (C1, C3, C5)を復号し， D(w1) = (D1, D3, D5) を出力する．成り立たなければ，reject を出力する．

4. 2

プライバシー

共通鍵暗号方式 SKE に対し，left-or-right (LOR) 安全性と

図 8 認証可能 SSE 方式の構成

いう概念が知られている（23）_{．SKE = (E, E}−1_{)が LOR 安全}

であるとき，Eke(m)と Eke(0|m|)は識別不可能となる．すな わち，どのような確率的多項式時間アルゴリズム B に対しても， | Pr[B(Eke(m)) = 1]− Pr[B(Eke(0 |m|_{)) = 1]|} が negligible になる．ただし，|m| は平文 m の長さを表し， 0|m|は長さ|m| の (0 . . . 0) を表す．AES 暗号が擬似ランダム 置換（20），（21）_{であるという仮定の下，（AES 暗号に基づく）カウ} ンタモード（20），（21）_{は LOR 安全である}（23）_{．（付録参照．）}

SKE = (E, E−1)が LOR 安全であるとき，4. 1 で示した 認証可能 SSE 方式 π はプライバシーを満たすことを示そう．ま ず，現実ゲームにおけるチャレンジャーの動作は，π によって自 動的に規定されることに注意しよう．次に，シミュレーション ゲームにおけるシミュレータ S を以下のように構成する． （格納フェーズ） （ 1 ） S は，チャレンジャーから，|D1|, · · · , |D5| 及びキー ワード数 m = 2 を受け取る． （ 2 ） S は， C′1= Eke(0 |D1|_{), . . . , C}′ 5= Eke(0 |D5|₎ を計算し，C′= (C₁′, . . . , C₅′)と置く． （ 3 ） S は，行列I′の各要素をランダムに選び， I′₌   label′1, index′1 T ag1′ label′2, index′2 T ag2′   と置く． （ 4 ） S は，(C′,I′)をチャンレジャーに返す． （検索フェーズ）S は，集合{1, 2} 上の置換 ϕ をランダムに選 ぶ．クライアントの検索キーワードが w1のとき， （ 1 ） S は，チャレンジャーから，List(w1) = (1, 3, 5)を受 け取る． （ 2 ） S は， t′(w1) = (labelϕ(1), index′ϕ(1)⊕ (10101)) をチャレンジャーに返す． このとき，どのような distinguisher B に対しても|Preal− Psim| = negligible となることの略証を示そう． 以下のようなゲームの系列 Game0, . . . , Game4を考える．ただ し，Game0を 3.1 で示した現実ゲームとする．また，Gameiにお

けるチャンレンジャーの動作を微修正した環境を Gamei+1とす

る．プライバシーの証明では，Game0から修正を繰り返し，3.1

に示したシミュレーションゲームに対応する Game4を構成する．

このとき，各ゲームの修正が B の動作に与える影響が小さけれ ば，Prealと Psimは近い値となり|Preal− Psim| = negligible

が示される．

Gameiにおいて distinguisher（識別者）B が b = 1 を出力す

る確率を piとする．

(Game1) Game0における各 Ci= Eke(Di)を Eke(0|Di|)で置 き換える．SKE は LOR 安全なので，|p1− p0| = negligible

である．

(Game2) Game1における fkの出力を全て乱数で置き換える．

fは擬似ランダム関数なので，|p2− p1| = negligible である．

(Game3) Game2における gk′の出力を全て乱数で置き換える．

gは擬似ランダム関数なので，|p3− p2| = negligible である．

(Game4) Game3における MACktの出力を全て乱数で置き換え る．MAC は擬似ランダム関数なので，|p4− p3| = negligible で

ある．

ここで，Game4とシミュレーションゲームは等価であることが

容易に分かる．よって，Psim= p4である．また，Preal= p0

なので，どのような distinguisher B に対しても

|Preal− Psim| = |p0− p4| = negligible (3)

となり，プライバシーが成り立つことが示された．

4. 3

強 信 頼 性

4. 1で示した認証可能 SSE 方式は強信頼性を満たすことを背 理法で証明しよう．すなわち，認証可能 SSE 方式が強信頼性を 満たさないとすると矛盾が生じることを示す． 認証可能 SSE 方式が強信頼性を満たさないとすると，3.2 で 示した強い攻撃に非 negligible な確率で成功する敵 (A1, A2)が 存在する．このとき，以下のいずれかが非 negligible な確率で 起こる． Case 1. クライアントが (C(w1)′, T ag1′) |= (C(w1), T ag1) となるような (C(w1)′, T ag1′)を accept する． Case 2. クライアントが (C(w2)′, T ag2′) |= (C(w2), T ag2) となるような (C(w2)′, T ag2′)を accept する． ここで，C(w1)′= C(w1)かつ T ag1′ |= T ag1の場合，MACkt が確定的アルゴリズムであるため，クライアントは明らかに (C(w1)′, T ag′1) を reject する．よって，以下のいずれかが非 negligibleな確率で起こっていることになる． Case 1’. クライアントが C(w1)′ |= C(w1) となるような (C(w1)′, T ag1′)を accept する． Case 2’. クライアントが C(w2)′ |= C(w2) となるような (C(w2)′, T ag2′)を accept する． このとき，MAC とランダム関数を非 negligible な有意差で識 別可能な distinguisher B を構成できることを示す．B は，以 下のようにクライアントの役割を果たし，(A1, A2)を走らせる． ただし，O によって MACktオラクルまたはランダム関数オラク ルを表す（図 9）． （格納フェーズ） （ 1 ） B は kt 以 外 の 鍵 (k, k′, ke) を ラ ン ダ ム に 生 成 し ， T ag1, T ag2以外の部分を方式通りに生成する． （ 2 ） i = 1, 2 について，B は (t(wi), C(wi))をオラクルO に質問し，T agiを受け取る．この T ag1, T ag2を利用し てI を構成する． （検索フェーズ） （ 1 ） B が t(w1)を A2に送り，A2が (C(w1)′ |= C(w1), T ag′1) を返してきた場合，B は (t(w1), C(w1)′)をオラクルO に質問して T ag∗1=O(t(w1), C(w1)′)を受け取り， T ag₁′ = T ag∗₁=O(t(w1), C(w1)′) (4) かどうかチェックする． （ 2 ） B が t(w2)を A2に送り，A2が (C(w2)′ |= C(w2), T ag′2) を返してきた場合，B は (t(w2), C(w2)′)をオラクルO に質問して T ag∗2=O(t(w2), C(w2)′)を受け取り， T ag₂′ = T ag∗₂=O(t(w2), C(w2)′) (5) かどうかチェックする． 最後に，B は，式 (4) または式 (5) が成り立ったら 1 を出力す る．そうでなければ，0 を出力する． B は ，格 納 フェー ズ に お い て ，(t(w1), C(w1)′) あ る い は (t(w2), C(w2)′)をオラクルO に質問していないことに注意 されたい． 図 9 強信頼性の証明（文献 (6) より引用）

O が MACktオラクルの場合，筆者らの仮定から，式 (4) また は式 (5) が非 negligible な確率で成立する．一方，O がランダ ム関数の場合，式 (4) または式 (5) が成り立つ確率は 2/2128_で ある．よって，B は非 neglligible な有意差で MAC とランダム関 数を識別できる．これは，MAC が擬似ランダム関数という仮定 に反する．ゆえに，強信頼性が成り立つ．

5. SSE

方式の

UC

安全性

本章では，認証可能 SSE 方式の UC 安全性について説明す る（5），（6）_{．一般に，プロトコル一つ一つは単体で見ると安全で} あっても，複雑に組み合わせると安全であるとは限らなくなっ てしまう．Canetti は，この問題に対し UC 安全性 (Universal Composability,汎用結合安全性）という概念を導入し，あるプ ロトコルが UC 安全であれば，それがどんな複雑なプロトコル の中に部品として組み込まれたとしても，その安全性が保たれ ることを証明した（24）_． UCの枠組みにおいては，プロトコル π に対し，その現実世 界と理想世界が定式化され，それら二つの世界が識別不可能性 であるとき，プロトコル π は UC 安全であると言われる． 現実世界では，環境Z がクライアントに指示を与え，プロト コルの実行を指示する．クライアントは，サーバと実際のプロ トコルを走らせる．更に，Z は現実世界の敵 A に指示を与え， 応答を受け取る（図 10）． 理想世界では，プロトコルは要求機能を理想的に実現する理 想機能FSSEに置き換えられる．理想世界では，Z はダミーク ライアントに指示を与え，プロトコルの実行を指示する．ダミー クライアントは，プロトコルそのものは実行せず，理想機能と の間で要求機能（ファイルの登録，検索など）を実現する．ま た，Z は理想世界の敵 S に指示を与え，応答を受け取る．ここ で，S はプロトコルに実際に攻撃を行う主体ではなく，理想機 能から得られる情報（例えば最小漏えい情報量）に基づいて現 実世界の攻撃者 A をシミュレートし，A がZ に送った情報も どきの応答をZ に回答する（図 13）． 環境Z は，現実世界と理想世界の識別を試みる．もしも Z が 二つの世界を識別することができなければ，現実のプロトコル が理想機能と識別できないこととなり，現実のプロトコルが要 求機能を理想的に実現していると言える． なお，どちらの世界においても，Z がクライアントへ外部入 力を与え，その外部への出力を受け取る．

5. 1

現 実 世 界

認証可能 SSE 方式の現実世界は，環境Z，クライアント，サー バ，敵 A の四つの確率的多項式時間アルゴリズムを用いて以下 のようにモデル化される（図 10）． （格納フェーズ） （ 1 ） 環境Z は，クライアントへ (D, W, Index) を送る． （ 2 ） クライアントは，秘密鍵 K をランダムに生成し，(C, I) を計算し，(C, I) をサーバに送る． 図 10 認証可能 SSE 方式の現実世界（文献 (6) より 引用） （検索フェーズ）以下を i = 1,· · · , q について実行． （ 1 ） 環境Z は，検索キーワード ˜wiをクライアントへ送る． （ 2 ） クライアントは，トラップドア情報 t( ˜wi)をサーバへ 送る． （ 3 ） サーバは，(C( ˜wi), gT agi)をクライアントに返す． （ 4 ） クライアントは，D( ˜wi)または reject をZ へ送る． 敵は，サーバを乗っ取り自由にコントロールすることができ る．更に，環境Z は敵 A と自由に通信できる．最後に，Z は 1または 0 を出力する．

5. 2

理 想 世 界

認証可能 SSE 方式の理想世界は，環境Z，ダミークライアン ト，敵 S，及び理想機能FSSEの四つの確率的多項式時間アル ゴリズムを用いて以下のようにモデル化される（5）_． （格納フェーズ）（図 11） （ 1 ） 環境Z は，ダミークライアントへ (D, W, Index) を 送る． （ 2 ） ダ ミ ー ク ラ イ ア ン ト は ，理 想 機 能 FSSE へ (D, W, Index) を送る． （ 3 ） FSSEは，最小漏えい情報であるファイル数 n，キー ワード数 m，及び各ファイルのサイズ|D1|, · · · , |Dn| を 理想世界の敵 S に送る． （検索フェーズ）以下を i = 1,· · · , q について実行．（図 12） （ 1 ） 環境Z は，ダミークライアントへ検索キーワード ˜wi を送る． （ 2 ） ダミークライアントは，理想機能FSSEへ ˜wiを送る． （ 3 ） FSSEは，最小漏えい情報である List( ˜wi)を理想世界 の敵 S に送る．

（ 4 ） S は，answer=accept or reject をFSSEに返す．

（ 5 ） FSSEは， Xi=    D( ˜wi) if answer = accept

reject if answer = reject をダミークライアントに送る．

（ 6 ） ダミークライアントは，XiをZ に送る．

更に，環境Z は敵 S と自由に通信できる．（図 13 参照．）最後

に，Z は 1 または 0 を出力する． ここで，以下のことに注意されたい．

図 11 理想世界：格納フェーズ（文献 (6) より引用） 図 12 理想世界：検索フェーズ（文献 (6) より引用） 図 13 理想世界の敵（文献 (6) より引用） • 理想世界の敵 S には，最小漏えい情報しか漏れていない． • ダミークライアントは，D( ˜wi)または reject を受け取る． これは，D( ˜wi)′ |= D( ˜wi)となる D( ˜wi)′は受け取らない，とい うことを意味している． ゆえに，この世界は理想世界である．

5. 3 UC

安全性

現実世界において環境Z が 1 を出力する確率を P0，理想世 界においてZ が 1 を出力する確率を P1とし， AdvucS(Z, A) = |P0− P1| と定義する．ただし，A は現実世界における敵であり，S は理 想世界における敵である． このとき，任意の A に対し，ある S が存在し，任意のZ に 対し，Advuc S(Z, A) が negligible となるとき，認証可能 SSE 方 式 π は UC 安全であると定義する． 上記の条件は，Z が図 10 と図 13 を区別できない，というこ とを意味している．なので，図 10 は図 13 と同程度に安全であ る，ということになる． ここで，以下の UC 結合定理が成り立つ（24）_{．認証可能 SSE} 方式 π を部品として使うプロトコルを Σ，Σ において π を理想 機能FSSEに置き換えたプロトコルを Σ′とする．このとき，π が UC 安全であれば，Σ は Σ′と同程度に安全である． ここで，同程度に安全とは，Σ に対する任意の敵 ˜Aに対し， Σ′に対するある敵 ˜S が存在し，どのような環境Z も Σ と Σ′ を区別不可能，という意味である．

6.

等 価 性

［定理 6.1］（6）_{認証可能 SSE 方式 π について，以下が成り立つ．} （ 1 ） π が UC 安全なら，プライバシー及び信頼性を満たす． （ 2 ） π がプライバシー及び強信頼性を満たすなら，UC 安 全である． 4. 1で示した認証可能 SSE 方式はプライバシー及び強信頼性 を満たすので，以下の系が得られる． ［系 6.1］ 4. 1 で示した認証可能 SSE 方式は，UC 安全である．

6. 1

定理

6.1 (1)

の証明

（6） （プライバシーの証明）まず，図 10 で示した UC の現実世界に おいて，クライアントからサーバへの各メッセージ Y を環境 Z に転送するような敵 A0を考える．（格納フェーズにおいては Y = (I, C) であり，検索フェーズにおいては Y = t( ˜wi)であ る．）この現実世界において，Z を distinguisher，（クライアン ト，サーバ，A）の組をチャレンジャーと考えれば，これはプラ イバシーの現実ゲームとみなせる（図 14 参照．）すなわち，こ の UC の現実世界は，プライバシーの現実ゲームと同じである． 一方，π は UC 安全と仮定しているので，上記の現実世界の 敵 A0と同様に動作する理想世界の敵 S が存在する．（図 15 参 照．）この理想世界において，Z を distinguisher，S をシミュ レータ，（ダミークライアント，FSSE）のペアをチャレンジャー と考えれば，これはプライバシーのシミュレーションゲームと みなせる．（図 15 と図 6，図 7 を比較せよ．）すなわち，この UC の理想世界は，プライバシーのシミュレーションゲームと同じ である． 以上から，

Advpriv_S (Z) = Advuc_S(Z, A0)

が成り立つ．したがって， Advpriv_S = max

Z Adv priv S (Z) = max Z Adv uc S(Z, A0) = negligible 図 14 現実世界＝「プライバシーの現実ゲーム」（文献 (6)より引用）

図 15 理想世界＝「プライバシーのシミュレーション ゲーム」（文献 (6) より引用） となる．ゆえに，π はプライバシーを満たす． （信頼性の証明）3. 2 で定義した攻撃を行う任意の敵 (A1, A2) に対し，(Z, A) = (A1, A2)となるような環境Z 及び現実世界 の敵 A を考える．このとき，π は UC 安全なので，ある理想世 界の敵 S が存在し， Advuc_S(Z, A) = |P0− P1| = negligible となる． また，(Z, A) = (A1, A2)が攻撃に成功したとき，Z は 1 を 出力し，そうでないとき 0 を出力するものとする．図 12 から 分かるように，理想世界においてZ は，検索キーワードが wi のとき，D(wi)′ |= D(wi)となる D(wi)′を受け取らない．した がって， P1 = Pr(Zが 1 を出力) = 0 となる．これから，

Advauth(A1, A2) = P0= negligible

となる．したがって，π は信頼性を満たす．

6. 2

定理

6.1 (2)

の証明

（6）

証 明 の 考 え 方 を 示 そ う．以 下 の よ う な ゲ ー ム の 系 列 Game0, . . . , Game4 を考え ，Gamei に おい てZ が 1 を出力す

る確率を piとする．ただし，現実世界を Game0とする． (Game1) 敵 A がサーバに対し， (C(w)′, T ag′) |= (C(w), T ag) なる (C(w)′, T ag′)をクライアントに返すよう指示した場合， サーバは reject をクライアントに返すように Game0を修正す る．このとき， |p0− p1| <= Advsauth を証明できる． (Game2) クライアントを，クライアント１，クライアント２に 分割する．ただし，サーバへの送信部分はクライアント２が受 け持ち，サーバからの受信部分及びZ への送信部分はクライア ント１が受け持つ（図 16）．このとき， 図 16 Game 2（文献 (6) より引用） 図 17 Game 3（文献 (6) より引用） p2= p1 となる． (Game3) クライアント２を，プライバシーのシミュレーション ゲームにおけるチャレンジャーとシミュレータ S0の組に置き 換え，S0の出力をサーバへ送るように Game2を修正する（図 17）．このとき， |p2− p3| <= AdvprivS0 を証明できる Game3において，（クライアント１，クライアント２）の組は FSSE と同じ動作をしていることが分かる．更に，(A, サーバ ，S0)の組を理想世界における敵 S とみなすことができる（図 18参照）．ゆえに， Advuc_S (Z, A) = |p0− p3| <

= Advsauth+ AdvprivS0

が得られる．これから，定理 6.1 (2) が成り立つことになる．詳 しくは，文献（6）を参照されたい．

7.

お わ り に

単一キーワード検索 SSE 方式の原理について，その安全性の 定義及び構成法に関する最近の研究成果について紹介した． キーワード w について検索したいとき，クライアントはト ラップドア情報 t(w) をサーバに送る．2. 2 で示した方式におい ては，この t(w) のサイズは O(n) である．ただし，n はファイ ル数．筆者の知る限り，ランダムオラクルを使わない場合，t(w) のサイズが O(n) より小さくなる方式は知られていない．よっ て，そのような方式の開発が今後の課題であろう．複数キーワー

図 18 理想世界（文献 (6) より引用） ド検索 SSE 方式についても，同様のことが言える． 一方，動的 SSE 方式においては，更新したファイルの最新性 をいかに保証するかが問題となる．これは，Merkle ハッシュ木 や accumulator を使えば一応解決できるが（7）_{，より効率の良い} 方法の開発も今後の課題である． UC安全性の定義は難解であるが，認証可能 SSE 方式に限っ ては，上述したようにかなり容易に理解できるようになる．本 稿を，SSE 方式のみならず UC 安全性の入門としても活用して 頂けたなら，望外の幸せである． 謝辞 本稿の原稿を丁寧に読み，有益な御助言をして頂いた閲 読者の方々に感謝致します． 文 献

（1） D.Song, D.Wagner, and A.Perrig,“Practical techniques for searches on encrypted Data,” IEEE Symposium on Security and Privacy 2000, pp.44–55, 2000.

（2） R.Curtmola, J.A. Garay, S.Kamara, R.Ostrovsky, “ Searchable symmetric encryption: improved defini-tions and efficient construcdefini-tions,”ACM Conference on Computer and Communications Security 2006, pp.79– 88, 2006.

（3） Y.Chang and M.Mitzenmacher, “ Privacy preserving keyword searches on remote encrypted data,” ACNS 2005, pp.442–455, 2005.

（4） E.-J. Goh,“Secure Indexes,”Cryptology ePrint Archive, Report 2003/216, 2003. http://eprint.iacr.org/ （5） K. Kurosawa, Y. Ohtaki,“ UC-secure searchable

sym-metric encryption,” Financial Cryptography 2012, pp.285–298.

（6） Full version of (16), “ How to construct UC-secure searchable symmetric encryption scheme,”Cryptology ePrint Archive: Report 2015/251, 2015.

（7） K. Kurosawa, Y. Ohtaki,“ How to update documents verifiably in searchable symmetric encryption,”CANS 2013, pp.309–328,2013.

（8） S. Kamara and C. Papamanthou,“Parallel and dynamic searchable symmetric encryption,”FC 2013, pp.258– 274, 2013.

（9） S. Kamara, C. Papamanthou, and T. Roeder,“Dynamic searchable symmetric encryption,”ACM Conference on Computer and Communications Security 2012, pp.965-976, 2012.

（10） L. Ballard, S. Kamara, and F. Monrose, “ Achieving efficient conjunctive keyword searches over encrypted Data. ”ICICS 2005, pp.414-426, 2005.

（11） J. W. Byun, D. H. Lee, and J. Lim,“ Efficient conjunc-tive keyword search on encrypted data storage system,” EuroPKI, pp.184–196, 2006.

（12） D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, and M. Steiner,“ Highly-scalable searchable symmetric encryption with support for boolean queries,”CRYPTO (1) 2013, pp.353–373, 2013.

（13） P. Golle, J. Staddon, and B. R. Waters,“ Secure con-junctive keyword search over encrypted data,” ACNS 2004, pp.31-45, 2004.

（14） K. Kurosawa: “ Garbled searchable symmetric encryp-tion,” Financial Cryptography 2014, pp.234-251. （15） P. Wang, H. Wang, and J. Pieprzyk,“ Keyword

field-free conjunctive keyword searches on encrypted data and extension for dynamic groups,” CANS 2008, pp.178-195, 2008.

（16） 佐々木圭佑，黒澤 馨，Garbled searchable symmetric en-cryption 方式の計算機シミュレーション，信学技報，ISEC2014-51, pp.27-34，Sept. 2014.

（17） D. Cash and S. Tessaro, “ The locality of searchable symmetric encryption,” EUROCRYPT 2014, pp.351-368, 2014.

（18） Privacy with Security. Technical report, DARPA Information Science and Technology Study Group, Dec. 2002. http://www.cs.berkeley.edu/-tygar/papers/ ISAT-final-briefing.pdf.

（19） K. Kurosawa, “ How to keyword search securely in cloud storage service,”(invited talk) ICISC 2014, http://kurosawa.cis.ibaraki.ac.jp/KuroIwa.html （20） 黒澤 馨，現代暗号への招待，サイエンス社，2010.

（21） 黒澤 馨，尾形わかは，現代暗号の基礎数理，電子情報通信学 会（編）, コロナ社, 2004.

（22） Full version of (7), Cryptology ePrint Archive, Report 2006/210, 2006. http://eprint.iacr.org/

（23） M. Bellare, A. Desai, E. Jokipii, and P. Rogaway,“ A concrete security treatment of symmetric encryption,” FOCS 1997, pp.394–403, 1997.

（24） R. Canetti, “ Universally composable security: A new paradigm for cryptographic protocols, ”Cryp-tology ePrint Archive, Report 2000/067, 2013. http://eprint.iacr.org/

（25） N. Baric and B. Pfitzmann,“ Collision-free accumula-tors and fail-stop signature schemes without trees, ” In Advances in Cryptology: Proc. EUROCRYPT, vol. 1233 of LNCS, pp.480–494. Springer-Verlag, 1997.

付

録

1. カウンタモード

米国標準暗号である AES 暗号は，128bit の平文 m を 128bit

の暗号文 c = AESk(m)に暗号化する．ただし，k は鍵である． 更に，128bit より長い平文を暗号化する方法として，カウンタ モードが知られている． カウンタモードにおいては，カウンタの役割を果たす変数 ctr を利用し，平文 M = (m1, . . . , mt)を以下のように暗号化する． まず， c1 = m1⊕ AESk(ctr + 1) . . . ct = mt⊕ AESk(ctr + t) を計算する．次に，暗号文を C = Ek(M ) = (ctr, c1, . . . , ct) とする．その後，ctr を ctr + t に更新する． 2. LOR安全性 カウンタモードなどの共通鍵暗号方式に対し，Left-or-Right

図 A· 1 カウンタモード（文献 (20) より引用） 安全性 (LOR 安全性）という概念が知られている（23）_．まず， left関数，right 関数を left(x0, x1) = x0 right(x0, x1) = x1 と定義する．このとき，どのような確率的多項式時間の敵 A に 対しても，

| Pr(AEk(left(·,·))_{= 1)}− Pr(AEk(right(·,·))_{= 1)}|

が negligible となるとき，共通鍵暗号方式 (E, E−1)は LOR 安 全であると呼ばれる．ただし，A は，|m0| = |m1| となる平文 のペア (m0, m1)を何回でもオラクルに質問できる． 上記のカウンタモードは，AES 暗号が擬似ランダム置換であ るという仮定の下，LOR 安全である（23）_． 図 A· 2 LOR 安全性 （ISEC 研究会提案，平成 27 年 5 月 7 日受付） 黒澤 馨（正員：フェロー） 1977東工大・工・電子卒. 1982 同大学院博士課程 了. 工博. 同年 同大・工学部助手.   1985 同大・院 総合理工学研究科講師. 1989 同大助教授. 1997 同 大教授. 2001 から茨城大・工・教授. 現代暗号理論 の研究に従事. 電子情報通信学会論文賞 (1980)，本 会篠原記念学術奨励賞 (1984)，電気通信普及財団テ レコムシステム技術賞 (2006)，本会業績賞 (2007)， 情報セキュリティ文化賞 (2009）各受賞．著書「現代暗号への招待」「現代 暗号の基礎数理」など．