DEIM Forum 2017 H6-4

暗号化データベースにおけるデータの秘匿性を保証した検索手法
篠塚 千愛†

渡辺知恵美††

北川博之†††† 筑波大学大学院システム情報工学研究科 〒 305–8573 つくば市天王台 1 丁目 1–1†† 筑波大学システム情報系情報工学域 〒 305–8573 つくば市天王台 1 丁目 1–1††† 筑波大学計算科学研究センター 〒 305–8573 つくば市天王台 1 丁目 1–1
E-mail: †sn@kde.cs.tsukuba.ac.jp, ††chiemi@cs.tsukuba.ac.jp, † † †kitagawa@cs.tsukuba.ac.jp
あらまし DBaaS によるデータ提供では，データ提供者や利用者のプライバシを保証するため，データとクエリを秘匿したまま検索を行ないたい．そこで我々はこれまでに，暗号化されたデータとクエリを秘密計算で照合する検索フ
レームワークを提案している．しかし，データを m 分探索して検索するので，検索を繰り返すにつれて探索段階と選択確率からデータの並びを推測できてしまい，データの秘匿性が低下してしまう．本研究では，探索対象データの選
択にランダム性を与え，探索段階ごとの選択確率の違いを取り除くことで解決を図る．
キーワード プライバシ保護，暗号化データベース，秘匿検索，秘密計算

1. は じ め にるからといって，データの安全性が低下することは暗号化デー
タベースとして望ましくない．

近年，データ提供のための新たなプラットフォームとして，

我々はこれまでに，索引のキー値と順序関係を分散管理し，Database as a Service（DBaaS）が注目されている．DBaaS

秘密計算技術 [4] によって暗号化データベースにおいてデータととはインターネットを介してデータベース機能を提供するク

クエリを秘匿しつつ索引検索を実現する Oblivious Secure In-

ラウドコンピューティングサービスで，Amazon Relationaldex Traversal（OSIT）フレームワークを提案している [16,17]．

Database Service [1]，Google Cloud Bigtable [2] などが有名

OSIT では，まず索引を暗号化してクライアントとサーバで分である．データ提供者にとって DBaaS によるデータ提供は，

散管理する．これにより，クライアントは検索対象の属性値にサーバの購入や DBMS の構築に加え，バックグラウンドのデー

基づく各レコードの順序関係を知っており, サーバは各レコー

タベース保守を委託できるという利点がある．

ドの属性値を暗号化した情報を知っていることになる．データ

しかしながら，格納データや検索クエリにはしばしば機密情を検索する際は，クライアントは自身の所有する索引を m 分

報が含まれており，DBaaS のようにデータベース管理を第三探索して，クエリ条件に該当するレコードを発見する．ただし，者に委託する場合には注意が必要となる．管理者はデータベー

クライアントとサーバはそれぞれ不完全な状態で索引を所有しス内のデータやクエリログを自由に閲覧できるため，利用者のており，各レコードの属性値に関する情報をもたないクライア

プライバシを侵害する恐れがあるからである．

ント単独では索引を探索できない．そこで，クライアントはク

信頼できない管理者にデータやクエリを秘匿する手法としエリと比較したいレコードの属性値をサーバに問い合わせ，秘て暗号化データベースが提案されている [7, 12]．暗号化データ

密計算を用いたプロトコルによって双方の索引の情報を明かさベースでは検索可能暗号を利用することにより，格納データをずにそれらの大小関係を比較する．

暗号化したままで管理や検索が可能にしている．しかし，暗号

しかし，サーバ管理者はクライアントからのアクセスログに化データベースにおける検索処理は時間計算量が大きく，デー

基づいて検索対象の属性値に基づく各レコードの順序関係をタへの高速なアクセスの保障を損ねてしまうため，データ提推測できてしまう．そこで本研究では，アクセスログから各レ供への応用には適さない．そこで本研究では，DBaaS によるコードの順序関係を推測できない索引探索手法を提案する．

データ提供事例を想定し，高速な検索処理が可能な暗号化デー
タベースの実現を目指す．

本論文の構成は以下の通りである．まず，第 2 節で関連する研究について述べる．第 3 節で提案手法を説明する上で必要と索引（index）は，データベースのアクセス効率の向上に有なる前提知識を，第 4 節で OSIT フレームワークを紹介する．

効であるが，暗号化データベースのようにデータの内容を秘匿

第 5 節で提案手法について述べ，第 6 節で評価実験について述したい場合には妨げとなってしまいかねない．例えば，B+木

べる．最後に，第 7 節で本稿のまとめと今後の課題を述べる．

索引の最下層ではキー値の順序を保存した並びで全データが格納されている．ここで，キー値自体が暗号化されていたとして

2. 関 連 研 究も，平文時の順序関係が保持されていると，一部のキー値の平暗号化データベースは，格納データを暗号化したままで管文値が漏洩した場合に残りのキー値の平文値を推測されやすく

理や検索が可能なシステムで，2002 年に Hacigümüş ら [7] になることが指摘されている [5]．検索にかかる時間が短縮でき

よって提案されて以来，現在までに多くの研究がなされている．

[7] では，予め格納データを一定の範囲ごとに分割してからが望ましい．

暗号化しておき，サーバで分割データに対する検索を行ない，3. 1. 1 データプライバシ

クライアントで検索結果を復号して精査する検索手法が提案さデータの機密を秘匿したいという要求をデータプライバシとれている．また，Hore らによってデータ値の統計的推測が困呼ぶ．DBaaS を利用する際，データ提供者が自身の資産である

難な分割データの生成手法が後に提案されている [8]．

データをサーバ管理者に秘匿したいと考えることは自然である．

初期の暗号化データベースでは集約演算を始めとした復号

また，データ提供を行なう際には，課金対象とならないデータを必要とする検索に対応できなかったが，Mykletun ら [10] やに関する情報をクライアントになるべく与えたくないと考える

Ge ら [6] は準同型暗号スキームを利用し，集約演算や k–近傍であろう．

探索に対応した暗号化データベースを実現した．さらに 2011

3. 1. 2 クエリプライバシ

年には，Popa がこれらの手法を組み合わせ，より複雑な検索クエリの機密を秘匿したいという要求をクエリプライバシとに対応できる暗号化データベース CryptDB [12] を提案した．

呼ぶ．サーバ管理者はクエリログを自由に閲覧できるため，過CryptDB では，RND や DET 暗号，Paillier 暗号 [11] などの去に発行されたクエリの内容から興味関心や行動履歴といった複数の暗号化スキームを用いて，格納データを多層的に暗号化

クライアント個人に関する情報を把握し得る．このような個人する．この多層的な暗号化により，格納データの機密性を保証

情報の漏洩を恐れて，クライアントは発行したクエリの内容をするとともに，各暗号化スキーム層ごとに選択・射影・結合・集サーバ管理者に秘匿したいと考えることがある．

約といった異なる演算をサポートすることができる．CryptDB

3. 1. 3 攻撃者モデル

はオープンソースパッケージとして公開されており，今なお実本研究では，攻撃者としてサーバ管理者とクライアントを想用的な暗号化データベースとして大いに注目されている．ま定する．サーバ管理者が攻撃者である場合，攻撃者は格納デー

た，Stephen らにより CryptDB の検索処理最適機構を改良しタの内容やクライアントの個人情報を入手しようとする．クラた Monomi [13] が提案されている．

イアントが攻撃者である場合，攻撃者は不正な問合せを行なう

2. 1 秘密計算を利用した索引検索手法

ことで課金対象とならないようにデータを取得しようとする．

CryptDB などの多くの暗号化データベースでは，暗号化さいずれの攻撃者も semi-honest モデルとして扱い，サーバ管理

れたすべてのデータとクエリとを一つ一つ照合して検索を行な者とクライアントは結託しないものとする．

うため，大量のデータを扱う場合に時間計算量が大きくなって

3. 2 加法準同型暗号

しまう．この問題に対し，一般的なデータベースと同様に索引

平文 m1 , m2 の暗号文 E(m1 ), E(m2 ) が与えられたとき，平

検索（Index Search）が実現できれば，パフォーマンスの向上

文や秘密鍵なしに E(m1 + m2 ) を導出できる性質を加法準同型を見込むことができる．しかし，暗号化データベースで索引検性といい，加法準同型性をもつ暗号を加法準同型暗号という．

索を実現するためには，格納データの秘匿性を低下させずに暗加法準同型暗号には lifted-Elgamal 暗号や Paillier 暗号 [11] な号化されたデータとクエリを比較しなければならない．

どがあり，本稿では Paillier 暗号を使用する．

これに対して，Wang ら [14] は R 木に非対称内積保存暗号ス
キーム [15] を R 木に適用して暗号化されたデータからクエリの近傍点を発見するアルゴリズムを提案し，これを用いて暗号

3. 2. 1 Paillier 暗号
Paillier 暗号は，以下の 4 つの機能（鍵生成・暗号化・復号・準同型演算）を有する．

化データベース上で索引による多次元範囲検索を実現している． ［鍵生成］秘密鍵 sk = (p, q) および公開鍵 pk = (n, g) を生成す
る．p, q は任意に選ばれた大きな素数で，n はそれらの積である．
また，Hu らの Oblivious Index Traversal フレームワーク [9]では，暗号化データベースを対象に B+木による索引検索を実

g は，任意に選ばれた k ∈ Zn に対して，g = 1 + kn mod n2

現している．この手法では，索引の各エントリを Paillier 暗号を満たす値である．

で暗号化しておき，クライアントとサーバが協力して暗号化さ［暗号化］平文 m と公開鍵 pk を入力として，暗号文 E(m) =れたエントリとクエリの大小関係を秘密計算 [4] する．

g m · rn mod n2 を出力する．ただし，r は r ∈ Z∗n2 を満たす乱3. 事 前 準 備
3. 1 DBaaS によるデータ提供
本研究では DBaaS によるデータ提供事例を，データ提供者，数である．この r により二つの同じ平文から必ずしも同じ暗号文が生成されるとは限らない．
［復号］暗号文 E(m) と秘密鍵 sk を入力として，平文 m を出力する．

サーバ管理者，クライアントで成立するモデルとして扱う．デー［準同型演算 1］二つの暗号文 E(m), E(m′ ) を入力として，暗タ提供者は，DBaaS で利用可能なクラウド上のデータベース

号文 E(m + m′ ) を出力する．E(m′ ) = g m · sn mod n2 としで，収集・解析したデータを管理する．サーバ管理者は，デーて，E(m + m′ ) は式 1 のように計算できる．

タ提供者に代わってバックグラウンドのデータベース管理を行E(m) · E(m′ ) = g m+m · (r · s)n mod n2 = E(m + m′ ) (1)なう．クライアントは，クエリ q をデータベースに問い合わせ，
取得したデータ量に応じてデータ提供者に課金する．

DBaaS によるデータ提供では，データ提供者のデータプラ
イバシ及びクライアントのクエリプライバシが保証されること′′［準同型演算 2］暗号文 E(m) と定数 a を入力として，暗号文

E(am) を出力する．E(am) は式 2 のように計算できる．
E(m)a = g am · rn mod n2 = E(am)(2)

Algorithm 1 ObliviousSecureIndexT raversal (client side)

4. OSIT フレームワーク

Require: N, h(·), min, max

本節では，索引を用いて効率的に暗号化データベースを検索

Ensure: クエリに該当するレコード集合 Result = Q(min, max)

するための Oblivious Secure Index Traversal（OSIT）フレー

1: Result ⇐ {}ムワークを紹介する．本フレームワークの主要な特徴として，

2: imin ⇐ getRecordIndex(N, min,“<=”)データ提供者は検索のための索引を構築し，それをサーバとク
ライアントで分散管理する．また，秘密計算を用いたプロトコ

3: imax ⇐ getRecordIndex(N, max,“>”)
4: for i : imin to imax do
5:h(i) に対応する E(ri ) を取得

6:ri ⇐ D(E(ri ))4. 1 問 題 定 義

7:Result.add(ri )暗号化データベース D = {ri } に関して，レコード ri =8: end forルによって双方の索引の情報を明かさずに索引検索を実現する．

(A1 , A2 , ..., Aj )，検索対象となる数値属性を A とする．また，クライアントが発行できるクエリを A に対する範囲検索クエ

Algorithm 2 getRecordIndex (client side)

リ Q とし，式 3 で定義する．クライアントは検索範囲の下限

Require: N , クエリ条件値 q, クエリタイプ type

値 min 及び上限値 max を指定すると，範囲内に A 値が収まるようなすべてのレコードを取得できる．

Q(min, max) := {ri ∈ D|min <= ri .A <= max}

Ensure: 該当するレコードのインデックス iq
1: iq ⇐ null
2: 探索領域 (l, u) ⇐ (1, N )(3)

3: E(q) をサーバに送信
4: while l < (u − 1) do

本研究では，D, min, max が与えられたとき，Q を高速に回

5:(l, u) を m 分割する i を (m − 1) 個選択

答するという問題を考察する．ただし，3. 1 節で示したプライ

6:

h(i1 ), h(i2 ), ..., h(im−1 ) をサーバに送信バシを保証するために，Q を導出する際には以下の三つの要件

7:

procedure at server
for j : i1 to im−1 do

8:を満たさなければならない．
要件 1 — サーバ管理者は，データベースに格納されているデー

9:h(j) に対応する E(ej ) を取得

10:

E(c) ⇐ {E(ej ) · E(q)−1 }r

タの内容を推測できない．

11:

要件 2 — サーバ管理者は，クエリ内容を推測できない．

12:

end for要件 3 — クライアントは，発行したクエリ条件に該当しない

13:

end procedure

レコードの情報を得られない．

14:

E(c1 ), E(c2 ), ..., E(cm−1 ) を復号

15:

c1 , c2 , ..., cm−1 に基づき (l, u) を更新

4. 2 暗号化索引
OSIT フレームワークでは索引に起因する情報漏洩を防ぐた
めに，暗号化索引の構築ならびにクライアントとサーバによる

16: end while
17: if l =| N or u =| 1 then18:

暗号化索引の分散管理する．以降では，OSIT フレームワーク

19:で使用する索引を暗号化索引と呼ぶ．

20:

4. 2. 1 索引のデータ構造

21:

暗号化データベース D に対する暗号化索引 I を，キー i とエ22:

ントリ ⟨E(ei ), E(ri )⟩ を紐付けるハッシュ索引とし，式 4 で定E(c) をクライアントに送信

if type is “<=” theniq ⇐ uelse if type is “>” theniq ⇐ lend if

23: end if

義する．ただし，ei はレコード ri 中の属性 A の値であり（つまり ei = ri .A），i は全レコードを e の順に並べたときのイン管理するために，I を順序情報 SI とエントリ情報 EI に分離

デックスを表す．

する．SI, EI をそれぞれ式 5，式 6 で定義する．

I : i → h(i) → ⟨E(ei ), E(ri )⟩+(4)

E(·) は暗号化関数を表し，ei は加法準同型暗号スキームで，riSI : i → h(i)EI : h(i) → ⟨E(ei ), E(ri )⟩

(5)
+

(6)

は任意の暗号化スキームでそれぞれ暗号化されているものとす

ここでは，i と h(i) の対応を SI としてクライアントに配置する．ここで，暗号化索引のサイズ |I| = N とする．

る．一方，h(i) と ⟨E(ei ), E(ri )⟩+ の対応を EI としてサーバ

4. 2. 2 索引の構築と配置に配置する．⟨E(ei ), E(ri )⟩+ について，集合自体を 1 つのデー

暗号化索引の構築と配置は，データ提供者が予め行なう．

タとして暗号化することで E(ei ) が同じ値をとるレコード数もデータ提供者は最初に全レコードについて ⟨ei , ri ⟩ のペアをサーバに秘匿することができる．

列挙し，e の値が小さい順に並べたときのインデックス i を求

4. 3 索引検索アルゴリズム

める．そして，⟨E(ei ), E(ri )⟩ を計算して，ハッシュテーブル

分散配置された暗号化索引 I の探索を含む検索全体の流れをの h(i) をキーとするエントリに割り当てる．このとき，i の衝

Algorithm1 に記す．一般的なデータベースでは索引をサーバ突が発生しないようにハッシュ関数 h(·) を設定する．
続いて，構築した暗号化索引をクライアントとサーバで分散側で探索するが，OSIT フレームワークでは I をクライアント
側で探索する．ここで，クライアントはデータ提供者から I の構築時に使用した暗号化スキームの暗号化関数 E(·) 及び対応

セスするエントリの選択規則の改善手法を提案する．

する復号関数 D(·) を事前に与えられているものとする．クラ5. 1 アクセスするエントリの選択規則の改善

イアントは，クエリ条件 [min, max) を指定して I を探索する提案手法では，クライアントは暗号化索引を m 分探索する

ことで，min より大きい最小の A 値をとるレコードのインデッ

ために，1 往復の通信ラウンドで k 個のエントリにアクセスすクス imin と，max より小さい最大の A 値をとるレコードのイ

る．ただし，k は後述する式 16 に基いて決定される．

ンデックス imax を発見する．ただし，I のエントリ情報 EI を

まず初回の問合せでは，クライアントはランダムに選択し知らないため単独では探索ができないので，EI をもつサーバ

た k 個のエントリにアクセスする．ただし，k 個のエントリと協力して探索を実行する．最後に，imin 番目から imax 番目

は重複を許す．ここで得られた各エントリとクエリの大小関係のレコードをサーバに問い合わせ，結果を復号することでクエ

E(c1 ), E(c2 ), ..., E(ck ) を基に，2 回目以降の問合せで m 分探リに該当するレコード集合 Q(min, max) を得られる．

索する索引領域 (l, u) を決定する．これにより，クライアント

分散配置された暗号化索引 I を探索するための秘密計算プ

は検索時に毎回異なる索引領域を m 分探索することになる．

ロトコルを Algorithm2 に記す．I を探索するには，サーバで2 回目以降の問合せでは，クライアントは (l, u) を m 分割管理される属性値 e とクライアントが指定するクエリの条件する m − 1 個のエントリに加え，(l, u) 外の索引領域からラン

値 q の大小を比較する必要が生じる．クライアントもサーバ

ダムに k − (m − 1) 個のエントリを選択して，サーバにクエも互いに自身のもつ値を明かしたくないので，両者が協力しリとの大小関係を問い合わせる．ランダムに選択されるエンて秘密計算をして大小関係を導出する．このプロトコルは，

トリにもアクセスすることで，m 分探索のためにアクセスさクライアントが ei , q の大小関係を知るためには，ei − q の正れたエントリをサーバに分からなくしている．なお，得られ負が分かればよいというアイディアに基づく．まず，4. 1 節る E(c1 ), E(c2 ), ..., E(cm−1 ), ..., E(ck ) のうち，ランダムに選の要件 2 を満たすために q を暗号化した上でサーバに送信す択したエントリとの大小関係は (l, u) の更新に影響しないためる．次に，索引の探索領域 (l, u) 内で比較したいエントリを復号処理を省略できる．

(m − 1) 個選択し，h(i1 ), h(i2 ), ..., h(im−1 ) をサーバに送信す

5. 2 安全性評価

る．サーバでは h(i) に対応するエントリの E(ei ) を取り出し，提案手法を用いた場合，クライアントからのアクセスログにE(c) = {E(ej ) · E(q)−1 r

} を計算する．Paillier 暗号は加法準同型性をもつため，この結果は E(r(ei − q)) となる．なお，クライアントに E(ei − q) を明かしてしまうと ei が知られてしまって要件 3 を満たさないので，E(ei − q) に乱数 r を掛けて正確な差を分からなくしている．ただし，真の差とで正負が反基づきサーバ管理者がエントリの順序を推測できないことを示す．
まず，索引としてソートされた配列 A を考える．

A = (e1 , ..., ei , ..., eN )(7)

転しないよう r は正値とする．クライアントはサーバから返さ∀i∀j, i < j ならば ei < ej

れた E(c) を復号すると，c の正負から比較したいエントリとA に対して，ei の値を暗号化し，A 上での順序関係がわからな

クエリの大小関係を得られる．

いようにした集合を A′ として式 8 で示す．

5. サーバでの平文値推測の防止

A′ = {e′1 , e′2 , ..., e′N }(8)

OSIT フレームワークでは暗号化索引の順序情報とエントリ

ここで，e′i は配列 A 上のいずれかのエントリを暗号化したも情報を分散管理することで，暗号化されたエントリそのものとのであり，A と A′ 間で各エントリの添字の順序には関係がな

平文時の順序関係を共存させないようにしていた．しかし，クい．以降では，A′ はサーバで管理されるものとする．

ライアントがどのエントリにアクセスしたかを知ることができ

任意の e′ ∈ A′ について，e′ を復号したエントリが A 上のどる．サーバ側で順序関係を推測できてしまう．

の位置であっても同様に確からしいとき，1 <=j<= N のすべて［例 1］クライアントはサイズ N の暗号化索引を二分探索する

1の j に対して e′ が ej を暗号化したものである確率は N
であとする．まず最初に，クライアントは索引中央に位置するエンる．これと同等であれば A 上の位置を知ることができないとみ

トリ e 1 N にアクセスする．このときサーバでは，クライアン

なせる．このことを根拠として，定義 1 を導く．

トが二分探索を開始した直後であると考えると，e 1 N が索引の［定義 1］（エントリの位置推測の防止）クライアントがアクセ

1
N 番目に位置すると推測できる．次に，クライアントはエン
2

スしたエントリリスト AccessLog を式 9 とする．

2

2

トリ e 1 N にアクセスするとする．このときサーバでは，クラ4

イアントが二分探索を行っていることを考えると，e 1 N が索引
4

AccessLog = (e′q1 , ..., e′qk |e′qi ∈ A′ )(9)の 14 N 番目あるいは 34 N 番目のいずれかに位置すると推測で

ここで e′ ∈ AccessLog が，あるエントリ ei ∈ A を暗号化した

きる（サーバは e 1 N とクエリの大小関係を知ることはできな

1ものである確率が，1 <= N のすべての i において高々 N で=i<

いため，これ以上の絞り込みはできない）．

あるとき，サーバ管理者は e′ の A 上での位置を推測できない．

2

文献 [5] で指摘されている通り，サーバにエントリ値の順序［定理 1］（提案手法によるエントリの位置推測の防止）提案手関係を知られてしまうと，たとえエントリ値が暗号化されてい法において，サーバ管理者は AccessLog に含まれる任意のエたとしても選択平文攻撃に弱くなる．この問題に対して，アクントリ e′ に対し，A 上での位置を推測できない．

証明. 提案手法ではクライアントが 1 往復の通信ラウンドで k

5. 3 コストモデルの導出

個のエントリにアクセスする．以降の議論では，クライアント

本節では，提案手法によって暗号化索引を m 分探索する際がアクセスしたエントリ e′j ∈ A′ が ei ∈ A を暗号化したものに，最適な m を決定するための索引探索のコストモデルを提である確率を P (e′j , ei ) で表す．

案する．

1 ラウンド目はランダムに選択したエントリにアクセスする

本稿では，（ tcomm , tcomp , tdec ）をそれぞれ，1 往復の通信

ので，e′q1 , e′q2 ..., e′qk ∈ AccessLog について，e′qj があるエントに必要なコスト，1 個のレコードとクエリの比較に必要な秘密

リ ei ∈ A を暗号化したものである確率は式 10 の通りである．

計算のコスト，1 個の暗号化された比較結果の復号に必要なコ

1
P (e′qj , ei ) =Nストとし，1 往復の通信による 1 個のレコードとクエリの比較(10)

コストを定義 2 に示す．

続いて，2 ラウンド目以降のアクセスについて考える．2 ラ［定義 2］（1 往復の通信ラウンドによる単一エントリとクエリ

ウンド目以降は，1 ラウンド目で決定された探索領域を m 分探の比較コスト）1 往復の通信に必要な通信コストが tcomm であ索するようにエントリを選択する．まず通常の手法で A を m

り，1 個のエントリとクエリの比較に必要な秘密計算コストが分探索をする場合を考える．A の e1 から eN の間で均等な位置

tcomp ，1 個の暗号化された比較結果の復号コストが tdec であにある m − 1 個のエントリ e⌈ N i⌉ (1 <= m − 1) にアクセス=i<m

する．そのため，e′j (1 <= m − 1) が e⌈ N i⌉ (1 <=j<
= m − 1)=i<mである確率は式 11 で表される．

∀i∀j ∈ [1, m − 1], P (e′j , e⌈ N i⌉ ) =
m

1
1
>
m
N

探索する領域が狭められている上に領域の開始位置がランダムに決められているためサーバ側には探索領域がわからない．そのため，2 ラウンド目で ei (1 <=i<
= N ) を暗号化したものにアクセスした確率を考えるには，すべてのあらゆる探索領域（考え得るすべての領域長，開始位置）で m 分探索することを考える必要がある．このとき，P (e′ , ei ) は式 12 で表される．

P (e′ , ei )

(12)
=

m−1
1
k N −m+2

l=m−1

1
N −l+1N∑−l+1f (l, s, i)e′ =1

ここで f (l, s, i) は，探索領域の領域長を l，開始位置を s としたとき，領域を m 分割する分岐点が均等になる部分の確率が1となることを表す．
m−1{

f (l, s, i) =式 12 中のCost = tcomm + tcomp + tdec

(17)

提案手法で暗号化索引を m 分探索する場合，1 往復の通信
ラウンドで k 個のエントリとクエリを比較する．このとき，初回の問合せではランダムに選択したエントリすべてとクエリの比較結果を得たいので，tcomm , tcomp , tdec は送信エントリ数 kに依存する．ところが，2 回目以降の問合せでは m 分探索に必要なエントリとクエリの比較結果のみを得られればよいので，

tcomm , tcomp は送信エントリ数 k に，tdec は m 分探索のための比較エントリ数 m − 1 に依存する．よって，定義 2 に従って

1 往復の通信ラウンドによる k 個のエントリとクエリの比較コストを定理 2 に示す．
［定理 2］（1 往復の通信ラウンドによる k 個のエントリとクエ
リの比較コスト）提案手法により暗号化索引を m 分探索する
場合，1 往復の通信ラウンドによる k 個のエントリとクエリの比較コストは式 18 のようになる．ただし，式中の m は 2 <
=m
とする．

1
m−1

if i = ml j + s (∃j, 1 <=j<= m − 1)0

if otherwise

N∑
−l+1

の比較コスト Cost を式 17 で定義する．

(11)

ところで，提案手法の 2 ラウンド目の場合は 1 ラウンド目でN∑るとき，1 往復の通信ラウンドによる 1 個のエントリとクエリ

Costf irst (m, k) = k(tcomm + tcomp + tdec )(18)

Costotherwise (m, k) = k(tcomm + tcomp ) + (m − 1)tdec′

f (l, e , i) は，m 分探索する領域のスタート

e′ =1

1
地点を 1 から N − l に動かす間に m − 1 回 f (l, e′ , i) が m−1提案手法では初回の通信ラウンドでエントリをランダムに選択し，それらの比較結果に基づいて決定された索引領域をになるときを最大値にとる．すべての広さの探索範囲でこうな

2 回目以降の通信ラウンドで m 分探索する．故に検索毎に mることはないが，上限として以下の値を設定できる．

分探索する索引領域の広さが変化するが，ここでは説明を簡N∑
1
1
N −m+2N −l+1l=m−1∫ N −m+2
11<dx= N −m+2x
1

P (e′ , ei ) <==log(N − m + 2)
N −m+2単にするために初回の通信ラウンドで均等にエントリを選択(13)

して 2 回目以降の通信ラウンドで m 分探索する索引領域の広さを固定してコストモデルを導出する．暗号化索引のサイ(14)ズが N であるとき，2 回目以降の索引探索に必要な通信ラウ
ンド数は ⌈log(N − k)/log(m)⌉ であるので，2 回目以降の探(15)

索開始から終了までの比較コストは Costotherwise (m, k) に

ここで，k の値が式 16 を満たせば，提案手法における 2 サイ⌈log(N + 1)/log(m)⌉ をかけたものになる．これを提案手法の1
クル目以降のアクセスで P (e′j , ei ) <= N

検索コストモデルとし，定理 3 に示す．

となる．

N (m − 1) log(N − m + 2)
(16)
N −m+2
1
以上から，提案手法で常に P (ej′ , ei ) <が成立する．
=k>=N［定理 3］（提案手法のコストモデル）探索対象の暗号化索引のサイズが N であるとき，提案手法における検索コストモデル
は，最悪のケースで上限として式 19 のようになる．

図 1 各エントリのアクセス確率の比較

TotalCost(N, m, k)

図 2 クエリ応答時間の実測値とコストモデルによる理論値の比較(19)= Costf irst (m, k)+ ⌈log(N − k)/log(m)⌉Costotherwise (m, k)

応答時間について，実測値と理論値を比較する．また，k は式

16 に基づいて設定した．実測値は，索引サイズ N = 100, 000のデータセットに対して各 m ごとに 10 回ずつ検索を行ない，平均クエリ応答時間を算出した．比較結果を図 2 に示す．実測

5. 4 各種パラメータの決定

値と理論値の傾向がほぼ一致しており，式 19 で定めたコスト提案手法では，式 16 ならびに式 19 に基づいて k, m を決定

モデルが妥当であると言える．また，m = 2 のときにクエリ応する．クライアントは，まず式 16 から様々な m に対する k の下限値を得る．続いて，（ tcomm , tcomp , tdec ）と先程導出した

答時間が最短となっていることがわかる．

7. お わ り にm, k の組合せのうち式 19 が最小となる m, k を得る．
本稿では，Oblivious Secure Index Traversal（OSIT）フレー

6. 評 価 実 験

ムワークにおいて，サーバ管理者による格納データ（暗号文）

6. 1 実 験 設 定の平文値推測の防止を目的とし，アクセスログからデータ間のすべての実験は，Mac OS X，Intel Core i5 @ 1.70GHz

順序関係を推測できない索引探索手法を提案した．続いて，提CPU，4GB RAM で構成されたマシン（クライアント端末）

案手法によってサーバ管理者がアクセスログを利用して暗号化と，Ubuntu 12.04，Intel Xeon L563 @ 2.13GHz CPU，2GBされたエントリの平文時の順序関係を推測することが困難であRAM で構成されたマシン（サーバ）を使用して実施した．プることを理論的および実験的に示した．また，提案手法のコス

ログラムは Java で実装し，JRE 64bit version 1.8 上で実行しトモデルを定義し，実験を通して妥当性を検証した．

た．なお，Paillier 暗号の実装は公開されているプログラム [3]を使用した．

今後の課題として，様々な索引サイズと通信環境の組み合わせにおけるクエリ応答時間の評価が挙げられる．提案手法では

6. 2 アクセスされるエントリの一様性の検証

格納データの秘匿性を確保するため，クライアントは実際の探提案手法における各エントリのアクセス確率を検証する．本索に必要なエントリ以外にも複数のエントリについてサーバに実験では，m = 2 とした場合の各エントリのアクセス確率に問い合わせなければならない．問い合わせるべきエントリ数はついて，提案手法と通常の二分探索を比較する．各エントリの索引サイズに応じて増加するが，通信コストが大きい環境では

アクセス確率は，索引サイズ N = 100 のデータセットに対し現実的な時間で検索できなくなる可能性がある．

て，様々なクエリごとに 50 回ずつ検索を行ない，そのときの謝辞

アクセス回数から算出した．なお，式 16 に基づき，k = 10 と設定した．比較結果を図 1 に示す．通常の二分探索では二分木

本研究の一部は JSPS 科研費 基盤研究 (C) JP16K00149 おのようなプロットが得られ，提案手法ではより水平に近い線がよび 平成 28 年度共同研究（SKY 株式会社） (CPE27116K)

プロットされた．

「機械学習の適用による SKYSEA Client View のログ及び資産

6. 3 コストモデルの妥当性の検証

情報からの例外的状況の自動検出」の助成を受けたものです．

様々な m に対するクエリ応答時間を実際に測定して，提案したコストモデルの妥当性を検証する．ここで，本実験環境下
では tcomm は 9.60 ミリ秒，tcomp は 0.02 ミリ秒，tdec は 0.08
ミリ秒となっており，これに基づいて式 19 から様々な m に対するクエリ応答時間の理論値を算出する．
本実験では，m を 2 から 40 の間で変化させたときのクエリ

文

献[1] Amazon Relational Database Service.
https://aws.
amazon.com/rds/.
[2] Google Cloud Bigtable.
https://cloud.google.com/
bigtable/.
[3] Google Code Archive (thep). https://code.google.com/

archive/p/thep/.
[4] Ian F Blake and Vladimir Kolesnikov. Strong conditional
oblivious transfer and computing on intervals. In International Conference on the Theory and Application of Cryptology and Information Security, pp. 515–529. Springer,
2004.
[5] Alexandra Boldyreva, Nathan Chenette, Younho Lee,
AdamO neill. Order-preserving symmetric encryption. In
Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 224–241. Springer,
2009.
[6] Tingjian Ge and Stan Zdonik. Answering aggregation
queries in a secure system model. In Proceedings of the
33rd international conference on Very large data bases, pp.
519–530. VLDB Endowment, 2007.
[7] Hakan Hacigümüş, Bala Iyer, Chen Li, and Sharad Mehrotra. Executing sql over encrypted data in the databaseservice-provider model. In Proceedings of the 2002 ACM
SIGMOD international conference on Management of data,
pp. 216–227. ACM, 2002.
[8] Bijit Hore, Sharad Mehrotra, and Gene Tsudik. A privacypreserving index for range queries. In Proceedings of theThirtieth international conference on Very large data basesVolume 30, pp. 720–731. VLDB Endowment, 2004.
[9] Haibo Hu, Jianliang Xu, Xizhong Xu, Kexin Pei, Byron
Choi, and Shuigeng Zhou. Private search on key-value storeswith hierarchical indexes. In 2014 IEEE 30th International
Conference on Data Engineering, pp. 628–639. IEEE, 2014.
[10] Einar Mykletun and Gene Tsudik. Aggregation queries inthe database-as-a-service model. In IFIP Annual Conference on Data and Applications Security and Privacy, pp.
89–103. Springer, 2006.
[11] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In International Conference on the Theory and Applications of Cryptographic
Techniques, pp. 223–238. Springer, 1999.
[12] Raluca Ada Popa, Catherine Redfield, Nickolai Zeldovich,and Hari Balakrishnan. Cryptdb: processing queries on an
encrypted database. Communications of the ACM, Vol. 55,
No. 9, pp. 103–111, 2012.
[13] Stephen Tu, M Frans Kaashoek, Samuel Madden, and Nickolai Zeldovich. Processing analytical queries over encrypted
data. In Proceedings of the VLDB Endowment, Vol. 6, pp.
289–300. VLDB Endowment, 2013.
[14] Peng Wang and Chinya V Ravishankar. Secure and eﬃcient
range queries on outsourced databases using rp-trees. In
Data Engineering (ICDE), 2013 IEEE 29th International
Conference on, pp. 314–325. IEEE, 2013.
[15] Wai Kit Wong, David Wai-lok Cheung, Ben Kao, and Nikos
Mamoulis. Secure knn computation on encrypted databases.
In Proceedings of the 2009 ACM SIGMOD International
Conference on Management of data, pp. 139–152. ACM,
2009.
[16] 篠塚千愛, 渡辺知恵美, 北川博之. Daas におけるデータとクエ
リ双方のプライバシー保護を実現する効率的な秘匿検索. 第 7
回データ工学と情報マネジメントに関するフォーラム（DEIM
フォーラム 2015）, 2015.
[17] 篠塚千愛, 渡辺知恵美, 北川博之. 秘密計算による秘匿検索フレー
ムワーク osit-bs における検索コストと最適化. 第 8 回データ
工学と情報マネジメントに関するフォーラム（DEIM フォーラ
ム 2016）, 2016.