一般論文♯これはあ

DBSJ Journal, Vol.12,No.2
October 2013

Bloom Filter を 利 用 し た 暗 号 化
SLCA 検索手法の検索手法の提案
Searching Encrypted
Bloom Filter

SLCA byUsing

中村伸一♥ 山本博章♦
Shin-ichi NAKAMURA♥ Hiroaki YAMAMOTO♦

XML 文書は
文書は XPath や XQuery を利用することで利用することで検索することで検索を検索を行うことができる．
ができる．しかし，
しかし，XPath や XQuery を利用するには利用するには，するには， XPath や
XQuery の文法や文法や検索する検索する XML 文書の文書の構造を構造を知っている必要っている必要が必要があり，あり，初心者には
初心者には難には難しいものとなっている．
しいものとなっている．そのため，
そのため，初心者に
初心者に
も 簡単に
簡単 に XML 文書の
文書 の 検索が
検索 が 行 えるように，えるように ， キーワードによるXML 文書の文書の検索手法について
検索手法について研究について研究が研究が進められている．
められている．本研究は，キーワードによる XML 文書の文書の検索に検索に焦点を焦点を当て，与えられたキーワードに対たキーワードに対し暗号化された
暗号化された XML 文書から
文書から，から，その SLCA を検索するための検索 するための手法
するための 手法を
手法 を 提案する
提案する．
する ． 我 々 の 手法では
手法 では権限
では 権限のない
権限 のない
管理者は管理者は検索するキーワードや検索するキーワードや結果するキーワードや結果を
結果を知 ることができない．
ることができない．本
稿 では，では，提案手法の提案手法 の安全性
安全性 について議論
について 議論し議論し，さらに，さらに，実験的に実験的に検索性能についても検索性能についても評価についても評価する
評価する．
する．
An XML document search can be performed by using
XQuery and XPath. However, we must know thegrammar of XPath or XQuery and the structure of an
XML document. Furthermore it is difficult for beginners
to use XQuery and XPath. Therefore, search methods on
an XML document using keywords have been studied sothat beginners can easily search an XML document. In
this paper, we propose a method to find Smallest Lowest
Common Ancestors (SLCAs) from an encrypted XML
document. In the proposed method, administrators
without access permission to the XML document canknow neither keywords nor search results. We discuss
security on the proposed method, and also evaluate search
performance by some experiments.

1. はじめに
近年，音声や動画配信，クラウド，商取引，Web 等の利用によって，インターネット上でやり取りされる情報量は増加し続けている．様々な形式の情報がインターネット上でやり取りされるが，その一つである XML は情報交換を目的とした形式として広く利用されている．XML は XPath や XQuery を利用することで詳細な検索を行うことができる．しかし，XPath や XQuery を利用するには，XPath や XQuery の文法や検索する XML 文書 の構造を知っている必要があり，初心者には難しいものとなっている．
そのため，初心者にも簡単に XML 文書 の検索が行えるよ
うに，キーワードによる XML 文書の検索手法について研究が♥学生会員 信州大学大学院総合工学系研究科
s09t203@shinshu-u.ac.jp♦
正会員 信州大学工学部
yamamoto@cs.shinshu-u.ac.jp

1

進められている．しかし，今までに提案されている手法は，
XML 文書を平文でデータベースに登録するため，データベースの管理者に検索内容や結果が知られてしまい，管理者から情報漏えいが発生する問題がある．
そのため，我々はキーワードによる XML 文書の検索手法である The Indexed Lookup Eager Algorithm[1](以下 IL)について，管理者に検索内容や結果がわからない暗号化に対応した手法を提案する．
提案手法は，事前に XML 文書から Bloom Filter と暗号化されたデータで構成されたテーブルを構築し，リレーショナ
ルデータベース(以下 RDB)に登録する．検索時は RDB 上で
Bloom Filter を利用したキーワードによる XML 文書の検索を行い，検索結果の Bloom Filter に対応する暗号化されたデータを RDB から取得する．取得した暗号化されたデータを復号して検索結果を作成する．この手法により，セキュリティ
上構築が難しい情報環境でもキーワードによる XML 文書の検索環境を構築できる．管理者に検索内容や結果がわからない
ため，Amazon Simple DB[2]等のインターネットを経由したデータベースサービスのような，利用者によるセキュリティ
管理が難しい情報環境でも，安心してキーワードによる XML
文書の検索環境を構築できる．
本論文は次のように構成されている．1 章のまえがきに続き，2 章は関連研究について述べる．3 章は提案手法について前提となる知識について述べる．4 章は IL の具体的なアルゴリズムについて述べる．5 章は提案手法を利用した暗号
化 XML 文書検索システムと具体的なアルゴリズムについて述
べ，また，提案手法の安全性について議論する．6 章は 5 章で述べた暗号化 XML 文書検索システムによる実験と考察について述べる．7 章はまとめと今後の課題について述べる．

2. 関連研究2.1 暗号化データに暗号化データに対
データに対するキーワード検索手法
するキーワード検索手法
金子[3]らは，Non-ShuffledBF と ShuffledBF を組み合わせ
る こ と で 安 全 性 を 損 な わ ず に RDB を 高 速 に 検 索 で き る
Semi-ShuffledBF と呼ばれる手法を提案したが，検索時に選択されるタプル数に合わせて Bloom Filter の処理を変えることでさらに高速化した手法を提案している．Watanabe[4]らは，データと鍵でハッシュ化するだけでは同じデータは同
じ結果となり出現数からデータが推測される可能性があると指摘し，暗号化したデータをさらにハッシュ化することでデータの推測を防ぐ手法を提案している．
Yan[5]らは，疑似乱数ビットを文書に対するインデックスに処理することで，計算量や通信量が少ないモバイル機器でも暗号化したままで検索できる手法を提案している．Liu[6]らは，検索可能公開鍵暗号である PEKS に対して，クラウド
上の文書に対するモバイル機器のキーワード検索を想定した計算量や通信量が少ない検索可能公開鍵暗号である CKPSと呼ばれる手法を提案している．
Wang[7]らは，XML 文書の要素の位置を 0 から 1 の実数で表現する DSI を利用して，暗号化した要素名と DSI のインデックスと DSI と対応する暗号化データのインデックスを RDBに登録することで，暗号化された XML 文書を検索する手法を提案している． Bertino[8]らは，XML 文書中の部分木を異なる鍵で暗号化することで利用者に対するアクセス制御を行う手法を提案している．Chang[9]らは，暗号化された XML 文
書全体を入手して復号し検索するのは効率的ではないと指摘し，XML 文書のスキーマを利用して検索結果に必要な暗号

日本データベース
日本データベース学会論文誌
データベース学会論文誌 Vol.12, No.2
2013 年 10 月

一般論文

♯これはあ

DBSJ Journal, Vol.12,No.2
October 2013

化された部分のみ入手するように XQuery を翻訳することで，暗号化された部分を減らす手法を提案している．Li[10]らは，事前に XML 文書からアクセス制御の情報を追加したインデックスを作成することで検索結果にアクセス制御が反映される手法を提案している．Unay[11]らは，暗号化された XML 文
書検索に関する手法について，暗号化標準と暗号化インデックスとパスや DeweyOrder の暗号化の視点でまとめたものを報告している．

2.2 検索手法の検索手法の比較提案手法と論文[3]～[10]について手法の比較を表 1 に示
す．項目について，データは扱うデータの種類，検索は検索処理をクライアントかサーバのどちらで実行するか，条件は検索条件の指定方法，暗号化はデータに対して暗号化する範囲，暗号化(XML)は XML 文書に対して暗号化する範囲の詳細，
取得データはクライアントが取得するデータ，アクセス制御
は利用者へのアクセス制御が可能かを示す．
提案手法は，XML 文書の内容や構造を暗号化する範囲としてキーワードによる検索を行う．クライアントはサーバから
XML 文書中のキーワードに合致するデータの一部を取得し，サーバとクライアントで検索を実行する．利用者へのアクセ
ス制御は対応しない．
論文[7]～[10]のような RDB に暗号化した XML 文書を登録して検索する手法は，条件に合う要素を取得する手法のため，SLCA を取得するにはクライアントで処理する必要があり，
SLCA を検索する仕組みは考慮されていない．
暗号化 IL は，XML 文書を暗号化したデータに対して，データと同様に暗号化したキーワードと一致するデータのみ
取得し，復号したデータに IL を適用する手法である．

XQuery や XPath を利用した検索手法は，検索結果が XQueryや XPath が指定する XML 文書中の特定の部分となるため，検索手法に関わらず検索結果は同じとなる．一方で，キーワー
ドを利用した XML 文書の検索手法は，検索結果に対する視点が異なるため，同じキーワードで検索しても検索手法によって結果が異なる．本稿で暗号化に対応する手法である IL は，
XML 文書中ですべてのキーワードを含む最小部分木の根である Lowest Common Ancestor(以下 LCA)の中で，子孫に LCAを持たない Smallest Lowest Common Ancestor(以下 SLCA)を検索する．提案手法の説明の簡略化のため，本稿では XML 文
章中のテキストそのものをキーワードとし，キーワードと同じテキストと言った場合，キーワードと内容が完全に一致するテキストを意味するものとする．
Bloom Filter は要素が集合に属しているか調べるデータ構造である．Bloom Filter は長さ m のビット配列と，k 個のハッシュ関数を用いる．ハッシュ関数はビット配列の長さの範囲(0,...,m-1)の整数を出力する．要素を集合に登録す
るには，要素名をハッシュ関数で数値に変換し，数値に対応するビット配列のビットを 1 にする．要素が集合に含まれるか判定するには，要素名をハッシュ関数で数値に変換し，数値に対応するビット配列のビットが 1 であれば要素は集合に含まれる(図 2)．Bloom Filter は誤って集合に属していると判断する偽陽性の可能性があるが，提案手法はクライアント
で Bloom Filter の判断が正しいか確認している．

表 1 手法の手法の比較

論文

Table 1 Comparison of the Technique
暗号化(XML)
ﾃﾞｰﾀ 検索条件 暗号化 内容
取得ﾃﾞｰﾀ
構造

金子[3]
RDB
ｻｰﾊﾞ
SQL
すべて
Watanabe[4] RDB
ｻｰﾊﾞ
SQL
すべて
Yan[5]
ﾃｷｽﾄ
ｻｰﾊﾞ
ｷｰﾜｰﾄﾞ すべて
Liu[6]
ﾃｷｽﾄ
ｻｰﾊﾞ
ｷｰﾜｰﾄﾞ すべて
Wang[7] XML文書 ｻｰﾊﾞ
XPath
一部
Bertino[8] XML文書 ｻｰﾊﾞ XQuery,XPath 一部
Chang[9] XML文書 ｻｰﾊﾞ
XQuery 一部
Li[10]
XML文書 ｻｰﾊﾞ
ｷｰﾜｰﾄﾞ 一部
暗号化IL XML文書 ｸﾗｲｱﾝﾄ
ｷｰﾜｰﾄﾞ すべて
提案手法 XML文書 ｻｰﾊﾞ、ｸﾗｲｱﾝﾄ ｷｰﾜｰﾄﾞ すべて

○
○
○
○
○
○

×
×
×
×
○
○

ｱｸｾｽ
制御

条件に合致するﾃﾞｰﾀのみ 不可
条件に合致するﾃﾞｰﾀのみ 不可
条件に合致するﾃﾞｰﾀのみ 不可
条件に合致するﾃﾞｰﾀのみ 不可
条件に合致するﾃﾞｰﾀのみ 不可
条件に合致するﾃﾞｰﾀのみ 可能
条件に合致するﾃﾞｰﾀのみ 不可
条件に合致するﾃﾞｰﾀのみ 可能
ｷｰﾜｰﾄﾞに合致するﾃﾞｰﾀすべて 不可
ｷｰﾜｰﾄﾞに合致するﾃﾞｰﾀの一部 不可

(a)

(b)
図 1 XML 文書の文書の木構造表現

Fig.1 Tree Representation of the XML Document

3. 準備XML 文書は要素をノードとする木構造で表すことができ，木の各ノードは要素名でラベル付けされている．<要素名>の開始タグと</要素名>の終了タグで挟まれるテキストも要素と同様にノードとして表すことができ，各ノードはテキストの内容でラベル付けされている．パスは根からノードまで辿る経路に出現するノードである．XML 文書を検索するには，要素やテキストの位置関係（先祖，子孫，親，子，兄弟等）を把握するため，要素やテキストの位置を把握する必要があ
る．XML 文書の要素やテキストの位置の表現に関して様々な手法があるが，IL は DeweyOrder を利用している．DeweyOrderは木の深さごとに"."で区切り，同じ親の要素である兄弟の左端を 0 とし，右に向かって順に 1,2,...と番号を割り当てたものである．本稿では，DeweyOrder はテキストを持つノードの DeweyOrder を意味する．
XML 文書の図 1(a)を同等の木で表現し，木の各ノードに要素名やテキストの内容と DeweyOrder を追加し，テキストのノードは下線を追加したものを図 1 (b)に示す．

2

図 2 ブルームフィルタ
Fig.2 Bloom Filter

4. The Indexed Lookup Eager Algorithm の手法
4.1
4.1 概要The Indexed Lookup Eager Algorithm[1]は，3 つのキーワ
ードに対する SLCA を取得する場合，初めに 1 番目と 2 番目のキーワードに対する SLCA を取得し，次に先ほどの SLCA と3 番目のキーワードに対する SLCA を取得する．このようにキーワードに対して順番に SLCA を繰り返し取得することで，すべてのキーワードに対する SLCA を取得する．SLCA はキーワードと同じテキストから見て，左側と右側で最も近い次の日本データベース
日本データベース学会論文誌
データベース学会論文誌 Vol.12, No.2
2013 年 10 月

一般論文

♯これはあ

DBSJ Journal, Vol.12,No.2
October 2013

キーワードと同じテキストの LCA が子孫となる方を SLCA としている．ただし，子孫にすでに検索した SLCA は含まないものとする．図 1(a)の XML 文書からキーワード c1,d1,e1 のSLCA を取得する場合は，以下の(1)～(4)の手順で行う．IL
はテキストの内容毎にテキストの DeweyOrder の集合で構成されたデータから，キーワードと同じテキストすべてのDeweyOrder の集合を取得する．2.2 節で述べた暗号化 IL はテキストの内容と DeweyOrder の集合を暗号化したデータから，暗号化したキーワードと同じテキストの内容に対応する
DeweyOrder の集合を取得し，復号した DeweyOrder の集合に
IL を適用する．
(1) 1 つ目のキーワード(c1)と 2 つ目のキーワード(d1)と同じ内容のテキストを検索する(図 3○)．
(2) (1)で得たテキストに対する SLCA を求める(図 3□)．
(3) 3 つ目のキーワード(e1)と同じ内容のテキストを検索する(図 3 点線○)．
(4) (2)と(3)の要素に対する SLCA がキーワード c1,d1,e1に対する SLCA となる(図 3 点線□)．

図 3 IL の手法
Fig.3 Method of IL

4.2
4.2 従来のキーワードによる従来のキーワードによる XML 文書検索の
文書検索の問題点

図 5 暗号化 XML 文書検索システムの文書検索システムの構成
システムの構成
Fig.5

Configuration of Encrypted XML Document
Search System

5.2
5.2 提案手法
5.2
5.2.1 概要
4.1 節で述べたように IL が SLCA を検索するには，キーワ
ードと同じテキストに対して，左側と右側で最も近い次のキーワードと同じテキストが必要となる．IL はキーワードと同じテキストを，XML 文書全体を範囲として RDB サーバから取得する．提案手法は，1 番目のキーワードと同じテキストを，XML 文書全体を範囲として RDB サーバから暗号化したままで検索し取得するが，2 番目以降のキーワードは前のキーワー
ドと同じテキストの親から根に向かったパス上の要素を根とする部分木を範囲として，次のキーワードと同じテキスト
を RDB サーバから暗号化したままで検索し取得する．提案手法は検索する範囲が XML 文書全体より狭いため，IL よりテキストの取得を減らすことができる．検索したテキストから
4.1 節で述べた手法で SLCA を取得する．
部分木の範囲でキーワードと同じテキストの検索をする
場合は，事前に XML 文書の要素毎に要素名とパス上の要素の位置を Bloom Filter に登録する(図 6①)．検索時はキーワードと範囲とする部分木の根から XML 文書の根までのパス上の要素の位置から Blooｍ Filter を作成し(図 6②)，作成した
Bloom Filter と同じデータが RDB サーバの Bloom Filter に含まれるか判定する(図 6③)．

IL はキーワードや検索結果の暗号化を行っていない．そのため，管理者がキーワードや検索結果を入手することで，情報漏えいが発生する問題がある(図 4)．

図 6 部分木のキーワード
部分木のキーワード検索のキーワード検索
Fig.6

図 4 管理者による管理者による情報漏による情報漏えい
情報漏えい
Fig.4 Information Leakage by the Administrator

Keyword Search in the Subtree

クライアントと RDB サーバとの間で以下のデータのやり取りを行う．

5 暗号化 XML 文書検索システム
文書検索システム
4.2 節で述べた問題点に対応した，XML 文書を暗号化したままで検索する暗号化 XML 文書検索システム(以下システム)を以下に提案する．

5.1 概要システムの概要を図 5 に示す．前処理として XML 文書を RDB
サーバに登録するため，利用者は XML 文書と暗号化に使用する鍵(以下 K)をクライアントに入力する．クライアントは，
K を用いて XML 文書の暗号化を行い，暗号化したデータを RDB
サーバに登録する．検索は，利用者がキーワードと K をクライアントに入力する．クライアントは 5.2 節の手法に基づき，検索結果を返す．なお，RDB サーバからクライアントがデータを取得した場合，K によるデータの復号が行われる．

3(1) Bloom Filter と暗号化された情報で構成されたデータテーブルを作成する(図 7(a)①)．
(2) キーワードと同じテキストを取得するため，テキストの内容とパスに関する情報から Bloom Filter を作成し，作成した Bloom Filter と同じデータが含まれるデータテーブルの Bloom Filter に対応した暗号化された情報を取得する(図 7(b)①②④)．
(3) (2)で取得した暗号化された情報から IL と同じ手法でSLCA を取得する(図 7(b)③)．
ハッシュ化の際，ハッシュから平文を推測されないようにするため，平文に鍵を追加している．ハッシュ化は，ハッシ
ュ化する平文のデータをHD，鍵を K，H୦ୟୱ୦ をハッシュ関数，

日本データベース
日本データベース学会論文誌
データベース学会論文誌 Vol.12, No.2
2013 年 10 月

一般論文

♯これはあ

DBSJ Journal, Vol.12,No.2
October 2013

5.2
5.2.3 キーワードに対応
キーワードに対応するデータ
対応するデータ取得
するデータ取得

HD′をハッシュ化データとして式(1)に従って行っている．
HD′  H୦ୟୱ୦ K, HD

(1)

暗号化の際，平文と暗号文から鍵を推測されないようにするため，平文にランダム文字列を追加している．暗号化は暗号化する平文のデータをED，ランダム文字列を S，鍵を K，暗号化関数をEୣ୬ୡ ，暗号化データをED′として式(2)，復号は復号関数をEୢୣୡ として式(3)に従って行っている．
ED′  Eୣ୬ୡ K, ED, S
ED  Eୢୣୡ K, ED′

(2)
(3)

(a)

(b)
図 7 提案手法
Fig.7

Proposed Method

5.2.2 XML 文書の文書の暗号化XML 文書を RDB サーバ に登録するため，データテーブル(以下 DTBL)を構築する．図 1(a)を XML 文書とする DTBL の構造を図 8 に示す．図 8 の EncryptedData 列の括弧内は，そこに格納されている暗号化データの元の値(要素名，テキスト，
DeweyOrder，位置情報)を示している．
DTBL は，5.2.1 節に従ってハッシュ化された要素名やテキストの内容と位置情報と DeweyOrder が登録された Bloom
Filter ， 5.2.1 節 に 従 っ て 暗 号 化 さ れ た デ ー タ で あ る
EncryptedData で構成されている．位置情報はパス上の要素
やテキスト毎に要素名やテキストの内容と深さを”:”でつなげたものである．DeweyOrder が 0.0.2.0 の位置情報は
a:0,b:1,f:2,c:3 であり，それぞれを Bloom Filter に登録す
る．DeweyOrder は Bloom Filter がすべて異なるようにする
ため登録している．暗号化されたデータは要素名やテキストの内容と DeweyOrder と位置情報で構成されている．紙面の関係から DTBL の一部と Bloom Filter と EncryptedData の暗号列の途中を省略する．この処理における計算量は，XML 文書の要素とテキストの合計を n とした場合 O(n)である．

キーワードと同じテキストの取得を以下の(1)～(3)の手順で行う．キーワードが 3 つ以上の場合はいままでの SLCAの位置情報と(3)からキーワードに対応するデータ取得を行う．Bloom Filter は誤ってデータを取得する場合があるため，取得後にテキストの内容がキーワードと一致するか確認す
る．(3)で判定結果はクライアントに記憶するため，以前に作成した Bloom Filter で判定は行わない．この処理における計算量は，キーワードと同じテキストのパス上の要素を根とする部分木の要素とテキストの合計を n とした場合 O(n)である．
(1) 5.2.1 節に従ってハッシュ化されたキーワードから
Bloom Filter を作成し，同じデータが RDB サーバのBloom Filter に含まれるか判定する．含まれる Bloom
Filter に対応した EncryptedData を取得する．
(2) (1)で取得した EncryptedData 毎に 5.2.1 節に従って復号し DeweyOrder と位置情報を取得する．取得した
EncryptedData 毎に(3)を行う．
(3) 5.2.1 節に従ってハッシュ化されたキーワードと位置情報から最も深さが大きいものを除いた残りから
Bloom Filter を作成し，同じデータが RDB サーバのBloom Filter に含まれるか判定する．含まれる Bloom
Filter に対応した EncryptedData を取得する．取得した EncryptedData 毎 に 5.2.1 節 に 従 っ て 復 号 し ，DeweyOrder が(2)の DeweyOrder に対し左側か右側にあるか調べ，左側右側毎に取得したデータを保存する．再び左側か右側にデータがあった場合，最初に保存したデータより(2)の DeweyOrder から遠くなるため保存しない．左側と右側の両方のデータが揃うまで(3)を繰り返す．
キーワード c1 と同じテキスト(図 9①)に対して，キーワー
ド d1 と同じテキストを検索する場合，テキストの親(図 9②)から XML 文書の根(図 9④)に向かってパス上の要素(図 9②③④) 毎に，要素を根とする部分木にキーワード d1 と同じテキストがないか検索する(図 9 矢印)．結果として，図 9 ①に対する右側のキーワード d1 と同じ内容のテキストとして，要素(図 9②)を根とする部分木に次のキーワード d1 と同じテキスト(図 9⑤)を発見し，左側のキーワード d1 と同じテキストとして，XML 文書の根(図 9④)を根とする部分木に次のキーワード d1 と同じテキスト(図 9⑦⑧)を発見する．

図 9 キーワードによるデータ取得
キーワードによるデータ取得
Fig.9 Obtaining Data by Keywords
図8

図 1(a)のの XML 文書に文書に対応する
対応する DTBL

Fig.8 DTBL for the XML Document in Fig. 1(a)4

日本データベース
日本データベース学会論文誌
データベース学会論文誌 Vol.12, No.2
2013 年 10 月

一般論文

♯これはあ

DBSJ Journal, Vol.12,No.2
October 2013

5.2.4
5.2.4 SLCAのSLCAの取得
5.2.3節で取得したデータを5.2.1節に従って復号し，EncryptedData中のDeweyOrderを利用して，ILと同様の手法
でSLCAを取得する(図10)．

と等しいか比較するSQLとした(図11(a)②)．ただし，この手法はBloom Filterのビット数分のインデックスが必要なため，
DTBL_INDEXの構築に時間がかかる．

(a)

図 10 SLCA の取得(b)

Fig.10 Obtaining SLCA

図 11 Bloom Filter のインデックス構築のインデックス構築

5.3
5.3 安全性について
安全性についてFig.11 Constructing Index for Bloom Filter

提案手法の安全性の評価を，想定される攻撃に対する対応策を分析することで行った．
(1) RDBサーバに対する攻撃
 DTBLのEncryptedDataに対する既知平文攻撃攻撃を行うには，要素に関するデータがある平文が必要だが，5.2.1節で述べたように平文にランダムな文字列を追加して暗号化されており，平文は入手できない．そのため，攻撃はできない．
 DTBLのEncryptedDataに対する選択平文攻撃
既知平文攻撃で述べたように，ランダムな文字列を追加して暗号化してあるため，平文や平文に対する暗号文も入手することができない．そのため，攻撃はできない．
 DTBLのBloom Filterに対する攻撃
5.2.2節で述べたようにBloom Filterは要素名やテキストの内容とDeweyOrderをハッシュ関数で処理したデータを登録しているため，安全性は利用するハッシュ関数に依存する．
(2) RDBサーバとクライアント間のデータのやり取りに対する攻撃
 送信するキーワードに対する攻撃
5.2.1節で述べたように，RDBサーバへBloom Filter
のみ送信されるため，安全性は利用するハッシュ関数に依存する．
 RDBサーバから取得するデータに対する攻撃
RDBサーバから暗号化されたDTBLのデータのみ取得するため，(1)RDBサーバに対する攻撃で述べたように，攻撃はできない．

5.4
5.4 提案手法の提案手法の改善について
改善についてBloom Filter用のインデックステーブルを追加してRDBサーバのインデックスを利用することで検索を高速化する改善を行った．
5.2.3節で実行するSQLは，論理積でBloom Filterに1が設定されているデータを抽出し，排他的論理和で1が設定されている部分が0の場合は，データを取得しない条件としていた(図11(a)①)．しかし，実験で使用したRDBサーバは，条件に論理積や排他的論理和を使用するとRDBサーバのインデックスを使用しないことがわかった．そのため，Bloom Filterの各ビットが列と対応するテーブルDTBL_INDEXを構築し(図11(b))，条件をBloom Filterのビット位置に対応する列が1

5

6. 実験
6.1 実験環境について
実験環境について提案手法と 2.2 節で述べた暗号化 IL と IL の性能比較を行うため実験を行った．RDB サーバは，Intel Xeon 2GHz，メ
モリ 4GB，CentOS 6.0，クライアントは，Intel Core2Duo
2.26GHz，メモリ 2GB，Windows XP の PC を 100Mbps のネットワークで接続して実験を行った．RDB サーバは MySQL
5.1.52 を使用し，提案手法は 5.4 節で述べた手法で Bloom
Filter，暗号化 IL と IL はテキストの内容でインデックスを構築した．提案手法と暗号化 IL と IL のプログラムは，プロ
グラミング言語を Python，ハッシュ関数を SHA1，暗号化ア
ルゴリズムは AES を採用した．
XML 文書は XMark[12]で公開されている XML 文書作成ソフ
トウェアで，50MB の XML 文書を作成した．XML 文書の要素とテキストの合計は 1,254,624 個であった．
Bloom Filter について，誤って判定してしまう確率を 0.1%未満と想定し，登録する要素数は要素名やテキストの内容とパス上の要素毎の位置情報と DeweyOrder を想定し(n=5)，長さ 108(m=108)のビット配列，8 個のハッシュ関数(k=8)を用いた．
XML 文書作成ソフトウェアは，オークションに関するデー
タを想定した XML 文書を作成する．引数の指定により XML 文
書の大きさも指定できる．図 12 に作成する XML 文書の構造の概要を示す．
実験は，提案手法と 2.2 節で述べた暗号化 IL と IL に対して検索するキーワード数と XML 文書中の同じ内容のテキスト
数を変化させて行った．検索したキーワードとテキストの数を表 2 に示す．表 2 の Keywords は検索したキーワード，キーワード右の括弧で囲まれた数値は XML 文書中のキーワードと同じテキストの数を示す．表 2 のキーワードに対して，結果は 3 回測定した検索時間の平均値とした．

図 12 XML 文書の
文書の構造
Fig.12 Element Hierarchy of XML Document

日本データベース
日本データベース学会論文誌
データベース学会論文誌 Vol.12, No.2
2013 年 10 月

一般論文

♯これはあ

DBSJ Journal, Vol.12,No.2
October 2013

【文献】
文献】

表 2 検索するキーワード
検索するキーワード
Table 2 Keyword to Search
No. Keywords
K1

Money order, Personal Check (632),
Will ship only within country (657), United States (11369), 1(18553)

K2

Featured, Dutch (217), 2 (2353), 1 (18553)

K3

Graduate School (676), United States (11369)

6.2 実験結果
表 3 に提案手法と 2.2 節で述べた暗号化 IL と IL の検索時間を示す．項目について，RDB は RDB サーバの実行時間，Decrypt はデータを復号する実行時間，Other は RDB と
Decrypt 以外の実行時間，Total は RDB と Decrypt(表 3(a)(b)のみ)と Other の実行時間，SLCA は検索した SLCA の数，Text
は RDB から入手した要素やテキストの数，Data はサーバとク
ライアント間の通信量を示す．
提案手法(表 3(a))と 2.2 節で述べた暗号化 IL(表 3(b))とIL(表 3(c))を比較すると，IL に比べて暗号化 IL は約 1.1 倍
遅く，提案手法は約 97～231 倍遅い．この理由として，ILと暗号化 IL はキーワードと同じテキストのデータを 1 回で検索している．対して，提案手法はキーワードと同じテキス
トの親から，パス上の要素を根とする部分木に対して検索しているため，IL や暗号化 IL と比べて遅いと考えられる．提案手法は IL や暗号化 IL と比べて遅いが，XML 文書の一部しか検索しないため Text は IL や暗号化 IL と比べて少ない．
しかし，提案手法は Bloom Filter を利用して XML 文書の内
容だけでなく構造も隠したままで検索するが，クライアント
は EncryptedData を取得して検索結果が正しいか確認して擬陽性に対応するため，Data は IL や暗号化 IL に比べて多くなってしまう．
表 3 実験結果(検索時間
実験結果 検索時間)
検索時間
Table 3 Experimental Results for Search Times
K1
K2
K3

RDB (ms) Decrypt (ms) Other (ms) Total (ms) SLCA Text Data (Bytes)
62,133
553
119,400
182,086
22 17,257
19,880,060
50,583439
30,381
81,40315 11,603
17,221,320
33,872
207
29,10063,179240
4,913
9,544,084(a)
RDB (ms) Decrypt (ms) Other (ms) Total (ms) SLCA Text Data (Bytes)
K1
266
5
627
898
22 31,211
588,976
K2
161
10
449
620
15 21,123
390,232
K3
114
0
580
694
240 12,045
235,908(b)
RDB (ms) Other (ms) Total (ms) SLCA Text Data (Bytes)
K1
193
595
788
22 31,211
441,688
K2
130
428
558
15 21,123
292,643
K3
83
569
652
240 12,045
176,903(c)[1] Yu Xu, Yannis Papakonstantinou:“Efficient Keyword
Search for Smallest LCAs in XML Databases”, SIGMOD'05 Proceedings of the 2005 ACM SIGMOD
international conference on Management of data,
pp.527-538 (2005).
[2] “AmazonSimpleDB”,
http://aws.amazon.com/jp/simpledb/.
[3] 金子 静花, 渡辺 知恵美 , 天笠 俊之:“ブルームフィル
タを用いたプライバシ保護検索システム Semi-ShuffedBFの問合せ高速化についての諸検討”, 第 4 回データ工学と情 報 マ ネ ー ジ メ ン ト に 関 す る フ ォ ー ラ ム (DEIM2012),
B7-4 (2012).
[4] Watanabe C. and Arai Y:“Privacy-Preserving Queries
for a DAS model using Two-Phase Encrypted
Bloomfilter”,
Database
SystemsforAdvanced
Applications, pp.491-495 (2009).
[5] Chang, Yan-Cheng, and Michael Mitzenmacher:“Privacy preserving keyword searches on remoteencrypted data”, Applied Cryptography and Network
Security, pp.442-455 (2005).
[6] Liu, Qin, Guojun Wang, and Jie Wu:“Secure andprivacy preserving keyword searching for cloud storage
services”, Journal of network and computer applications
35.3 pp.927-933 (2012).
[7] Wang, Hui, and Laks VS Lakshmanan:“Efficient
secure query evaluation over encrypted XML databases”,
Proceedings of the 32nd international conference on
Very large data bases, pp.127-138 (2012).
[8] Bertino, Elisa, and Elena Ferrari:“Secure and selective
dissemination of XML documents”, ACM Transactions
on Information and System Security (TISSEC) 5.3
pp.290-331(2002).
[9] Chang, Tao-Ku, and Gwan-Hwan Hwang:“Developing
an efficient query system for encrypted XML
documents”, Journal of Systems and Software 84.8
pp.1292-1305 (2011).
[10] Xiaodong Li, Weidong Yang, Jiangang Zhu, Hao
Zhu:“SXKSearch: A System of XML Keyword Search
Based on Secure Access Control”, Proceedings of the2010 International Conference on Internet Computing,pp.77-82(2010).
[11] Ozan Ünay, Taflan I. Gündem:“A survey on querying
encrypted XML documents for databases as a service”,
ACM SIGMOD Record 37.1 pp.12-20 (2008).
[12] “XMark - An XML Benchmark Project”,
http://www.xml-benchmark.org/.

中村伸一 ShinShin-ichi NAKAMURA

7. おわりに
本論文では，管理者が検索内容や結果がわからない，安全なキーワードによる暗号化 XML 文書検索手法を提案した．
提案手法について，XML 文書を暗号化する範囲の攻撃に対して安全性の評価を行い安全であることを示した．
XMark[12]で公開されている XML 文書作成ソフトウェアで作成した XML 文書で，IL と提案手法の手法との性能比較を行い，検索時間は IL より約 97～231 倍遅い結果となった．
今後の課題は検索時間の高速化と DTBL_INDEX を高速に構築する手法の提案である．

6

信州大学大学院総合工学系研究科博士課程在学中．信州大学
大学院工学系研究科・情報工学専攻修了．データベースに関する研究に従事．日本データベース学会学生会員．

山本博章 Hiroaki YAMAMOTO
信州大学工学部教授．東北大学大学院工学研究科博士課程修了．工学博士．アルゴリズムの開発，オートマトン，情報検索に関する研究に従事．電子情報通信学会，情報処理学会，
日本ソフトウェア科学会，日本データベース学会，EATCS 各
会員．

日本データベース
日本データベース学会論文誌
データベース学会論文誌 Vol.12, No.2
2013 年 10 月