検索可能暗号におけるブルームフィルタを応用した検索方式の提案

全文

(1)Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 情報処理学会研究報告 IPSJ SIG Technical Report. 検索可能暗号におけるブルームフィルタを応用した検索方式の提案佐保航輝1. 油田健太郎1. 山場久昭2. 久保田真一郎2. 朴美娘3. 岡崎直宣2. 概要：近年，クラウドストレージサービスが一般のユーザのみでなく企業でも利用されている．クラウドストレージサービスを利用することによってインターネットに接続されている環境であればどこでもデータの利活用が可能になったが，安全性が課題とされる．サーバ側の不正閲覧等を防ぐために，暗号化したデータを復号することなく検索可能とした検索可能暗号が注目されている．その手法の一つとしてブルームフィルタを用いることでより検索自由度を高めようとした方式があるが，一度登録したキーワードを削除することができず，削除する際には再構成する必要があった．そこで本研究では, ブルームフィルタを拡張したカウンティングフィルタを用いることでキーワードの削除を可能とするより柔軟な手法を提案する．キーワード：検索可能暗号，ブルームフィルタ，カウンティングフィルタ. 1. はじめに近年，クラウドコンピューティング環境を利用してデー. ఍♫ 䝣䜷䝹䝎䛾䜰䝑䝥䝻䞊䝗. እฟඛ 䝯䞊䝹䛾㏦ಙ. タを保存するクラウドストレージサービス (図 1) が普及している．これにより必要なデータなどをインターネット上から利用することが可能になり，インターネットさえ利. 䜽䝷䜴䝗䝃䞊䝡䝇. 用できればどこからでもアクセスが可能であるため一般のユーザのみでなく企業などでも利用されている．しかし，どこでも利用できるという利便性がある反面，クラウド上に保存したデータが漏えいする危険性を考慮しなければならず，重要なデータなどに対しては暗号化がさ. 㜀ぴ. れていた．暗号化されたデータを検索する際には一度デー. ⮬Ꮿ. タの復号が必要であり，その鍵はサーバ側が保持する．そのため，管理者による不正閲覧が可能なことやコンピュー. 図 1 クラウドサービスの概要. タウイルスに対して弱いことが問題とされてきた．この問題を解決するため，暗号化したデータを復号することなく検索できる検索可能暗号という技術がある [1]．データそのものだけでなく，検索キーワードさえも暗号化したまま検索可能であるため，安全なデータの利活用ができるとして注目されている．検索可能暗号の検索方式の一つに，時間的, 空間的効率の. 良いブルームフィルタを用いた方式がある．一文字単位で登録することで部分一致検索も可能とした検索自由度の高い方式 [2] や，複数のデータを単一のブルームフィルタで管理する手法 [3] などが提案されている．しかし，これらの方式ではブルームフィルタの構造上，一度登録したキーワードを削除することができない．そこで本研究では，ブルームフィルタをキーワードの削. 1. 2. 3. 大分工業高等専門学校 Oita National College of Technology 宮崎大学 University of Miyazaki 神奈川工科大学 Kanagawa Institute of Technology. ⓒ 2015 Information Processing Society of Japan. 除に対応させるよう拡張したカウンティングフィルタを用いて，キーワードの削除を可能としたより柔軟性の高い方式を検討する．. 1.

(2) Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 情報処理学会研究報告 IPSJ SIG Technical Report. マン符号を用いた方式 [8] やキーワードから数ビットの情. 2. 検索可能暗号. 報漏れを許容することで検索の高速化を図る方式 [9] 等が. 従来の方式では，暗号化されたデータを検索する場合，暗号化されたデータをその都度復号してキーワードを含むか否かを調べる必要があった．この方法では暗号化により保護された情報を復元する鍵をサーバ側が保持することになり，管理者による不正閲覧が可能なことやコンピュータ. ある．共通鍵暗号方式の一つにブルームフィルタを用いた手法 [2], [3], [10] がある．時間的，空間的効率の良いブルームフィルタを用いることによって高速化，低コスト化を図っている．. 3. ブルームフィルタ. ウィルスにも弱いことが懸念される．これを解決する手法として検索可能暗号 (図 2) という技術が生まれた．データを暗号化したまま検索する暗号技術のことであり，検索対象のデータのみでなく検索キーワードも暗号化したまま処理できるため，クラウド上のデータの安全な利活用に役立つ技術として注目されている．検索可能暗号には大きく分けて共通鍵暗号方式と公開鍵暗号方式の 2 つがある．公開鍵暗号方式の中では関数型暗号 [4] や ID ベース暗号を用いたもの [5], [6] などが一般的. ブルームフィルタ (Bloom Filter) は 1970 年に Bloom が考案した確率的データ構造 [11] であり，キーワードが集合に含まれるかをチェックすることができる．集合をビット列で表現 (図 3) するため，非常に空間効率の良いデータ構造である．ブルームフィルタの構成手順は以下のとおりである．（1） M ビットの配列，K 個のハッシュ関数，N 個のキー. に挙げられる．また，それらの鍵を用いず秘密分散方式を用いる方式も提案されている [7].. （2）配列を初期化する．. 共通鍵暗号方式は以下のプロセスで行う．. (1). （3）キーワードを K 個のハッシュ関数に入力し，その. データの所有者と検索を行うユーザとの間で，事前に鍵の共有を行っておく．. (2). ワードを用意する．. ハッシュ値に対応する配列のビットをたてる．（4） (3) を N 回繰り返す．. データの所有者は，暗号化したデータの内容を表す. 䜻䞊䝽䞊䝗΂ŬĞǇ͕ƉŚŽŶĞ΃ 䝝䝑䝅䝳㛵ᩘ΂,ϭ͕,Ϯ΃. キーワードを指定する．. (3). 登録キーワードのトラップドアを計算する．. (4). 暗号化したデータと登録キーワードのトラップドア. ,ϭ;ŬĞǇͿсϮ. ,Ϯ;ŬĞǇͿсϵ. ,ϭ;ƉŚŽŶĞͿсϰ ,Ϯ;ƉŚŽŶĞͿсϱ. をサーバに送信する．. (5). サーバは暗号化したデータと登録キーワードのトラップドアをデータベースに登録する．. (6). 検索を行うユーザは，検索キーワードのトラップド. Ϭ. Ϭ. ϭ. Ϭ. ϭ. ϭ. Ϭ. Ϭ. Ϭ. ϭ. ΀Ϭ΁. ΀ϭ΁. ΀Ϯ΁. ΀ϯ΁. ΀ϰ΁. ΀ϱ΁. ΀ϲ΁. ΀ϳ΁. ΀ϴ΁. ΀ϵ΁. 䝤䝹䞊䝮䝣䜱䝹䝍. 図 3 ブルームフィルタの登録. アを計算する．. (7). 検索キーワードのトラップドアをサーバに送信する．. (8). サーバは，データベースから検索キーワードのトラップドアにヒットするデータを検索し，検索を行ったユーザに結果を返信する．. キーワードを検索する際には，検索キーワードのハッシュ値を作成されたブルームフィルタと比較して判定する．ハッシュ値に対応するビットが全て 1 ならキーワードは存在する (true) と，一つでも 0 があればキーワードは存在しない (false) と判定する (図 4)．. 䝕䞊䝍䝧䞊䝇. 䝕䞊䝍. 䝖䝷䝑䝥䝗䜰. 䜻䞊䝽䞊䝗΂ŬĞǇ͕ƉĞŶ΃ 䝝䝑䝅䝳㛵ᩘ΂,ϭ͕,Ϯ΃. ᬯྕ໬䝕䞊䝍. 䝃䞊䝞. ᬯྕ໬ 䜻䞊䝽䞊䝗. dƌĂƉĚŽŽƌ ,ϭ;ŬĞǇͿсϮ. ,Ϯ;ŬĞǇͿсϵ. ,ϭ;ƉĞŶͿсϱ. ,Ϯ;ƉĞŶͿсϳ. 䜻䞊䝽䞊䝗. ᳨⣴䝍䜾. ᳨⣴⤖ᯝ. ᥦ౪⪅. ᳨⣴⪅. 㘽. Ϭ. Ϭ. ϭ. Ϭ. ϭ. ϭ. Ϭ. Ϭ. Ϭ. ϭ. ΀Ϭ΁. ΀ϭ΁. ΀Ϯ΁. ΀ϯ΁. ΀ϰ΁. ΀ϱ΁. ΀ϲ΁. ΀ϳ΁. ΀ϴ΁. ΀ϵ΁. 䝤䝹䞊䝮䝣䜱䝹䝍. 図 2 検索可能暗号 (共通鍵暗号方式). 検索可能暗号についての研究は，実用化を視野に入れた高速化を目的とするものが多い．その一例として，ハフ. ⓒ 2015 Information Processing Society of Japan. ŬĞǇсƚƌƵĞ͖ƉĞŶсĨĂůƐĞ 図 4 ブルームフィルタの検索. 2.

(3) Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 情報処理学会研究報告 IPSJ SIG Technical Report. しかし，ブルームフィルタは一度登録したキーワードを. されることはない．. 削除することができない．キーワードのハッシュ値に対応. ブルームフィルタを用いた従来の手法として, 一文字単. するビットを全て 0 にした場合，他のキーワードでも同じ. 位でブルームフィルタに登録するより検索自由度の高い検. ビットが 1 になっていた可能性があるためである．その場. 索可能暗号方式が提案されている (図 6)．キーワード単位. 合，本来登録されてあるキーワードを登録されていないと. で登録する方式では完全一致検索のみが可能であったが，. 判定してしまう偽陰性が発生する．偽陽性の場合は最終的. この方式ではそれ以外の部分一致検索等も可能になる．. に目的のデータ等を検索することができるが偽陰性の場. 䜻䞊䝽䞊䝗΂ŬĞǇ΃. 合は検索不可能になる．そのため，ブルームフィルタではキーワードの削除ができない．. ŬĞǇ. Ŭ. Ğ. Ǉ. 3.1 偽陽性偽陽性 (False Positive) とは，実際には登録していないキーワードを検索した際に誤ってそのキーワードが存在すると返してしまうことであり，ハッシュ値の衝突によって発生する (図 5)．ブルームフィルタではこの偽陽性を許. 䝤䝹䞊䝮䝣䜱䝹䝍. 䝤䝹䞊䝮䝣䜱䝹䝍. ŬĞǇсƚƌƵĞ ͍ĞǇ сĨĂůƐĞ. ŬĞǇсƚƌƵĞ ͍ĞǇ сƚƌƵĞ. 容することによって空間効率を上げている．また，無理に図 6. キーワードの削除をしようとしない限り，実際に登録して. 一文字ごとに登録する手法. いるキーワードを存在しないと返す偽陰性は発生しない．偽陽性が発生する確率 (偽陽性率) は配列のビット数，. また，二分木の特性を利用し，サーバ上で単一のブルー. ハッシュ関数の数，キーワードの数によって求めることが. ムフィルタでの管理を可能とする方式も提案された (図 7)．. でき，その式は以下のとおりである．. 従来一つのデータごとにブルームフィルタを登録していたため，データの数に比例してブルームフィルタに必要とな. 1 KN K ) ) M. (1 − (1 −. るデータ量が増加する問題があったが，この方式により複. 式からわかるように，M が大きくなれば偽陽性率は減少し，N が大きくなると偽陽性率は増加する．また，M と. N が分かっている時，偽陽性率を最小とする K の値は次式で求まる．. M ln(2) N. 数のデータを単一のブルームフィルタで管理することが可能となり，サーバ側の管理も容易になった．䝕䞊䝍. 䝤䝹䞊䝮䝣䜱䝹䝍. 䝕䞊䝍. 䜻䞊䝽䞊䝗΂ĐƵƉ΃ 䝝䝑䝅䝳㛵ᩘ΂,ϭ͕,Ϯ΃ ,ϭ;ĐƵƉͿсϮ. 䝕䞊䝍. 䝕䞊䝍. 䝤䝹䞊䝮䝣䜱䝹䝍. 䝤䝹䞊䝮䝣䜱䝹䝍. ,Ϯ;ĐƵƉͿсϱ. 䝕䞊䝍. Ϭ. Ϭ. ϭ. Ϭ. ϭ. ϭ. Ϭ. Ϭ. Ϭ. ϭ. ΀Ϭ΁. ΀ϭ΁. ΀Ϯ΁. ΀ϯ΁. ΀ϰ΁. ΀ϱ΁. ΀ϲ΁. ΀ϳ΁. ΀ϴ΁. ΀ϵ΁. 䝤䝹䞊䝮䝣䜱䝹䝍. ĐƵƉсƚƌƵĞ;ĨĂůƐĞƉŽƐŝƚŝǀĞͿ 図 5. 䝕䞊䝍. 偽陽性. 䝤䝹䞊䝮䝣䜱䝹䝍. 図 7. 複数のファイルを管理する手法. しかし，これらの手法ではブルームフィルタの構造上，一度登録したキーワードの削除ができない．. 4. 提案手法 3.2 検索可能暗号への応用. 4.1 カウンティングフィルタを用いた手法. ブルームフィルタを検索可能暗号に応用させる場合，ト. カウンティングフィルタ (Counting Filter) とはブルー. ラップドアの生成 (キーワードの暗号化) 部にブルームフィ. ムフィルタをキーワードの削除に対応させるよう拡張され. ルタを用いる．共通鍵となるのは K 個のハッシュ関数で. たデータ構造である [12]．本研究ではカウンティングフィ. ある．サーバ側の管理者が登録されてあるブルームフィル. ルタを用いた検索手法を検討する．. タを閲覧したとしても，登録されてあるキーワードが判別. ⓒ 2015 Information Processing Society of Japan. カウンティングフィルタとブルームフィルタの大きな違. 3.

(4) Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 情報処理学会研究報告 IPSJ SIG Technical Report. いは，配列の構成である．ブルームフィルタがビット列で. 4.2 登録時の動作. 構成されるのに対して，カウンティングフィルタは数列で. 本手法ではキーワードを一文字単位で登録する．各文字. 構成される (図 8)．これによってキーワードの追加をイン. にその文字が何文字目であったかという情報を結合して登. クリメント，削除をデクリメントで表現することができる．. 録する．例として，「key」というキーワードを登録すると. カウンティングフィルタの構成手順を以下に示す．. する．key という単語は k,e,y に分解されるが，このまま. 䜻䞊䝽䞊䝗΂ŬĞǇ͕ƉŚŽŶĞ͕ĐƵƉ΃ 䝝䝑䝅䝳㛵ᩘ΂,ϭ͕,Ϯ΃ ,ϭ;ŬĞǇͿсϮ. ,Ϯ;ŬĞǇͿсϵ. になり，key というキーワードが登録されることにはならない．そのため，eyk といった意味のない文字列で検索しても存在すると判定してしまう．これを解決するために，. ,Ϯ;ĐƵƉͿсϱ. ,ϭ;ĐƵƉͿсϮ. 登録してしまうとアルファベットをそのまま登録すること. ,ϭ;ƉŚŽŶĞͿсϰ ,Ϯ;ƉŚŽŶĞͿсϱ. それぞれの文字順の情報を結合して登録した．図 9 を見てわかる様に，一文字目の k は”1k”，二文字目の e は”2e”,. Ϭ. Ϭ. Ϯ. Ϭ. ϭ. Ϯ. Ϭ. Ϭ. Ϭ. ϭ. ΀Ϭ΁. ΀ϭ΁. ΀Ϯ΁. ΀ϯ΁. ΀ϰ΁. ΀ϱ΁. ΀ϲ΁. ΀ϳ΁. ΀ϴ΁. ΀ϵ΁. 䜹䜴䞁䝔䜱䞁䜾䝣䜱䝹䝍. 三文字目の y は”3y”として登録する．こうすることでアルファベットの集合から意味のある文字列の集合になる．. 図 8 カウンティングフィルタ. 䜻䞊䝽䞊䝗΂ŬĞǇ΃ (1). 要素数 M の配列，K 個のハッシュ関数，N 個のキーワードを用意する．. (2). 配列を初期化する．. (3). キーワードを K 個のハッシュ関数に入力し，その. ᩥᏐ㡰 ᩥᏐ. ϭϮϯ ŬĞǇ. ハッシュ値に対応する配列の値をインクリメントする．. (4). (3) を N 回繰り返す．. (5). 削除時は，削除キーワードを K 個のハッシュ関数. ,;ϭŬͿ. ,;ϮĞͿ. ,;ϯǇͿ. に入力し，そのハッシュ値に対応する配列の値をデ. 䜹䜴䞁䝔䜱䞁䜾䝣䜱䝹䝍. クリメントする．図 9. キーワードを検索する際は，基本的にはブルームフィル. 提案手法の登録法式. タと同様であるが，判定の際に 0 か 1 かではなく，0 であるかそうでないかで判定する．カウンティングフィルタを用いた検索手法は第 2 章でも述べた共通鍵暗号方式を用いる．提案手法は以下の通りに行う．. (1). 5. 評価本章では提案手法について評価する．表 1 の環境で実際にカウンティングフィルタを作成し，シミュレーションを行った．. データの所有者と検索を行うユーザとの間で，事前表 1. に鍵の共有を行っておく．. (2). OS. データの所有者は，暗号化したデータの内容を表すキーワードを指定する．. (3). キーワードのハッシュ値を計算し，カウンティング. 開発環境 Windows7. コンパイラ. Visual Studio 2013. CPU. Intel Core i5-2400. メモリ. 4.00GB. フィルタを生成する．. (4). 暗号化したデータとカウンティングフィルタをサーバに送信する．. (5). サーバは暗号化したデータとカウンティングフィルタをデータベースに登録する．. (6). 検索を行うユーザは，検索キーワードのハッシュ値を計算し，検索フィルタを生成する．. (7). 検索フィルタをサーバに送信する．. (8). サーバは，データベースに登録されたカウンティングフィルタと検索フィルタを比較し，一致したデータを検索を行ったユーザに返信する．. ⓒ 2015 Information Processing Society of Japan. 5.1 柔軟性今回述べる柔軟性とは完全一致検索以外の検索が可能であるか，キーワードの削除が可能であるかの 2 点である．部分一致検索を可能にするためにキーワードを一文字単位で登録した登録の手法は 4.2 項で述べたとおりである．検索も登録時と同様に一文字単位で検索を行う．その検索アルゴリズムを以下に示す．. (1). 検索者は検索キーワードを入力する．. 4.

(5) Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 情報処理学会研究報告 IPSJ SIG Technical Report. (2). キーワードを一文字ごとに分解する．. (3). 一文字目から順に，それぞれの文字番号と結合させてハッシュ値を得る．. (4). ハッシュ値をカウンティングフィルタと比較する．一致した場合は次の文字の判定に進み，一致しない場合は false と返し終了する．. (5). 最後の文字まで全て一致した場合，true と返す．. 作成したプログラムの検索時のフローチャートを図 10 に示す．図中の”||”は結合子の意味である．実際にはハッシュ関数が複数あるため，比較判定の部分を繰り返し文で表現している．. 図 11. ᳨⣴. 検索結果. 5.2 時間計算量提案手法の時間計算量について，登録時にはキーワー ;ϭͿ. Eධຊ. EїŶϭ͕ŶϮ͕䡡䡡䡡Ŷŝ Eŝї;ŝͮͮŶŝͿ. ドの文字数に依存する．キーワードの文字数を C とすると，登録する際の時間計算量は O(CK) となる．また，キー. ;ϮͿ. ワードの削除に関してもこれと同様である．キーワードの総文字数が増える程，時間計算量も大きくなる．. ;ϯͿ. 検索の際には，先頭から一文字ずつ判定して結果が存在 ;ϰͿ. しないとなった場合それ以降の文字は判定しない．よって. EŽ. ,;ŶŝͿсϬ͍. E;ŝнϭͿсEh>>͍ ĨĂůƐĞ. 状況によって時間計算量が異なる．キーワードが存在しな. ;ϱͿ. zĞƐ. EŽ. ŝїŝнϭ. zĞƐ ƚƌƵĞ. 図 10 検索プログラムのフローチャート. 完全一致検索以外の検索手法には，以下の手法がある．・. 算量は O(CK) となる．. 20 文字のランダムな文字列を生成し，それをカウンティングフィルタに登録する時間を測定した (図 12)．N = 1 − 50 個，C = 20 − 1000 文字の範囲で測定を行った．また，. M = 1024，K = 8 個である．図 12 を見ると, 実線の測定値ではばらつきがあってわかりにくいが，近似値を表した破線に注目すると文字数が増加するごとに実行時間も増加. キーワードの前半部分が一致する検索である．今回. することは明らかである．. 致検索を可能としている．後方一致検索キーワードの後半部分が一致する検索である．前半部分に’ ?’ を用いることで後方一致検索を可能としている．・. 在しない場合の最悪時間計算量及び存在する場合の時間計. 前方一致検索の検索手法では後半部分に’ ?’ を用いることで前方一. ・. い場合の最良時間計算量は O(1) となり，キーワードが存. 部分一致検索. ϮϱϬϬ ϮϬϬϬ Ϳ Đ ϭϱϬϬ Ğ Ɛ ŵ ;. 㛫ϭϬϬϬ ᫬ ϱϬϬ. キーワードの一部が一致する検索である．一致しない部分に’ ?’ を用いることで部分一致検索を可能とし. Ϭ. Ϭ. ϮϬϬ. ている．図 12. それぞれの検索手法が可能であることを図 11 に示す．図. ϰϬϬ. ᩥᏐᩘ. ϲϬϬ. ϴϬϬ. ϭϬϬϬ. 実行時間のグラフ. 11 では CountingFilter に，’2014/12/19’ というキーワードを登録してある．キーワードの削除についても CountingFilter を用いることで対応させてある．. ⓒ 2015 Information Processing Society of Japan. 5.3 偽陽性率カウンティングフィルタの偽陽性率は第 3.1 項で述べたブルームフィルタの偽陽性率と同様である．しかし，提案. 5.

(6) Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 情報処理学会研究報告 IPSJ SIG Technical Report. 手法では一文字単位で登録するため文字数も考慮しなければならず，その式は次のようになる．. (1 − (1 −. 5.4 データ量カウンティングフィルタとブルームフィルタとで大きく異なるのが配列のサイズである．同じ数の配列を用意した. 1 KC K ) ) M. 場合，ブルームフィルタはビット列であるため一つの要素. 図 13 は M = 1024 の時の偽陽性率を示したものである．. K それぞれ 2,4,8,16 としている．明らかに C が増加する. につき 1 ビットでよいが, カウンティングフィルタは数列になるためより多くのビット数を必要とする．その結果カウンティングフィルタの方が配列数は同じでもそのサイズ. ほど偽陽性率は増加している．. は大きくなる．カウンティングフィルタではオーバフローを起こさない. ϭ. ようにする必要がある．オーバフローが起きた場合，キー. Ϭ͘ϵ ŬсϮ. ⋡ ᛶ 㝧 ഇ. Ϭ͘ϴ. Ŭсϰ. Ϭ͘ϳ. Ŭсϴ Ŭсϭϲ. Ϭ͘ϲ. ワードの削除ができなくなるためである．オーバフローを起こさないために一番安全な方法は，一つの要素ごとに「キーワードの文字数×ハッシュ関数の数」ビット用意す. Ϭ͘ϱ. る方法である．このように設定すると仮に全てのハッシュ. Ϭ͘ϰ. 値が同値であったとしてもオーバフローを起こすことはな. Ϭ͘ϯ. い．しかし，ハッシュ関数は配列の各位置を同じ確率で返. Ϭ͘Ϯ. すため，今回の実験では 8 ビット用意した．28 = 256 ビッ. Ϭ͘ϭ Ϭ. トの衝突が可能であるため十分といえる． Ϭ. ϭϬϬ. ϮϬϬ. ϯϬϬ. ϰϬϬ. 図 13. ϱϬϬ. ᩥᏐᩘ. ϲϬϬ. ϳϬϬ. ϴϬϬ. ϵϬϬ. ϭϬϬϬ. 偽陽性率のグラフ. 6. まとめと今後の課題本稿では，カウンティングフィルタを用いた柔軟な検索手法について検討した．カウンティングフィルタを用いる. また，本手法での偽陽性率は上式のみでは求まらない．. ことでキーワードの削除に対応することができ，一文字ご. 図 14 において検索してある二つのキーワードは共に true. とに登録することによって完全一致検索のみでなく，前方. と返されているが，いずれも偽陽性である．一つ目の”key”. 一致検索，後方一致検索，部分一致検索も可能とした．. は，登録されている”keyboard”というキーワードの前半部. カウンティングフィルタではブルームフィルタと同様に. 分と同様のハッシュ値が得られる．これは前方一致検索と. 偽陽性が発生する．そのため偽陽性率について検討する必. いう部分一致検索の一例でもあるのだが，実際には”key”. 要がある．本手法は単一のファイルを管理するため登録す. というキーワードを登録していないため擬陽性とする．二. るキーワードを最大 5 とする．ここでいうキーワードの数. つ目の”keep”は，図 14 の複数の登録キーワードの点線に. とは図 2 における検索タグの数のことである．一つのキー. 囲まれた部分を結合すると，”keep”と一致していることが. ワードで 20 文字を超えることは考えにくいため，文字数. わかる．このように複数のキーワードの文字群から意味の. の最大値を 100 とした．今回は M ＝ 1024，K ＝ 8 として. ある単語が発生する場合も偽陽性といえる．これらの事象. 第 5.3 項の式に代入して偽陽性率を求めた．その結果偽陽. が起こりうる確率については現在検討中であるが，登録. 性率はおよそ 0.75 ％となり，許容できる範囲内である．. キーワードが増加するほどに確率も上昇することは明らか. 現在，入力された文字列の型を変更させて得た値を用いる単純なものをハッシュ関数として使用しているが，今後. である．. は HMAC-SHA256 に変更する．HMAC-SHA256 では 256 ビットの結果が返ってくる．今回用意したカウンティン. Ⓩ㘓䜻䞊䝽䞊䝗 ŬĞǇďŽĂƌĚ ;ϭŬ͕ϮĞ͕ϯǇ͕͙Ϳ. ĚŝƐƉůĂǇ ;ϭĚ͕Ϯŝ͕ϯƐ͕ϰƉ͕͙Ϳ. ƐƉĞĂŬĞƌ ;ϭƐ͕ϮƉ͕ϯĞ͕͙Ϳ. グフィルタは M ＝ 1024 であるため，その範囲内にマッピングする必要がある．得られたハッシュ値を h として，. hmod(M ) の計算を行いマッピングした．䜹䜴䞁䝔䜱䞁䜾䝣䜱䝹䝍. カウンティングフィルタの各要素のサイズについて，正規のハッシュ関数を用いることで配列の全ての要素に同じ確率で選択されるものとする．C ＝ 100，K ＝ 8 として得. ŬĞǇ;ϭŬ͕ϮĞ͕ϯǇͿсƚƌƵĞ ͖ 図 14. ŬĞĞƉ;ϭŬ͕ϮĞ͕ϯĞ͕ϰƉͿсƚƌƵĞ 新たな偽陽性の説明. られるハッシュ値の数は 800，それに対して配列数は 1024 である．キーワードを分解した際に同じ文字番号に同じ文字がある場合なども考慮して，8 ビット用意する．ハッシュ関数を偽陽性率が最も小さくなるように設定してあるため. ⓒ 2015 Information Processing Society of Japan. 6.

(7) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-CSEC-69 No.8 Vol.2015-IOT-29 No.8 2015/5/21. 実際にはまだ小さくても問題ないと考えられる．今後許容できる値等についても検討していく．また，今回の場合ではカウンティングフィルタのサイズは 1024[byte] となる．今回作成した物は簡易的なものであるため，今後は実装を目的として研究を行う．今回用いたハッシュ関数は簡易的な計算式を基に作成したため正確性に欠ける．ここでの正確性とは，フィルタの全ての番地に同様の確率で結果を返すことができるかどうかを指す．今後は米国家安全保障局 (NSA) によって開発された HMAC-SHA256 を用いることでより正確なシミュレーションを行う．仮想のクラウドを設計し，実際に複数の PC で登録, 検索を行う．特に検索は複数のファイル (カウンティングフィルタ) を用意し，検索に要する時間や，より正確な偽陽性率等について検討する．また，暗号方式であるから安全性についても当然考慮しなければならない．安全性についての数学的な証明等も今後行う必要がある．参考文献検索可能暗号：研究開発：日立 - 日立製作所:http://www.hitachi.co.jp/rd/portal/glossary /jp ke/kensakukanou angou.html． [2] 菅孝徳，西出隆志，櫻井幸一，”ブルームフィルタを用いた検索自由度の高い検索可能暗号の設計と実装評価”，情報処理学会研究報告，Vol.2011-CSEC-53，No.20(2011)． [3] 木村俊介，稲葉宏幸，”ブルームフィルタを用いた高速な検索可能暗号方式の提案”，電子情報通信学会，信学技報 (2014)． [4] 関数型暗号三菱電機: http://www.mitsubishielectric.co.jp/corporate /randd/spotlight/spotlight15.html. [5] 冨田幸嗣，宮嵜仁志，毛利公美，白石善明，”アクセス制御機能付き検索可能暗号の ID ベース暗号からの構成” ，マルチメディア，分散，強調とモバイル (DICOMO2013) シンポジウム，pp.208-214(2013)． [6] 冨田幸嗣，毛利公美，白石善明，”暗号文の提供者を不特定多数とする検索者を限定したキーワード検索可能暗号方式”，情報処理学会第 75 回全国大会，pp.517-518(2013)． [7] 伊藤孝一，牛田芽生恵，山岡裕司，及川孝徳，菊池浩明，” 検索可能秘密分散方式の提案”，情報処理学会研究報告， Vol.2014-DPS-158 No.13(2014)． [8] 森拓海，平野貴人，服部充洋，伊藤隆，松田規，”検索可能暗号におけるハフマン符号を利用した索引手法”情報処理学会第 74 回全国大会，pp.589-590(2012)． [9] 松田規，伊藤隆，柴田秀哉，服部充洋，平野貴人，”検索可能暗号の高速化と Web アプリケーションへの適用方式に関する提案”，マルチメディア，分散，強調とモバイル (DICOMO2013) シンポジウム，pp.2067-2074(2013)． [10] 西出隆志，櫻井幸一，菅孝徳，”クラウドストレージサービスにおける実用的検索可能暗号の実現”，電気通信普及財団，研究調査報告書，No.28，pp.511-516(2013)． [11] B.H.Bloom，”Spase/time trade-oﬀs in hash coding with allowable errors” ，Commun.ACM,vol.13,no.7,pp.422426(1970)． [12] L. Fan, P. Cao, J. Almeida, A. Broder， ”Summary cache: A scalable wide-area Web cache sharing protocol. ”，In Proceeding of SIGCOMM ’98(1998)．. [1]. ⓒ 2015 Information Processing Society of Japan. 7.

(8)