DEIM Forum 2016 F8-2

索引を用いた複数演算に対応した安全で効率的な秘匿検索手法
秋山賢人†

渡辺知恵美††

北川 博之††† 筑波大学情報学群情報科学類 〒 305–8573 つくば市天王台 1–1–1†† 筑波大学システム情報系 〒 305–8573 つくば市天王台 1–1–1
E-mail: †k akiyama@kde.cs.tsukuba.ac.jp, ††{chiemi,kitagawa}@cs.tsukuba.ac.jp
あらまし 近年普及しつつある DBaaS ではクラウドサーバ管理者によるデータ，クエリの漏洩を防ぐためにプライバシ保護が必要である．先行研究である篠塚らの手法では，データとクエリのプライバシを守りつつ高速な検索処理を可能にする OSIT-bs フレームワークを提案している．OSIT-bs は検索用の索引をサーバとクライアント間で分散管理し，クライアントがサーバとの通信により索引を探索する手法であり，１つのクエリにつき１つの索引を探索して完全一致検索と範囲検索を行うことができる．しかし，この手法では１つのクエリで複数の索引探索が必要になった
場合に，各索引での探索結果、つまり中間結果をクライアント上で明らかにしなければならずプライバシ要求が満たされないという問題があった．そこで本研究では，複数の索引探索を必要とするクエリのうち連言節で結ばれた二つの条件を含むクエリ文を対象とし，中間結果をクライアントに明かさずに問合せを行う手法を提案する．本手法ではWong らの手法にある鍵更新演算を利用し，２つの索引探索結果である暗号化されたレコード ID 集合の積集合を暗号化したままサーバ上で行い，その結果をサーバに知らせることなくクライアントに渡す．これによりクライアントに中間結果を与えることなく複数条件による検索を処理することができる．
キーワード

プライバシ保護，秘密計算，Database as a Service

1. は じ め に

ベースシステムではデータを暗号化した状態で DBaaS にて管理し，検索可能暗号スキームを用いることによってデータを暗近年，Database as a Service（DBaaS）を利用したデータの号化したまま問合せ処理を行う．暗号化データベースに関する検索サービスが普及しつつある．DBaaS とはネットワークを研究として，CryptDB [4]，SDB [5] などが提案されている．

経由してデータベースの機能を提供するクラウドサービスであ篠塚らは [6] において，機密性を守りつつ高速な検索処理を可る．DBaaS を利用したサービスの提供例としては，Amazon

能にする検索可能暗号フレームワークである OSIT-bs（Oblivi-

RDS [1]，Oracle Enterprise Manager 12c [2]，Google Cloudous Secure Index Traversal-binary search）フレームワークをBigtable [3] などがある．DBaaS を用いる利点は，DBaaS の提案した．

利用者がサーバの購入や DBMS の構築を行うことなく DBaaS

このフレームワークでは索引を暗号化したままクライアントのサービスプロバイダにサーバの稼働及びデータベース管理をとサーバに分割して配置し，クライアント自身が索引を探索し委託することで利用者側の負担の軽減を行うことができる点，て該当するレコード集合を求めるところが特徴である．索引はデータへの高速なアクセスが保障される点，データ量に応じてサーバとクライアントに分割されて配置されており，紛失通信

柔軟にデータベースの拡張を行える点などが挙げられる．

を使って探索を行う．これによりサーバ及びクライアントが完

DBaaS は手間のかかるタスクを委託できる一方で，機密デー

全な索引の情報を知らないまま探索を実現することができる．

タやクエリの漏洩が起こりうるという問題がある．機密データ

また索引の探索に秘匿計算を用いることで，データや索引を秘やクエリの漏洩を防ぐためには，下記にあるデータとクエリに匿したまま問合せができるほかクエリの内容自体も秘匿するこ関するプライバシの要求を満たさなければならない．

とが可能であり，データ所有者及びクライアントの個人情報をデータプライバシに関する要求
・データ所有者はサーバ管理者に対し，保存するデータの中身秘匿できる．
しかしこの研究では，クライアントは一つのクエリを評価すを知られたくない

るために一つの索引を探索することを想定している．つまり・データ所有者はクライアントに対し，必要以上の情報を与え「SELECT * FROM R WHERE age > 40」のような一つの属

たくない性を検索条件とした範囲検索または完全一致検索にのみ対応し

クエリプライバシに関する要求ていた．そのため「SELECT * FROM R WHERE age > 40

・クライアントはデータ所有者及びサーバ管理者に対し，自身

AND salary < 200,000」というように連言節を含んだ複数のが発行するクエリの履歴を知られたくない条件を処理する場合，「SELECT * FROM R WHERE age >このような要求に対応するため，近年は暗号化データベース

40」「SELECT * FROM R WHERE salary < 200,000」といシステムに関する研究が盛んに行われている．暗号化データ

う別々の条件をクライアントで評価し，それぞれの結果集合の論理積を求めることになる．これはクライアントにとって負荷を持つものがある．また Gentry らにより整数上完全準同型暗が大きくなるだけでなく，問合せの途中結果がクライアントに号が提案 [17] されたが，この手法はビットごとの演算が必要で漏洩するという安全性の問題も存在する．

ありデータベースに用いるにはまだ多くの改良が必要とされそこで，本研究では先行研究をもとに，連言節で接続された複数の条件を含む問合せに対し，問合せの中間結果をクライアる [18]．また，PEKS [19] は ID ベース暗号を元にした暗号ス
キームであり，キーワード検索が可能である．

ントに知られずに求める手法を提案する．本研究を実現するた

これらの手法は非常に安全性は高いが暗号化データベース

めに，Wong らの手法 [5] で導入されている鍵更新演算を利用として大量のレコードに対して検索を行う場合には十分なパ

し，属性ごとに異なる鍵で暗号化されたレコード ID を比較しフォーマンスを満たすことができない．これらの暗号化スキーてクライアントに中間結果を与えることなく複数条件による検ムを用いた場合，レコード一つ一つに対して検索条件に該当す索を行う．

るか否かをチェックする必要があり，データの量に対して検索

本稿の構成は以下のようになっている．まず，2 節で関連研

時間がかかってしまうからである．これに対し，Hu らの手法は究について述べ，3 節で本研究に必要な前提知識について述べデータベース索引を用いた安全な検索フレームワーク OIT [20]る．次に，4 節で先行研究についての紹介を行う．続いて，5 節を提案した．この手法では索引をクライアントが所有しクライで本研究の提案手法について述べ，6 節で提案手法を評価する

アント自身が索引を探索することで安全性を確保しているが，実験について述べる．そして，7 節でまとめと今後の課題につクライアントに対するプライバシ要件が侵害されると，クライ

いて述べる．

アントに大きな負荷がかかることから，篠塚らはサーバとクラ2. 関 連 研 究

イアントで索引を分散配置した OSIT フレームワーク [6] を提案している．

DBaaS 環境における暗号化データベースシステムは，Hacigu-

また，暗号化データベースにおいては，関係代数のようにクmus [7] らによって提案されたのを先駆けにこれまで数多くのエリを構成する各演算の間に相互運用性（interoperability）を研究が取り組まれている．Hacigumus らはサーバ上で一部検索持たせることも課題である．SDB [5] では相互運用性のある加可能な安全性の低いデータをおき，サーバで一部を検索しクラ法準同型性をもった暗号スキームを提案し，それを用いた暗イアントで精査するという仕組みを提案しその問合せ処理モデ号化データベースシステムを実装している．この手法により，ルを定義した．Hore [8] らは，Hacigumus [7] らの手法をベー

サーバ側で中間結果を一度クライアントに転送して処理をした

スに統計による値の推測を困難にするサーバ側データの生成法

り，サーバ側で一部のデータを復号することなく，暗号化したを提案した．また，Agrawal [9] は数値属性の順序関係を保存

まま演算の出力結果を次の演算の入力とすることができる．

できる検索用索引の生成方法 (OPE) を提案した．この手法では順序関係が保存されているため一部のデータが漏洩した場合

3. 基 本 事 項に他の値がなし崩しに判明するという問題が指摘されており，

本節では本研究を説明する上で必要な知識について述べる．

Lee ら [10] や Hasan ら [11] などにより改良手法が提案されて

3. 1 準同型暗号

いる．また Mykletun ら [12] や Ge ら [13] によって準同型暗号

準同型暗号とは，2 つの暗号文が与えられた時に平文や秘密を利用した集約演算を可能にするサーバ側でのデータ暗号化手

鍵の値を知らなくても，暗号化したまま平文の加算や乗算を行法や，k-近傍探索への対応なども提案されている．2011 年にえる準同型性を持つ暗号のことである．準同型暗号の暗号化関はこれらの提案手法を組合せて実装した CryptDB というオー数を E(·)，2 つの平文を m1 ，m2 とした時に以下の式 (1) が成

プンソースパッケージが Popa ら [4] により公開され，暗号化り立つ．ただし，⊕ や ⊗ は加法演算子や乗法演算子のようなデータベースシステムは大きな注目を集めた．CryptDB では，演算子とする．

RND，DET，Paillier 暗号 [15] などの異なる暗号化スキームを用いて機密データを幾重にも暗号化することで，機密データの漏洩を防ぐという手法がとられている．また，各暗号化スキー
ムごとに異なるクエリの処理を行うことでキーワード検索，結合演算，大小比較などの様々な演算をサポートしている．またStephen らにより CryptDB の検索処理最適化機構が改良された Monomi [14] も発表された．

E(m1 ⊕ m2 ) = E(m1 ) ⊗ E(m2 ).

(1)

準同型暗号には RSA 暗号，ElGamal 暗号，Paillier 暗号 [15]などがあり，本稿では Paillier 暗号を使用している．Paillier 暗号の暗号化関数を E(·)，平文を m，公開鍵を pk = (n, g)，rを n 以下のランダムな値とすると Paillier 暗号の暗号化は以下の式 2 で表すことができる．

これらの暗号化データベースシステムで用いられている手法
は，特に範囲検索や結合処理を行う際に OPE を使うことが多E(m) = g m · rn mod n2 .

(2)

かったが，上記の指摘にもある通り現在この手法は安全性の問題が指摘されている．そのため近年では準同型暗号を用いた検索手法や検索可能暗号，紛失通信等を利用した手法が提案されつつある．準同型暗号は Paillier 暗号 [15] などのように加法準同型性を持つものと ElGamal [16] 暗号のように乗法準同型性

また，Paillier 暗号は加法準同型性を持つ．以下の式 3 のように 2 つの平文 m1 ，m2 の暗号文から m1 + m2 の暗号文を計算することができる．

E(m1 ) · E(m2 )= (g m1 · r1 n mod n2 ) · (g m2 · r2 n mod n2 )= g m1 +m2 · (r1 · r2 )n mod n2

ムワークが提案する手法で索引を探索することができる．
以下に索引の探索方法について述べる．OSIT-bs において

(3)

= E(m1 + m2 ).

サービスプロバイダは索引とデータを保管するデータサーバと大小比較を行う計算サーバの 2 台のサーバを提供する．索引を探索するにはノードの値とクエリ値の大小比較を繰り返し

3. 2 GT-SCOT プロトコル行う必要がある．索引の探索には二分探索を使用するが，毎回

GT-SCOT プロトコル [21] は大小比較を行う紛失通信プロトの検索で最初に選ばれる索引が中間値であり，以降の探索によコルであり，お互いの持つ値を知ることなく受信者のみが比較る索引構造の漏洩を防ぐために探索範囲の中間値にランダム結果を知ることができるという特徴を持つ．受信者 X と送信者

値 s を加えて摂動化したものを使用している．ここではサーバ

Y がそれぞれ x，y という値を持っている時に大小比較を行う

上のあるノードの値 k とクライアントで発行されたクエリ値

手順を説明する．まず，X は x を Paillier 暗号で暗号化した値

q の比較を行う手順について述べる．なおサーバ上のノードにE(x)，x < y を示す値 s0 ，x > y を示す値 s1 を Y に送る．次は Paillier 暗号 E(·) にて暗号化された値 E(k) が保存されてに，Y で E(x)，y ，s0 ，s1 を用いて E(s0 ) または E(s1 ) が得おり，そのノードのサーバ上のアドレスを h(i)，索引のサイズられる計算を行う．そして得られた結果を X に送信すると，Xを n とする．索引の探索手順を図 1 及び Algorithm 1 に示す．

は結果を復号して s0 または s1 を得ることにより，x と y の大探索が開始されると，クライアントは n に初期値である索引

小関係を知ることができる．Y では暗号化された x の値しか知のノードサイズ N を代入する (Step.0)．まず，クライアント

ることができず，比較結果も暗号化された状態で出てくるため

は r を Paillier 暗号で暗号化した E(r)，データサーバ上のア

大小関係も知ることができない．X も大小比較の結果のみしかドレス h(i) を求めてデータサーバに送る (Step.1)．次に，クラ知ることができない．

イアントはクエリ値 q にランダム値 r を加えた q ′ を求めて計

4. 先 行 研 究

算サーバに送り，h(i) にあるノードの値 E(k) に E(r) を乗算して E(k) · E(r) = E(k + r) を計算サーバに送るよう要求す

篠塚らはデータとクエリ双方のプライバシを保護した高速なる (Step.2)．続いて，計算サーバは E(k ′ ) と q ′ の大小比較を

秘匿検索フレームワークである OSIT-bs [6] を提案している．

してその結果をクライアントに返す (Step.3)．クライアントは

このフレームワークは，データ所有者がデータを暗号化した状計算サーバから受け取った結果を復号し (Step.4)，n を更新す態で DBaaS のサービスプロバイダに管理を委託し，クライアる (Step.5)．なお，大小比較は E(k ′ ) の値を暗号化したまま比ントはデータ所有者から検索の権限をもらって問合せを行うと較結果を求め，その結果もサーバに知られないようにしなけれいう状況を想定している．まず，4. 1 小節で問題定義について，ばならない．そのため比較演算では GT-SCOT プロトコル [21]4. 2 小節で OSIT-bs の概要について述べる．そして，4. 3 小節を利用している．以上の (Step.1) から (Step.5) を繰り返してで先行研究の問題点について述べる．

索引を探索する．

4. 1 問 題 定 義
先行研究では，「SELECT * FROM R WHERE age > 40」というような一つの属性を検索条件とした範囲検索または完全一致検索を安全に行うことを想定している．安全に検索を行う
ために，満たすべきプライバシ要件は以下の通りである．
・ サーバ管理者は暗号化されたデータの内容及びクエリ履
歴から元の値を推測できない・ クライアントは発行した問合せに対する結果以外の情報を得ることができない

4. 2 OSIT-bs フレームワークの概要
この手法の主要な特徴はデータ所有者がデータとともに検索用のデータベース索引を作成し、暗号化した索引をサーバとク
ライアントで分割して管理するところにある．索引には属性値

図1

索引の探索

でソートされた配列を使用する．サーバは索引のノードを暗号化した状態で所有しているが，ノード間の兄弟関係や親子関係

なお，データサーバで保存されているリーフノードにはノーは所有せず索引の構造を把握することはできない．また，デードに該当するレコードのアドレスリストが暗号化された形で保タ所有者から検索の権限を与えられたクライアントは，索引存されている．クライアントは索引をリーフノードまでたどっのノード間関係に関する情報をデータ所有者から与えられる．

た後，該当するレコードのアドレスリストを入手し，サーバ上各ノードに関してはサーバ上のアドレスのみ知らされており，のデータからレコードを取得する．

ノード自体を取得することはできない．このようにサーバ・ク
ライアント双方が完全な索引の情報を知らないまま，本フレー

Algorithm 1 先行研究における索引の探索

新演算を利用している．提案手法の概要を説明する上で，表 1

Procedure:のリレーションを用いて，条件 A「age > 40」 AND 条件 B

1: n ← N // Step.0「salary < 200,000」を例に考える．

2: while the search is not terminated do
3:client sends h(n/2 + s) and E(r) to data server // Step.1

4:

client sends q ′ , s0 , s1 and data server sends E(k + r) to calculation server // Step.2

5:

まず先行研究の索引の探索アルゴリズムを利用し，各条件に対応する索引を探索する．この例の場合，前提としてレコード集合に対して属性 age の値による索引と属性 salary に対する

calculation server performs GT-SCOT(E(k′ ), q ′ , s0 , s1 )索引がデータ所有者によってあらかじめ作成され，先行研究の// Step.3

フレームワークに従ってサーバとクライアントに分散配置され

6:

client decrypts the result // Step.4ていることを想定する．なお，索引のエントリ暗号化の際は，

7:client updates n // Step.5

8: end while

属性ごとに異なる鍵を使用する．ここでは属性 age の索引に対して鍵 ka を属性 salary の索引に対して鍵 kb を用いたとして説明を進める．

4. 3 先行研究の問題点

先行研究の索引の探索手順 (Step.1) から (Step.5) を繰り返

OSIT-bs は１回の問合せにつき１つの索引を探索することした後，クライアントが結果のレコード ID を入手する手順をを想定している．またレコードに複数の属性が含まれている場

図 2 に示す．条件 A，B を満たすレコード ID へのアドレスを

合は、属性ごとに異なるキーで索引を作成する．この手法の問

hA (kA1 ), ...，hB (kB1 ), ... とする．また，ここでは条件 A を満

題は複数の索引を探索する必要がある問合せを安全に評価す

たすレコード ID の集合を RA = {Eka (a1 ), ..., Eka (an )}, 条件

ることができないことである．例えば「SELECT * FROM R

B を満たすレコード ID の集合を RB = {Ekb (b1 ), ..., Ekb (bm )}WHERE age > 40 AND salary < 200,000」というように連とする．ここで用いている暗号プロトコルは Wong らのスキー

言節で接続された複数の条件式を評価する場合，OSIT-bs では

ム [5] を適用している．このスキームは加法準同型性を持つほクライアントが「age」と「salary」それぞれの索引に対して探か，暗号化したまま鍵を更新する関数が定義されている．Wong

索を行い，探索で得たアドレスリストを復号してサーバからレらのスキームと鍵を更新する関数については付録を参照．ま

コードを入手する．クライアントは各結果のレコードから両方ず，クライアントは hA (kA1 ), ...，hB (kB1 ), ... をデータサーバの条件を満たすレコードを最終結果として得る．この場合クラに送り (Step.a)，計算サーバに暗号化されたレコード ID の集

イアントは各々の条件を満たす結果を知ることができ，「クライ

合 RA , RB を送るよう要求する (Step.b)．次に，クライアント

アントは発行した問合せの結果以上の情報を得ることができな

は鍵更新に必要な値 p，q を計算して計算サーバに送り，計算い」というプライバシ要件を満たすことができない．

サーバに対し，鍵更新とレコード ID の論理積演算を要求する

5. 提 案 手 法
提案手法では 4. 3 小節で課題とされていた連言節で接続され(Step.c)．そして，計算サーバはクライアントに演算結果を送り (Step.d)，クライアントは結果を復号してレコード ID を入手する (Step.e)．

た複数の条件を持つ問合せに対し，クライアントに中間結果を続いて，クライアントがレコード ID を入手してから結果レ明かさずに問合せを評価する手法を提案する．まず，5. 1 小節

コードを得るまでの手順を図 3 に示す．まず，クライアントはで提案手法における問題定義について述べる．続く 5. 2 小節で受け取った結果を復号して得たレコード ID をデータサーバに提案手法の概要について述べる．

送る (Step.f)．次に，データサーバはクライアントに該当する

5. 1 問 題 定 義

暗号化されたレコードを送る (Step.g)．クライアントは各属性提案手法では「SELECT * FROM R WHERE age > 40の鍵を利用してレコードの復号を行い，結果のレコードを入手

AND salary < 200,000 」というような連言節で接続された複する (Step.h)．

数の条件を持つ問合せを想定している．問合せを安全に行うた

ここからは，サーバでの具体的な論理積の計算方法についめに満たすべきプライバシ要件は 4. 1 節で述べた以下である．

て説明する．なお，鍵 ka から kc への鍵更新関数をここでは(1) サーバ管理者は暗号化されたデータの内容及びクエリ履

ChangeKey(Eka (a), ka , kc ) とする．

歴から元の値を推測できない．

提案手法のアルゴリスムを Algorithm 2 に示す．出力結果を(2) クライアントは発行した問合せに対する結果以外の情報

RC = {Ekc (s1 ), ..., Ekc (sn )} とすると，Rc は RA の要素数とを得ることができない．

同数である．レコード ID ai が RB に含まれていた場合 si は特に，本研究では複数の条件を持つ問合せに対しても（2）を

ai となり，含まれない場合はレコード ID のドメイン外の値と満たす，すなわちクライアントに中間結果を与えないというこなる．RC はクライアントで復号し，レコード ID のドメインとを目標としている．

内の値のリストが A and B を満たすレコードのリストとなる．

5. 2 提案手法の概要
本研究では連言節で接続された複数の条件を持つ問合せをAlgorithm 2 の 3 行目の Si を求める式では，まず Ai と Bjの鍵を共通の鍵 kc に変更した後 Ai と Bj の差を求めている．

クライアントに中間結果を明かさずに求めることを目標とし

ID が一致すれば 0 となり，そうでなければ 0 以外の値となる．

ており，目標を達成するために Wong らの手法 [5] にある鍵更これを B0 から Bm の値に対して求めて総積を求めると，Ai のS1 = Ekr (r1 ) · (Ekc (3) − Ekc (2)) · (Ekc (3) − Ekc (3))
+ Ekc (3)= Ek′ (3)
ここで k ′ は計算後の暗号鍵である．計算により得られたRC = {S0 , S1 } をクライアントは復号し，3 つ目のレコードが条件に該当するとわかる．
表 1 リレーション R

ID agesalary1

45

300,000

2

20

100,0003

42

180,000

図 2 結果のレコード ID 取得

6. 実

験

本節では，提案手法の性能評価のための実験について述べる．

6. 1 実 験 環 境
本実験には，Mac OSX，Intel Core i7 @ 3GHz CPU，16GB

RAM で構成された PC を使用した．データセットに属性「A」と「B」からなるレコードを 100，1,000，10,000，100,000 件作
成して用いた．また，各属性値は 0 から 1000 の整数値を取る．

6. 2 実 験 評 価
図3

結果のレコード取得

本稿では，提案手法の性能を評価するために，SDB [5] と比較を行った．SDB は提案手法と同様に，サーバで複数演算を安Algorithm 2 Logical Product (RA , RB )Input: RA = {A1 , ..., An } = {Eka (a1 ), ..., Eka (an )},RB = {B1 , ..., Bm } = {Ekb (b1 ), ..., Ekb (bm )}Output: RC = {S1 , ..., Sn } = {Ekc (s1 ), ..., Ekc (sn )}1: for each Ai ∈ RA do
2:

ri はレコード ID のドメインを超えるランダム値で鍵 kr で暗号化されている3:

Si = Ekr (ri ) ×∏m

j=0 (ChangeKey(Ai , kc )−ChangeKey(Bj , kc )) + Ai
4: end for

全に行うことができる．また，提案手法と SDB では以下の２点が異なる．

•

問合せ処理時の索引の利用:

SDB はテーブル内のレ

コードに対して問合せ条件との参照を行う．一方で提案手法は索引の探索により条件に該当するレコードを求める•

条件該当レコードの開示： SDB では演算そのものは値を暗号化したまま行うことができるが，選択演算や結合演算，論理積等の演算において条件を満たすレコードの集合はサーバに明らかになるという性質を持つ．提案手法はこれらの結果がサーバ上で明らかになることはない．

レコード ID が RB に含まれていた場合のみ値は 0 となり，Si

１点目の相違点によって，本提案手法は選択演算の際には SDB

は Ai となる．これらの計算は暗号化したまま全て行うことがと比べて理論的には検索速度は優れていると想定される．ただできるのでサーバに比較結果を明かすことはない．

し２点目の相違点によって，本提案手法のみサーバ上で結果の提案手法を用いて，表 1 のようなリレーションに上記例の問合

漏洩をしないという安全性を確保しているため，計算コストとせを行い正しくレコードが検索できることを示す．まず，索引のしては O(n2 ) を費やすこととなり，検索速度としては劣ること

探索により RA = {Eka (1), Eka (3)}, RB = {Ekb (2), Ekb (3)}が予想される．

が求められる．次に，求めた RA ，RB を入力として Algorithm

2 を適用すると以下のような計算が行われる．

実験は「SELECT * FROM R WHERE A < 10 AND B >990」という条件での問合せに対し，各データ数における平均
クエリ応答時間の比較を行った．この問合せに該当するレコー

S0 = Ekr (r0 ) · (Ekc (1) − Ekc (2)) · (Ekc (1) − Ekc (3))
+ Ekc (1)= Ek′ (2r0 + 1)

ド数は A,B ともに全レコード数の 1%程度になっている．各
データ数における平均クエリ応答時間を図 4 及び表 2 から表 4に示す．結果は各条件に該当するレコード ID を求める計算時
間，両方の条件を満たすレコード ID を求める計算時間，結果のレコードを復号する計算時間に分けて示してある．図 4 から提案手法では [5] と比べて，レコード数が 100 件の時は実行時
間のほとんどを索引の探索にかけている．提案手法の場合は探索回数は少ないが，１回の探索でサーバとクライアントのやり

表 4 各データ数における結果レコードの復号時間 (ms)
データ数

とりが必要となり時間がかかるためレコード数が少ない場合は

100

0

1,000

5

6

10,00038

29

100,000286271

索引は有効でないことがわかる．図 4 が示すようにレコード数
が 1,000，10,000 の場合は SDB よりも実行時間が短くなっている．特に，レコード数 10,000 の時は索引を利用しているこ

提案手法 SDB

0とで各条件に該当するレコードを高速に求めることができていることが示せた．図 4 からレコード数 100,000 の時も索引による効率的な処理が行われていることがわかる．また，平均クエ

7. お わ り にリ応答時間も SDB よりも 20%ほどの増加に抑えることができている．レコード数の増加により実行時間の大部分が論理積演

本研究では，連言節で接続された複数の条件を含む問合せに算にかかってしまったことが実行時間増加の原因であることが対し，中間結果をクライアントに明かさずに求める手法を提案示せた．

した．また，実験結果から各条件に該当するレコード数が増加

本実験から，提案手法は索引を用いているためレコード数がすると論理積演算の回数が膨大になり，論理積演算が実行時間多く，問合せの各条件に該当するレコード数が少ない場合に効の大部分を占めていることが示された．しかし，索引を用いて率的な問合せ処理を行うことができることが示せた．また，各いるためデータ数が多く各条件を満たすレコード数が少ない場

条件に該当するレコード数が増加すると，索引を用いて削減で合は効率的な処理を行うことができた．

きた実行時間以上に論理積演算にかかる時間の影響で SDB よ

今後の課題としては，安全性を追求したことにより実行に時りも遅くなるということが示せた．論理積演算の計算コストを間がかかったことを踏まえて安全性を考慮しつつ計算時間を減削減することが今後の課題となると言える．

少させることを目標とし，比較演算の改善を検討する必要があ
る．改善方法としては，各条件に該当するレコード全ての組合せについて計算を行わずに，各該当レコード集合を分割した小さなグループに対し比較演算を行う手法が有効であると考えている．

文

図 4 各レコード数における平均クエリ応答時間

表2

各データ数における各条件を満たすレコードの探索時間 (ms)
データ数 提案手法

SDB

100

52

8

1,000

49

53

10,00046

228

100,000

36 1,855

表 3 各データ数における論理積演算の時間 (ms)
データ数

提案手法 SDB

100

0

0

1,000

0

0

10,0006

0100,000

2,290

0

献

[1] Amazon RDS. https://aws.amazon.com/jp/rds[2] Oracle Enterprise Manager 12c. http://www.oracle.com/
technetwork/jp/oem/enterprise-manager/overview/index.
html[3] Cloud Bigtable - Google Cloud Platform. https://cloud.
google.com/bigtable/?hl=ja[4] R. A. Popa et al. Cryptdb: processing queries on an encrypted database. CACM, 2012.
[5] W. K. Wong et al. Secure Query Processing with Data Interoperability in a Cloud Database Environment. Proceedings of the 2014 ACM SIGMOD International Conference
on Management of data, pp. 1395-1406 (2014)[6] 篠塚 千愛, 渡辺 知恵美, 北川 博之. DaaS 環境におけるデー
タとクエリ双方のプライバシ保護を実現する効率的な秘匿検索.
DEIM Forum 2015 G2-6 (2014).
[7] H. Hacigumus, B. Iyer, C. Li and S. Mehrotra. Executing
SQL over Encrypted Data in the Database-Service-Provider
Model. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of data, pp. 216-227(2002)[8] B. Hore, S. Mehrotra, and G. Tsudik. A Privacy-Preserving
Index for Range Queries. In Proceedings of the 30th International Conference on Very Large Data Bases, 2004
[9] R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Orderpreserving encryption for numeric data. in Proceedings of the2004 ACM SIGMOD international conference on Management of data (SIGMOD 04), pp. 563-574, 2004.
[10] S. Lee, T. Peak, D. Lee, T.Nam and S.Kim. Chaotic Order
Preserving Encryption for Eﬃcient and Secure Queries on
Databases. IEICE Transactions on Information and Systems E92.D（11）, 2207-2217（2009)[11] Kadhem H. Amagasa T. and Hiroyuki K. A Secure and Efficient Order Preserving Encryption Scheme for Relational
Databases. In Int’l Conf. on Knowledge Management andInformation Sharing (KMIS2010), Valencia (2010)[12] E. Mykletun, G. Tsudik. Aggregation Queries in the
Database-As-a-Service Model. In IFIP WG 11.3 on Data
and Application Security (2006)[13] T. Ge, S. B. Zdonik. Answering Aggregation Queries in a
Secure System Model. In Proceedings of VLDB 2007, pp.
519-530 (2007)[14] S. Tu et al. Processing Analytical Queries over Encrypted
Data. In PVLDB, 2013[15] P. Paillier. Public-key cryptosystems based on composite
degree residuosity classes. in Proceedings of the International Conference on the Theory and Application of Cryptologravarphic Techniques Prague (EUROCRYPT 99), pp.
223-238, 1999.
[16] T. Elgamal. A Public-Key Cryptosystem and a Signature
Scheme Based on Discrete Logarithms. IEEE Transactions
on Information Theory, v. IT-31, n. 4, 1985, pp. 469-472[17] C. Gentry. Fully homomorvarphic encryption using ideal
lattices. In STOC, 2009.
[18] C. Gentry et al. Fully homomorvarphic encryption withpolylog overhead. In EUROCRYPT, 2012.
[19] D. Boneh, G. D. Crescenzo, R. Ostrovsky and G. Persiano.
Public key encryption with keyword search. In EUROCRYPT, 2004.
[20] H. Hu et al. Private search on key-value stores with hierarchical indexes. in Proceedings of IEEE 30st International
Conference on Data Engineering (ICDE 2014), pp. 628-639,
2014.
[21] I.F. Blake and V. Kolesnikov. Strong Conditional Oblivious
Transfer and Computing on Intervals. in Proceedings of the10th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT
2004), pp. 515-529, 2004.

付

•

乗算

A，B の 暗 号 化 値 を そ れ ぞ れ ae ，be と し ，カ ラ ム キ ー を
ckA = ⟨mA , xA ⟩，ckB = ⟨mB , xB ⟩ とする．ae と be の乗算方法について述べる．クライアントは乗算後の鍵を式 A·5 で計算
する．

mC = mA mB mod n.

(A·5)

xC = xA + xB mod φ(n).
乗算結果を ce とし，サーバは式 A·6 で暗号化された値を書き換える．

ce = ae be mod n.

(A·6)

ce が正しく復号できることを式 A·7 で示す．なお，簡単のため mod は省略している．

c = ce ck = ae be ck= ae be mC g rxC= ae be mA mB g r(xA +xB )(A·7)= a e a k be bk
= ab
•

鍵更新式

以下で鍵の更新演算について述べる．まず，データ管理者がデータを預ける際にカラム内の値がすべて 1 のカラム S を暗号化してサーバに保存する．

録

S のカラムキーを ckS = ⟨ms , xs ⟩，カラム A の暗号化値を

ここでは Wong らの暗号化スキーム及び鍵更新式について述

ae ，カラムキーを ckA = ⟨mA , xA ⟩，更新後のカラムを C，暗べる．まず，暗号化のためにクライアントは 2 つの秘密の数 g,

号化値を ce ，カラムキーを ckC = ⟨mC , xC ⟩ とする．クライアn を準備する．ここで g と n は互いに素，n は 2 つの大きなラントは以下の式 A·8 で p，q の値を計算してサーバに送る．

ンダムな素数 ρ1 ，ρ2 の積である．また，φ(n) を以下の式 A·1
で定める．

p = x−1s (xC − xA )mod φ(n)φ(n) = (ρ1 − 1)(ρ2 − 1).

(A·1)

以降で鍵の生成，暗号化，復号，乗算，鍵更新式の式を示す．

•

q = mA mS p mC −1 mod n(A·8)

サーバはクライアントから p，q を受け取り以下の式 A·9 でce 計算する．

暗号化鍵の生成

各カラムごとに定められたカラムキー ck = ⟨m, x⟩ から暗号化

ce = qae se p

及び復号鍵を生成する．ただし，m, x は 0 < m, x < n の整数とする．以下に暗号化鍵の生成式 A·2 を示す．

(A·9)

以下の式 A·10 で ce を ckC で復号できることを示す．以下では mod を省略する．

vk = mg rxmod φ(n) mod n.
•

(A·2)

暗号化

c = ce mC g rxC = mA mS p mc −1 ae se p mC grxc

v を平文，ve を暗号化した値とする．以下に暗号化の式 A·2 を示す．

= mA mS ae ((mS g rxS )−1 )se p mC grxc
= mA ae (g rxS xS

ve = vvk −1 mod n.
•

(A·3)

復号

−1

(xC −xA ) −1)

(A·10)

grxc= ae (mA g rxA ) = a
以上より暗号化値を変更することなく，鍵の更新を行えるこ

以下に復号の式 A·2 を示す．

v = ve vk mod n.

とが示せた．

(A·4)