DEIM Forum 2016 F5-6

秘密計算による秘匿検索フレームワーク OSIT における検索コストと最適化
篠塚千愛†

渡辺知恵美††

北川 博之††† 筑波大学システム情報工学研究科 〒 305–8573 つくば市天王台 1–1–1†† 筑波大学システム情報系 〒 305–8573 つくば市天王台 1–1–1
E-mail: †sn@kde.cs.tsukuba.ac.jp, ††{chiemi,kitagawa}@cs.tsukuba.ac.jp
あらまし

クラウドデータベース（DBaaS）を利用したデータ提供サービスが普及しつつある．しかし，DBaaS 管理者へのデータやクエリの漏洩はデータ提供者やサービス利用者のプライバシ侵害となり，DBaaS におけるデータやクエリの秘匿は重要な課題である．加えて，データ提供サービスとして高速な処理性能も要求される．我々はこれまでにデータとクエリを秘匿したまま高速な検索処理を可能にするフレームワーク OSIT を提案している．OSIT では秘密計算を利用したプロトコルで検索用索引を探索するが，索引の 1 回のエントリ探索にサービス利用者の端末とデータベース間で通信することを想定しており，その最適な探索法として二分探索を採用している．本稿では先行研究を拡張して，複数エントリを同時に探索する手法とその検索コスト式を提案する．また，提案する検索コスト式に基づ
き，同時に探索するエントリ数の最適値を求め，妥当性を実験にて評価する．
キーワード

プライバシ保護，秘匿検索，Database as a Service

1. は じ め にた，索引の各エントリとクエリの比較は，クライアントとサーバ間で秘密計算を行なう．OSIT フレームワークによる検索処

クラウド型データベースサービス（DBaaS）が様々なプロパ

理は，信頼できない DBaaS 管理者に対してデータとクエリ双イダから提供され，DBaaS を利用したデータ提供サービスが普方を秘匿できるものの，各エントリの比較のたびに発生する秘及しつつある．データベース管理を DBaaS 管理者に委託でき，

密計算コストが大きく，データ提供サービスへの適用が現実的

低コストにデータ提供サービスを提供できることから注目されではない．

ている．しかし，提供データや検索クエリにはしばしば機密情

そこで，本研究では OSIT フレームワークの安全性を低下さ報が含まれており，第三者である DBaaS 管理者への委託にはせずに索引の探索コストを削減し，検索処理の効率性の向上さ注意が必要となる．DBaaS 管理者はデータベース中のデータせる．まず，OSIT フレームワークの索引探索アルゴリズムをやクエリログを自由に閲覧できるため，データやクエリの機密拡張手法を提案する．OSIT フレームワークでは，索引の一つ

情報を侵害する恐れがあるからである．そこで，DBaaS を利のエントリに対する秘密計算につき，クライアントとサーバ間用したデータ提供サービスでは，DBaaS 管理者に対してデーで一往復の通信を必要とする．しかしながら，複数のエントリ

タとクエリの内容を秘匿可能な検索処理技術が求められる．

の秘密計算を一往復の通信で行なったとしても，安全性は低下

信頼できないデータベース管理者に対してデータやクエリのしない．続いて，一往復の通信で比較を行なうエントリ数の最内容を秘匿可能な検索処理技術として，データベース暗号化 [6]

適値を決定するために，拡張した OSIT フレームワークにおけがある．これは，データを検索可能暗号スキームで暗号化した

るコストモデルを提案する．また，提案するコストモデルの実状態でデータベースに格納し，復号化せずに問合せ処理を行な

験的評価を行ない，妥当性を検証した．

うことによって，格納データやクエリログに含まれる機密情報

本稿の構成は以下の通りである．2 節で本研究に関連する研を秘匿する方法である．データベース暗号化は非常に高い安全究を紹介する．3 節で本研究の問題設定を，4 節で前提となる性を保証するものの，検索時には暗号化された全てのレコード

事項を説明する．5 節で OSIT フレームワークについて述べる．

とクエリとを一つ一つ照合しなければならず，検索処理の効率

6 節で OSIT フレームワークの拡張手法とコストモデルを提案

性は低い．大量のレコードを扱う場合には，検索対象のレコー

する．7 節でコストモデルの妥当性に関する評価実験の結果をド数に依存する検索コストが課題となる．

示す．8 節で本稿のまとめと今後の課題を述べる.

我々はこれまでに，データベース暗号化手法に索引を用いた検索処理を適用することで，効率的な秘匿検索を実現する

OSIT（Oblivious Secure Index Traversal）フレームワークを提案している [14]．OSIT フレームワークでは，データベース

2. 関 連 研 究
本節では，本研究に関連するデータベース暗号化に関する研究について言及する．

側にクエリの内容を秘匿するため，クライアント側で索引のデータベース暗号化は，信頼できないデータベース管理者に一部を所有しておき，クライアント自身が索引を探索する．ま対して格納データや検索クエリに含まれる機密情報を秘匿する

問合せを行ない，必要なデータを取得できる．

3. 2 プライバシ要件
DBaaS を利用したデータ提供サービスでは，データプライバ
シとクエリプライバシの二種類のプライバシ要件を満たすことが求められる．WPA2 キーデータの提供サービスを例として，
これらのプライバシを説明する．このサービスにおけるデータ
所有者は Wifi サービスプロバイダであり，DBaaS を利用して
図 1 データ管理と検索の流れ

クライアントに Wifi ホットスポットの WPA2 キーデータを提供する．DBaaS を利用することから，WPA2 キーデータベースの管理は DBaaS 管理者に委託されることになる．しかし，方法である．Hacigümüş らの研究 [6] を初めとして現在までに多くの研究 [7, 8, 11] が行なわれており，本研究でもデータベー
ス暗号化を用いてデータとクエリのプライバシを保証する．文献 [8] は，SQL データベースに対する適用方法を提案したものであり，文献 [7] は，XML データベースに対する適用方法を提案したものである．特に，CryptDB [11]，及び Monomi [12] は有名なデータベース暗号化手法である．CryptDB では，RND
や DET 暗号，Paillier 暗号などの複数の暗号化スキームを用いて格納データを多層的に暗号化することで，格納データの機密性を保証するとともに，各暗号化スキーム層毎に選択・射影・結合・集約といった異なる演算をサポートする．また，

Monomi [12] は CryptDB の検索処理最適機構を改良したものである．これらのデータベース暗号化手法は非常に高い安全性を保証するが，検索時には暗号化された全てのレコードとクエ
リとを一つ一つ照合しなければならいため，検索処理の効率性は低い．大量のレコードを扱う場合には，検索対象のレコード数に依存する検索コストが課題であった．
これに対して，データベース索引を用いた検索処理が可能であるデータベース暗号化手法が提案されてきた [9, 10]．文献 [9]では，B + 木索引を用いた検索処理が可能なデータベース暗号化フレームワーク OIT (Oblivious Index Traversal) が提案されている．また，文献 [10] では，非対称内積保存暗号を適用した索引を用いることで，暗号化されたデータベースに対して多次元範囲検索を実現するアルゴリズムが提案されている．しかしながら，これらの研究ではクライアントが格納データの属性情報や暗号化方式に関する知識を検索時に持っていることを想定している．一方，本研究が対象とする DBaaS を利用したデータ提供サービスでは，クライアントはそのような知識を持たないため，我々の想定する状況とは異なる．

3. 問 題 設 定
3. 1 DBaaS を利用したデータ提供サービス
データ提供サービスはデータ所有者が収集したデータや，それらを解析したデータに対する検索権限を販売するサービスを指す [13]．DBaaS を利用して提供される場合，データ所有者，

DBaaS 管理者，クライアントの三者により成立する．サービスモデルを図 1 に示す．データ所有者は，DBaaS 管理者にデー
タベース管理を委託し，データ提供サービスを提供する．また，クライアントにサービスの利用権限を与える．クライアントは，

DBaaS で提供されるデータベースに対してクエリを発行してWPA2 キーデータはデータ所有者の資産であるため，DBaaS
管理者に対して秘匿されることが望ましい．また，クライアン
トに対しても検索結果以上の WPA2 キーデータが秘匿されることが望ましい．このようなデータに関する秘匿要求がデータ
プライバシである．データプライバシを定義 1 に示す．
定義 1（データプライバシ）データ所有者は，提供データに含まれる機密情報を DBaaS 管理者に対して秘匿したい．また，
クライアントに対しても検索結果を除くデータを秘匿したい．
この要求をデータプライバシという．データベースは次の要件を満たせば，データプライバシを保証する．

•

DBaaS 管理者にデータ内容や推測の手がかりとなる情報を秘匿できる•

クライアントに検索結果以外のデータを与えない

一方，クライアントは接続したいスポットの WPA2 キーを問い合わせる．しかし，クエリはクライアントの位置情報を含
むため，DBaaS 管理者に対して秘匿されることが望ましい．このようなクエリに関する秘匿要求がクエリプライバシである．
クエリプライバシを定義 2 に示す．
定義 2（クエリプライバシ）クライアントは，クエリ含まれる機密情報を DBaaS 管理者に対して秘匿したい．この要求をク
エリプライバシという．データベースは次の要件を満たせば，クエリプライバシを保証する．

•

DBaaS 管理者にクエリ内容を秘匿できる

4. 基 本 事 項
4. 1 Paillier 暗号
Paillier 暗号 [1] はデータベース暗号化に用いられる準同型暗号スキームの一種である．平文 m と公開鍵 pk = (n, g) が与えられたときの暗号化関数 E(·) を式 (1) に示す．

E(m) = g m · rn mod n2(1)

ただし，r は n 以下のランダムなノイズである．これにより同じ平文であっても常に同じ暗号文が生成できるとは限らない．

Paillier 暗号は加法準同型性を有する．加法準同型性とは，二つの平文に対する加法演算を，それらの暗号文に対する演算に変換可能な性質である．この性質より，式 (2) のように共通の暗号鍵を用いて暗号化された二つの平文 m1 ，m2 の暗号文から

m1 + m2 の暗号文を計算できる．
E(m1 ) · E(m2 ) = (g m1 · r1n mod n2 ) · (g m2 · r2n mod n2 )= g m1 +m2 · (r1 · r2 )n mod n2= E(m1 + m2 )(2)

4. 2 GT–SCOT プロトコル
GT–SCOT (Strong Conditional Oblivious Transfer for“Greater Than” predicate) プロトコル [3] とは，ある条件に関する秘密計算のための条件付き紛失通信プロトコル [4] のうち，2 値の大小関係を条件としたものである．GT–SCOT プ
ロトコルによる紛失通信では，受信者と送信者は互いに相手の図 2 暗号化索引の分離・分散配置

持つ値を知らないままそれらの大小関係を計算できる．また，導出される大小関係は受信者のみが取得できる．

て，エントリの要素に付与する．つまり，配列の各エントリは受信者が値 x を持ち，送信者が値 y を持つとき，x, y の大小関係は以下のように導出する．まず，受信者は x < y である⟨id, key, val⟩ で構成される．次に，データ所有者は各エントリの key と val を加法準同型暗号 E(·) で暗号化する．以下では，ことを示す値 s0 ，及び x > y であることを示す値 s1 を決定す

この配列を暗号化索引と呼ぶ．なお，本稿では加法準同型暗号

る．次に，E(x), s0 , s1 を送信者に送信する．ただし，E(·) はに Paillier 暗号 [1] を使用する．

加法準同型暗号の暗号化関数である．本稿では，式 (1) を使用

続いて，暗号化索引をエントリに関する情報と構造に関するする．続いて，送信者は E(x), y, s0 , s1 に対して，E(s0 ) また

情報に分離する．分離のために，まずは暗号化索引の各エント

は E(s1 ) が得られる計算アルゴリズムを適用する．この計算アリの id をハッシュ関数 h(·) でハッシュ化する．その後，h(id)ルゴリズムを，GT–SCOT 関数として定義 3 に示す．
定義 3（GT–SCOT 関数）の値で再びエントリをソートする．id のハッシュ化後にエントリを再ソートすることで，エントリ間の順序関係を秘匿でき{

Gt–scot(E(x), y, s0 , s1 ) =E(s0 )

if x < yE(s1 )

if x > yる．このようにして得られた ⟨h(id), E(key), E(val)⟩ で構成さ(3)

れるエントリの配列を暗号化索引のエントリに関する情報とする．また，ハッシュ関数 h(·)，暗号化索引に含まれるエントリ

送信者は，式 (3) の計算結果を受信者に返す．受信者は，この計算結果を復号化することで，s0 もしくは s1 を取得でき，

x, y の大小関係が分かる．このように，受信者は y の値自体を知ることはできないが，x, y の大小関係を知ることができる．
一方，GT–SCOT 関数内では E(x) を復号化しないため，送信者は x の値自体を知ることはできない．また，式 (3) の結果は暗号化された状態で導出されることに加え，s0 , s1 は受信者により決定されることから，送信者は x, y の大小関係を知ることもできない．

5. OSIT フレームワーク

数 N ，各レコードの暗号化に用いた暗号鍵，及びそれに対応する復号鍵を暗号化索引の構造に関する情報とする．エントリに関する情報はサーバ側に，構造に関する情報はクライアント側にそれぞれ配置され，暗号化索引は分散管理される（図 2）．

5. 2 索引探索アルゴリズム
OSIT フレームワークでは，クライアント自身が暗号化索引を探索して検索処理を行なう．しかし，クライアントは暗号化
索引のエントリに関する情報を持たないため，単独では探索ができない．そこで，サーバにエントリに関する情報を問い合わ
せて，クエリの条件 q と各エントリの key を比較する．比較に際しては，クライアントとサーバ間で互いの暗号化索引の情報

本節では，OSIT (Oblivious Secure Index Traversal) フレー
ムワーク [14] を紹介する．OSIT フレームワークは，データベース中の暗号化されたデータを索引を用いて効率的に検索するための枠組みである．ここでは，クライアント側でエントリに関する情報を取り除いた索引を管理し，サーバ側で構造に関する情報を取り除いた索引を管理する．クライアントは，エン
トリに関する情報をサーバに問い合わせながら索引を自身で探索することで，クエリに該当するデータを取得する．5.1 節で索引構築アルゴリズムについて説明し，続く 5.2 節で索引探索
アルゴリズムについて説明する．

5. 1 索引構築アルゴリズム
まず，データ所有者は検索用のデータベース索引を構築するために，データベース中の各レコードの検索対象となる属性の値 key とレコード内容 val の組合せ ⟨key, val⟩ で構成されるエントリの配列を作成する．この配列のエントリを keyの値でソート後，配列中の位置を各レコードの識別子 id としが漏洩することを防ぐため，GT–SCOT プロトコル [3] を用いた紛失通信を行なう．また，データ所有者は GT–SCOT プロ
トコルを実行するためのサーバを，データベース利用のためのサーバとは別に用意する．ここでは，暗号化索引のエントリ情報を管理するサーバをデータベースサーバ，GT–SCOT プロト
コルを実行するサーバを秘密計算サーバと呼ぶ．
暗号化索引の探索アルゴリズムを図 3 と Algorithm 1 に示す．まず，クライアントは q にランダムなノイズ r を加えてクエリを書き換える．クエリをそのままの値でサーバに送信しないことで，クエリプライバシを保証する．また，データ所有者から提供された暗号鍵を用いて r を暗号化する．さらに，比較したいエントリの配列上の位置 id のハッシュ値 h(id) を導出す
る．その後，h(id), E(r) をデータベースサーバに，q + r, s0 , s1を秘密計算サーバに送信する．なお，s0 , s1 は GT–SCOT プロ
トコルで用いる値である．データベースサーバでは，指定され6. 提 案 手 法
本節では，暗号化索引をより効率的に探索するための OSIT
フレームワークの拡張手法を提案する．OSIT フレームワークでは，一つのエントリにつき一回の紛失通信サイクル（Algorithm

1: l. 2–17）を行なってクエリと比較する．従って，探索に必要となる通信回数はエントリの比較回数に相当する．また，OSIT
フレームワークの検索コストは通信コストに最も依存する．以上のことから，OSIT フレームワークでは比較回数が最小とな

図 3 暗号化索引の探索

る二分探索を採用することで，検索コストを削減している．しAlgorithm 1: 索引探索アルゴリズム（OSIT）

かしながら，一回の紛失通信サイクルで複数のエントリを比較

1

id ← N+µ2

しても安全性に問題はない．そこで，OSIT フレームワークの2

while 探索が終了するまで do

索引探索アルゴリズムを拡張して，複数のエントリを一回の紛

3

Procedure クライアント

失通信サイクルで比較するアルゴリズムを提案する．さらに，/* initialization */4

q + r, E(r), h(id) を導出

5

データベースサーバに h(id), E(r) を送信

6

秘密計算サーバに q + r, s0 , s1 を送信

7

h(id) が付与されたエントリの E(key) を取得

9

E(key + r) ← E(key) · E(r)13

6. 1 索引探索アルゴリズムの拡張提案手法では，一回の紛失通信サイクルで k − 1 個のエント
リとクエリを比較して，暗号化索引を k 分探索する．この場合

es ← Gt–scot(E(key + r), q + r, s0 , s1 )も，暗号化索引はデータ所有者によって構築され，クライアン

クライアントに es を送信

トとデータベースサーバで分散管理される．提案する索引探索

Procedure クライアント

アルゴリズムを Algorithm 2 に示す．まず，クライアントはクエリを書き換えるために k − 1 個のランダムなノイズ r を用意

es を復号化し，id を更新

15

17

6.2 節で拡張した OSIT フレームワークのコストモデルを示す．

Procedure 秘密計算サーバ

1216を提案する．6.1 節で探索アルゴリズムの拡張について説明し，

秘密計算サーバに E(key + r) を送信

1014きるように，拡張後の OSIT フレームワークのコストモデル

Procedure データベースサーバ

8

11

一回の紛失通信サイクルで比較するエントリ数を最適に決定でendする．このノイズを用いて k − 1 通りにクエリを書き換えて，end

書き換え後クエリ集合 Q を作成する．また，データ所有者から提供された暗号鍵を用いて全ての r を暗号化して，集合 ER をた h(id) が付与されたエントリの E(key) を取得する．ここで，後の比較で q と key の大小関係を変えないために，q と同様に
ノイズ r を加えて key を書き換える．E(key + r) は，加法準同型性を利用して式 (4) のように E(key) と E(r) から導出できる．

E(key + r) = E(key) · E(r)位置 id のハッシュ値 h(id) を導出する．この h(id) の集合を Hとする．その後，H, ER をデータベースサーバに，Q, s0 , s1 を
秘密計算サーバに送信する．データベースサーバでは，指定された h(id) ∈ H が付与されたエントリの E(key) を取得する．
続いて，各 E(key) にノイズ r ∈ ER を加えてクエリ同様に書(4)

次に，導出した E(key + r) を秘密計算サーバに送信する．秘
密計算サーバでは，GT–SCOT プロトコルを実行して出力結果

es を得る．es は，E(s0 ) もしくは E(s1 ) であり，クライアン
トに送信される．クライアントは，データ所有者から提供された暗号鍵を用いて出力結果を復号化し，得られた大小関係に基づいて次に比較するエントリを決定する．以上の操作をまとめて紛失通信サイクルとして，探索が終了するまで繰り返す．なお，暗号化索引の探索には二分探索を用いている．ただし，ア
クセス頻度から構造に関する情報がデータベースサーバ側に漏洩することを防ぐために探索範囲の中間値を毎回ランダムに摂動させる必要がある．Algorithm 1 中の µ は摂動値である．また，紛失通信によって id を更新する場合も摂動を考慮しなければならない．

作成する．そして，比較したい k − 1 個のエントリの配列上のき換える．この E(key + r) の集合を EK とする．データベー
スサーバは，作成した EK を秘密計算サーバに送信する．秘密
計算サーバでは，EK, Q, s0 , s1 に対して GT–SCOT 関数を適用して，得られた出力結果 es をクライアントに送信する．ク
ライアントは，データ所有者から提供された暗号鍵を用いて全ての出力結果を復号化して，得られた大小関係に基づいて次に比較するエントリを決定する．以上の操作を探索が終了するまで繰り返す．

6. 2 コストモデル
以下では，拡張 OSIT フレームワークにて暗号化索引を k 分
探索する場合のコストモデルを提案する．
まず，一回の紛失通信サイクルに必要な通信コストを導く．以下では，(1) クライアント端末からデータベースサーバへの通信コスト，(2) クライアント端末から秘密計算サーバへの通信コス
ト，(3) クライアント端末から秘密計算サーバへの通信コスト，及び (4) 秘密計算サーバからクライアント端末への通信コストをそAlgorithm 2: 索引探索アルゴリズム（拡張 OSIT）
1

while 探索が終了するまで do

2

Procedure クライアント

3

for i=1 to k-1 do

SCOT 関数の計算コストを tcomp とした上で，一回の紛失通信サイクルによる単一エントリの比較コストを定義 5 に示す．
定義 5（一回の紛失通信による単一エントリの比較コスト）一回の紛失通信に必要な通信コストが tcomm であり，単一エント

4

q + ri , E(ri ), h(idi ) を導出

リとクエリの比較に必要な計算コストが tcomp であるとき，一5

Q に q + ri を追加

回の紛失通信による単一エントリの比較コストを式 (6) とする．

6

ER に E(ri ) を追加

7

H に h(idi ) を追加

8

end

9

データベースサーバに H, ER を送信
秘密計算サーバに Q, s0 , s1 を送信

10
11Procedure データベースサーバ
for i=1 to k-1 do

12

Cost = tcomm + tcomp(6)

拡張 OSIT フレームワークで暗号化索引を k 分探索する場
合，一回の紛失通信で k − 1 個のエントリをクエリと比較する．
このとき，通信コスト tcomm はエントリ数に依存しないが，計算コスト tcomp に依存する．よって，定義 5 に従って一回の紛
失通信による複数エントリの比較コストを定理 1 に示す．

13h(idi ) が付与されたエントリの E(key) を取得

14

E(key + ri ) ← E(key) · E(ri )定理 1（一回の紛失通信による複数エントリの比較コスト）拡15

EK に E(key + ri ) を追加

張 OSIT フレームワークにより暗号化索引を k 分探索する場

16

end

合，一回の紛失通信サイクルによる複数エントリの比較コスト

17

秘密計算サーバに EK を送信

は式 (7) のようになる．

18

Procedure 秘密計算サーバ

19

for i=1 to k-1 do

20

esi ← Gt–scot(E(key + ri ), q + ri , s0 , s1 )21

ES に esi を追加

22

end

23

クライアントに ES を送信

24

Procedure クライアント

25

for i=1 to k-1 do

26

esi を復号化
end

27

id を更新

28
29
30

end
end

Cost(k) = tcomm + (k − 1)tcomp(7)

暗号化索引が N 個のエントリで構成される場合，探索開始
から終了までに ⌈log(N +1)
⌉ 回の紛失通信サイクルを行なう必
log(k)

要がある．拡張 OSIT フレームワークのコストモデルを定理 2に示す．
定理 2（拡張 OSIT フレームワークのコストモデル）探索対象の暗号化索引のエントリ数が N のとき，拡張 OSIT フレーム
ワークのコストモデルは式 (8) のようになる．

TotalCost(N, k) = Cost(k)⌈log(N + 1)⌉
log(k)(8)

なお，（拡張）OSIT フレームワークではデータベース側に暗号化索引の構造情報を秘匿するためにエントリを選択する際に

CL→DB
CL→CS
DB→CS
CS→CL
れぞれ (1) τcomm, (2) τcomm, (3) τcomm, (4) τcommとする．このとき，一回の紛失通信サイクルに必要な通信コス

摂動を加えていたが，ここでは簡単のために摂動を加えずに検索を行なうことを想定している．摂動を考慮した場合には，通信サイクル数は ⌈トは各パスの通信コストを全てを合わせたものではない．これは，GT–SCOT プロトコルの実行に，クライアントから送信される q + r ，及びデータベースサーバから送信される E(key + r)
がともに必要であり，秘密計算サーバで同期が発生するからである．クライアントが探索のために通信を開始してから GT–

SCOT 関数が実行されるまでの通信コストは，クライアント端
CL→DB
末からデータベースサーバへの通信コスト τcomm
とデータ
DB→CS
ベースサーバから秘密計算サーバへの通信コスト τcommの和，及びクライアント端末から秘密計算サーバへの通信コスト
CL→CS
τcomm
で最大値に相当する．一回の紛失通信サイクルに必要

7. 実

log(N +1)
⌉ 回になるとは限らない．
log(k)

験

本節では，提案コストモデルの妥当性を検証するために行なった実験について述べる．

7. 1 環 境 設 定
計算環境 本実験には，CPU が Intel Core i7（3GHz），メモ
リが 16GB の Mac 端末をクライアント端末として利用した．
また，CPU が Intel Xeon L5630（2.13GHz），メモリが 2GBで構成される二台の Ubuntu サーバを用意して，一方をデータ
ベースサーバ，もう一方を秘密計算サーバとして利用した．

な通信コストを定義 4 に示す．

データセット 本実験には，レコード数 N = 10, 000 である人

定義 4（一回の紛失通信サイクルに必要な通信コスト）一回の工のデータセット A，及びレコード数 N = 100, 000 である人

紛失通信サイクルに必要な通信コスト tcomm を式 (5) とする．

tcomm
CL→DB
DB→CS
CL→CS
CS→CL
= max(τcomm+ τcomm, τcomm) + τcomm(5)

続いて，一つのエントリとクエリを比較するときの GT–

工のデータセット B を用いた．いずれも各レコード中の検索対
象の属性は，210 以上 220 以下の整数値をランダムにとる．

7. 2 提案コストモデルの評価
提案コストモデルの妥当性を検証するために，まずは本
実験環境における tcomm ，及び tcost を計測した．その結果，

図4

k 毎の探索時間の実測値と理論値の比較 （左）データセット A

tcomm = 1850.4[ms], tcomp = 53.8[ms] が得られたので，式 (8)に従って本実験におけるコストモデルを導出した．

TotalCost(N, k) = {1850.4 + 53.8(k − 1)}⌈log(N + 1)⌉
log(k)

log(N + 1)
= (53.8k + 1796.6)⌈⌉ (9)log(k)
続いて，k を 2 から 45 の間で変化させたときの索引の探索
時間について，実測値と式 (9) から導出される理論値を比較することで，提案コストモデルの妥当性を検証する．実測値として，データセット A, B に対して各 k 毎に 10 回ずつ検索を行な
い，探索時間の平均値を算出した．なお，比較対象となるエン
トリを選択する際の摂動はコストモデルで考慮されていないので，本実験でも摂動を加えずにエントリを選択した．比較結果
を図 4 に示す．いずれのデータセットにおいても実測値と理論値の傾向がほぼ一致しており，提案コストモデルが妥当であると言える．また，k = 2 の場合の索引探索アルゴリズムは既存の OSIT フレームワークの索引探索アルゴリズム（Algorithm1）に相当する．図 4 より k > 2 のときに探索時間が短くなっていることから，提案する索引探索アルゴリズムが検索処理の（右）データセット B

8. お わ り に
本稿では，信頼できないデータベース管理者に対してデータとクエリ双方のプライバシを保証する秘匿検索フレームワーク

OSIT について，索引探索アルゴリズムの拡張手法を提案した．
提案手法では，索引のエントリを一括してクエリと比較することで通信サイクル数を削減し，検索処理の高速化を実現している．また，拡張 OSIT のコストモデルを提案し，一回の通信サ
イクルで比較対象とするエントリ数の最適値を検討した．
今後の課題は二つある．一つ目は，並列計算による暗号化索
引探索の更なる高速化を検討することである．拡張 OSIT による検索処理は，評価実験よりレコード数が高々100,000 のデー
タセットでも 10 秒以上かかっており，実用的なものとは言えない．これに対して，GT–SCOT プロトコルによる大小比較演
算は，複数の秘密計算サーバで並列に行なうことが可能である
ので，複数のエントリを一括して比較する拡張 OSIT では並列計算による高速化が期待できる．二つ目は，グルーピングや集約演算，他のレコードとの結合といった複雑な演算をサポートできるようにすることである．

高速化を実現していることが実験的にも示された．
謝辞 本研究の一部は，平成 27 年度共同研究（SKY 株式会社

CPE27116）によるものです．

文

図 5 k 毎の探索時間と通信回数・計算回数の関係

続いて，k 毎の通信回数と計算回数からコストモデルの妥当性を検証する．図 5 は，データセット A における k 毎の通信回数・計算回数を計測し，探索時間との関係を示したものである．通信回数と計算回数がトレードオフの関係にあり，式 (8)の示す通りになっている．以上の結果から，提案するコストモ
デルが妥当であることが示された．

献[1] P. Paillier. Public-key cryptosystems based on composite
degree residuosity classes. Advances in Cryptology – EUROCRYPT’99, pages 223–238 (1999).
[2] A. C. Yao. Protocols for secure computations (extended abstract). In FOCS Volume 82, pages 160–164 (1982).
[3] I. F. Blake and V. Kolesnikov. Strong Conditional Oblivious
Transfer and Computing on Intervals. Advances in Cryptology – ASIACRYPT 2004, pages 515-529 (2004).
[4] G. D. Crescenzo, R. Ostrovsky, and S. Rajagopalan. Conditional oblivious transfer and timed-release encryption. Advances in Cryptology ― EUROCRYPT 99 Lecture Notes
in Computer Science Volume 1592, pages 74–89 (1999).
[5] A. Boldyreva, N. Chenette, Y. Lee, and A. O’Neill. Orderpreserving symmetric encryption. Advances in Cryptology– EUROCRYPT 2009, Lecture Notes in Computer Science
Volume 5479, pages 224–241 (2009).
[6] H. Hacigümüş, B. Iyer, C. Li and S. Mehrotra. Executing

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

SQL over Encrypted Data in the Database-Service-Provider
Model. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data (SIGMOD 02),
pages 216-227 (2002).
H. Wang and L. V. S. Lakshmanan. Eﬃcient secure query
evaluation over encrypted XML databases. In Proceedingsof the 32Nd International Conference on Very Large Data
Bases (VLDB’06), pages 127-138 (2006).
M. Kuzu, M. Islam, and M. Kantarcioglu. Eﬃcient similarity search over encrypted data. In Proceedings of IEEE
28st International Conference on Data Engineering (ICDE2012), pages 1156-1167 (2012).
H. Hu, J. Xu, X. Xu, K. Pei, B. Choi and S. Zhou. Private search on key-value stores with hierarchical indexes. In
Proceedings of IEEE 30st International Conference on Data
Engineering (ICDE 2014), pages 628-639 (2014).
P. Wang, Ravishankar, C.V. Secure and eﬃcient range
queries on outsourced databases using Rp-trees. In Proceedings of IEEE 29st International Conference on Data Engineering (ICDE 2013), pages 314–325 (2013).
R. A. Popa, C. M. S. Redfield, N. Zeldovich and H. Balakrishnan. CryptDB: processing queries on an encrypted
database. In Commun. ACM, volume 55, 9, pages 103–111(2012).
S Tu, M. F. Kaashoek, S. Madden and N. Zeldovich. Processing analytical queries over encrypted data. In Proceedings of the 39th international conference on Very Large Data
Bases (PVLDB’13), pages 289–300 (2013).
P. Koutris, P. Upadhyaya, M. Balazinska, B. Howe and D.
Suciu. Toward practical query pricing with QueryMarket.
In Proceedings of the 2013 ACM SIGMOD International
Conference on Management of Data (SIGMOD ’13), pages
613–624 (2013).
篠塚 千愛，渡辺 知恵美，北川 博之．DaaS 環境におけるデー
タとクエリ双方のプライバシ保護を実現する効率的な秘匿検索．
DEIM Forum 2015 G2-6 (2015).