DEIM Forum 2013 F8-5

検索効率を重視したプライバシ保護型検索における
タプル情報の漏洩を防止する索引手法
宮崎 昇幸†

吉川 正俊†† 京都大学大学院 情報学研究科 〒 606-8501 京都市左京区吉田本町
E-mail: †tmiyazaki@db.soc.i.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp
あらまし

暗号をベースとしたプライバシ保護型検索の枠組みでは，検索に伴う情報漏洩と検索効率とはトレードオフの関係にある．特に，これまで提案されている検索効率化を重視した研究では，索引付けによってタプル間の関係情報を漏洩しており，特定の攻撃に対する安全性を著しく損なってしまう．そこで本稿では，検索効率を重視したプ
ライバシ保護検索において，検索効率を大きく損なうことなくタプル単位での情報漏洩を防止する索引手法を提案す
る．この索引手法は，互いに識別不能であることを保証したタプルの集合を関係情報漏洩の最小単位としており，かつ安全な更新が可能である．
キーワード

プライバシ保護型検索, データベースアウトソーシング, Database as a Service

Takayuki MIYAZAKI† and Masatoshi YOSHIKAWA†† Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Sakyo, Kyoto 606-8501 Japan
E-mail: †tmiyazaki@db.soc.i.kyoto-u.ac.jp, ††yoshikawa@i.kyoto-u.ac.jp

1. は じ め に
DaaS (Database as a Service) [1] [2] においては，利用者はデータベースシステムの運用・保守に要する管理コストを削減

データ断片を分散したサーバの結託による情報漏洩の危険が存在する．すなわち，外部の脅威への対策は秘密分散法によって一つの解決をみたと言えるが，内部の脅威への対策は未だ研究の余地を残している．

できる一方で，サービス提供者に委託する機密データの安全性

効率的な検索とは，データベースに格納されている全てのをいかにして保証するかが問題となる．データの暗号化は，こデータに対する照合を必要としないことを意味する．そのため，うした環境においてデータの安全性を保証するための強力なこれらの研究課題は，いかにして暗号化データ上に安全な索引手段であるが，一般に，安全性を損なうことなく効率的に種々付けを行うかという問題に帰着される．アプローチの一つとしの検索（範囲検索など）を行うことを困難にしてしまう．こうて，平文の大小関係が暗号文の大小関係にそのまま反映されるした背景から，安全性と検索効率の両立を目的としたデータ暗よう暗号化を施し，その順序関係を索引付けに利用する手法が号化，および検索手法は盛んに研究されている [3] [4] [1] [2] [5]．

提案されている [3]．しかし，この手法はタプル単位の順序関係

本論文では，こうした手法を，検索効率を重視したプライバシや平文の出現数が漏洩することを許容しており，ドメインの分

保護型検索と呼ぶ．

布に関する知識を持つ攻撃者に対して脆弱である．

委託する機密データに対する脅威は，DaaS のモデルに含ま立場の異なるアプローチとして，秘匿したい属性の索引付け，れない外部の攻撃者によるものと，モデル内部の悪意ある主体

および問合せは全て複数のタプルを含む集合（バケット）単位

によるものに分類できる．Shamir の研究 [6] や Blakley らので行うことで，本来問合せ対象となっていたタプルの匿名性を研究 [7] では，機密データを n 個の断片に分割したうえ複数の保証する手法が提案されている [1] [2]．この手法での検索は非サーバに分散配置し，そのうち k 個が収集されたときはじめて常に効率的であると同時に，匿名性の保証によってタプル間の元データを復号可能となる k-out-of-n 秘密分散法を提案して順序関係や値の出現頻度漏洩を防止する．しかし，問合せ結果

いる．秘密分散法は情報量的安全性を保証しており，実サービの中に含まれる偽陽性をフィルタリングするコストが利用者にスとして提供されている事例もある [8] ．しかし，サービス提課されるうえ，更新に対応した動的な安全性の保証にも難が供者，ひいてはサーバ（群）の悪意ある挙動は想定しておらず，ある．

本論文では，暗号化データに対する効率的検索を目的とした化してからサーバに渡されるため対象となる属性およびその値

上記 2 つのアプローチを統合することで，両者が持つ課題を補を知られることはない．また，問合せ結果にはハッシュ値の衝完した安全な索引手法を提案する．サービス提供者（サーバ，突による偽陽性が含まれ，特定のフィルタとタプルとを結びつ

サーバ群）は悪意を持っていると仮定し，従来タプル単位で許けられるリスクを低減している．しかし，問合せの度に Bloom

容されていた順序関係の漏洩を，複数の暗号化タプルを含んだ

Filter の生成，および索引全てに対する存在検査が必要であり，バケット単位でしか許容しない．また，バケット内ではタプル

ハッシュ値の計算等に要するオーバーヘッドが問題となる．

間の区別ができないことを保証し，各平文の出現頻度を秘匿す

川本らの研究 [17] では，摂動を加えた内積範囲述語暗号を検る．これらのバケットを葉とする暗号化 B+木索引を構築し，

索トークンとして用いるプライバシ保護範囲 (一致) 問合せ手

この索引によって各平文の出現頻度に応じた匿名性を保証する法を提案している．この手法は格納データおよび問合せの匿名

バケット分割，および問合せをサポートする．

性を保証するが，全てのタプルに対する行列演算による照合処

2. 関 連 研 究
本節では，データベース上の安全な検索を対象とする関連研究を紹介する．

理が必要であり，全データ数 n に対して O(n) の検索コストを要する．これに対し，Bloom Filter と局地性検知可能ハッシュを利用した検索効率化も提案されている [18] が，金子らの研究
同様，検索結果に含まれる偽陽性のフィルタリングが問題とな

2. 1 検索可能暗号

る．また，暗号化問合せの頻度を用いた統計的攻撃の実現性に検索可能暗号 (Searchable Encryption : SE) [9] [10] [11] は，ついても十分な検証はなされていない．

秘匿したいデータの暗号文に検索用タグを付加することで，暗Lu の研究 [5] では，範囲述語暗号を利用した暗号化 B+木を号化したままでのキーワード完全一致検索（もしくは部分一致

構築することにより，タプルの順序関係漏洩を許容する代わり検索）を可能とする暗号化手法である．検索用タグは元のデーに対数オーダーでのプライバシ保護一致・範囲検索を実現してタから抽出したキーワードを反映した暗号文であり，検索したいる．この手法は安全な更新，アクセスコントロール，およびいキーワードを入力として生成した復号鍵によりこれらのタ

データ完全性の検証をサポートするが，索引付けによって順序

グが正しく復号されるか否かによってキーワードの一致を判定

保存暗号化と同様にタプル間の順序関係を即座に漏洩してしまする．

う．先述のようにこれらタプル単位での順序関係漏洩は非常にSE は共通鍵暗号をベースとしたものと公開鍵暗号をベースとしたものに大別されるが，一般には高速性を重視し共通鍵暗号をベースとするものが多い．一方，どちらの場合も検索用タリスクが高いと考えられるが，検索効率を重視する場合に許容できる程度の情報漏洩であるのかは議論されていない．

2. 3 順序保存暗号

グおよびトークンを用いた照合処理は格納されている全ての順 序 保 存 暗 号 (Order-Preserving Encryption Scheme :データに対して行う必要があり，全データ数 n に対して O(n)OPES) は，平文の順序関係を保存したまま暗号化を施すこのコストを要する．そのため，対象データが非常に大規模であとで，暗号化データ上での効率的な検索を可能とする暗号化手

る場合は検索が非効率になるという課題がある．

法である．順序関係を保存することから，OPES により暗号化

2. 2 プライバシ保護型検索されたデータベースを観察した者は立ちどころに全タプルの順

プライバシ保護型検索は，データベースサービスを提供する

序関係情報を入手することが可能である．

信頼できないデータ保持者（サーバ）と利用者のインタラク

Agrawal らの研究 [3] では，暗号化対象となる数値属性のドションによる情報漏洩，およびそれに基づく統計的攻撃も考慮

メインを順序関係を保ったまま別の分布に再マップすることした上で，利用者が問い合わせた内容を秘匿する検索を行うこによる OPES を提案している．一方，この手法ではある平文とを目的とする研究である．

に対する暗号文は一意に決定されるため，当該属性値の頻度

Private Information Retrieval (PIR) [12] [13] [14] は，問合分布を知る攻撃者による統計的攻撃に対して脆弱であるといせに関する情報をデータベースサーバに一切知られることなくう課題がある．これに対し Kadhem らの研究 [4] では，あるデータを取得することを目的とする研究である．PIR では，0平文に対して複数の暗号文を割り当てることが可能な順序保から n − 1 までの数値が割り当てられた n 個の 1 ビットデー

存暗号化スキーム MV-OPES (Multivalued-Order Preserving

タ {x0 , x1 , · · · , xn−1 } を格納しているデータベースに対して，

Encryption Scheme) を提案している．しかしこの研究では，利用者は i 番目のビット値を i を秘匿したまま問い合わせる

各平文に別のドメインの部分空間を割り当てる際に入力としたことが可能である．一方，複数の結託しないことが保証できる

頻度分布の偏りが後から変化する場合，全ての部分空間の再割

サーバおよび膨大な通信コストを必要とするなどの特徴から，

当をしなければ全体が一様分布になることを保証できない．

実現性のある手法を与えることが困難である．

OPES の暗号学的安全性については近年盛んに議論が成され金子らの研究 [15] では，要素集合に対するある要素の存在検ている [19] [20] が，主眼は「暗号文から順序関係以外の情報を査に用いられる Bloom Filter [16] を索引として利用し，タプル

漏洩していないか」という点であり，知識を持つ攻撃者によるを暗号化したまま一致・範囲問合せを行う手法を提案している．

統計的攻撃に対する脆弱性は考慮されていない．しかし，攻撃

Bloom Filter はビット列同士の OR 演算を伴うため元の属性値

者が当該属性値の頻度分布についての完全な知識を持つ場合だを復元することはできず，問合せもハッシュした上でフィルタ

けでなく，ドメインの最小・最大値，属性の性質，頻度分布の一部，もしくは問合せの履歴など不完全な知識しか持たない場
合にも，タプル間の順序関係情報との組み合わせにより推論攻撃の信頼度を幾ばくか高められる危険性がある (例 1, 例 2)．このように，OPES にみられるタプル単位での順序関係漏洩が許容できるか否かについては議論の余地が残る．
例 1:

暗号化された属性が「試験の得点」であることを，攻撃
図 3 Database as a Service モデル

者が知り得た事例を考える (図 1)．この知識から，暗号化前の属性値の値域は [0, 100] である可能性が高いことがわかる．ここで，暗号文が順序保存かつ決定論的である（平文と暗号文がある平文 ptextA を元とする暗号文の集合に一致する．このこ一意に対応する）という性質を持つ場合には，テーブルに格納とから，ptextA は攻撃者が知る部分頻度分布のうち，頻度 10された暗号文の多様性（何種類存在するか）が高いほど，各暗を持つ値 55 である可能性が浮上する．この時点では，推定の号文の元値推定の信頼度を高めることできる．

信頼度は当該ドメインにおける頻度 10 を持つ属性値の数に依

また，暗号文が決定論的でない場合にも，問合せ履歴を収集出来るという現実的な仮定のもとでは，攻撃者が暗号文の元となった平文の多様性を収集可能である可能性がある．すなわち，存するため，攻撃者は自身の推定の確からしさを検証することができない．
一方，問合せ履歴を更に観察すると，結果集合 B, C も出現

平文が共通するタプルの数を漏洩しない問合せ手法を用いなけ

頻度がそれぞれ 6, 1 である平文 ptextB , ptextC を元とする暗れば，同様に推論攻撃の信頼度を高められる危険性がある．

号文の集合に一致する可能性が高く，かつ昇順に B, A, C ，もしくは C, A, B の大小関係があることがわかる（ここではタプル

例 2:

暗号化された属性の部分的な頻度分布，および問合せ

間の順序関係から，B, A, C の順であるとわかったとする）．先履歴を攻撃者が知り得た事例を考える (図 2)．この場合，ドメほど推定した ptextA = 55 の前後の頻度分布と ptextB , ptextC

インの最小・最大値を高い信頼度のもとに推定することは困難の頻度とを総合すると，両者には一致が見られ，結果集合 A のであるため，例 1 のような格納データの多様性に基づく推論攻

性質のみに基づいた場合よりも ptextA = 55 という推定の信撃の精度向上は非現実的であると考えられる．その一方で，攻頼度は高まったといえる．これを随時繰り返すことで，攻撃者撃者が知る頻度分布の範囲内では，精度の高い推論攻撃が可能が持つ部分頻度分布に出現する値と暗号文とを，高い信頼度のである．

もとに対応付けすることが可能となる．加えて，部分頻度分布

例えば，図 2 のような部分的頻度分布（図中実線部）と問合に対応付けされた暗号文との前後関係や問合せ履歴から，分布せ履歴の知識を攻撃者が持つことを考える．まず，問合せ履歴の知識を持たなかった暗号文にまで推論攻撃を波及できる危険から，結果集合 A に属するタプル群は，範囲検索の結果では性も存在する．

なくある共通の平文に対する一致検索の結果である可能性が高

2. 4 バケット化

いことがわかる．すなわち，結果集合 A は，出現頻度が 10 で

文献 [1] [2] では，検索対象となる sensitive 属性のドメインをタグによって識別される複数の部分タプル集合（バケット）に分割し，これらのタグを検索語として問合せに利用するバケッ
ト化（Bucketization）手法を提案している．バケットのタグは包含する値とは無関係に選ばれ，各バケット内では，暗号化タ
プルが互いに識別不能であることを保証する．利用者は属性値a に対する問合せ用の属性値 a∗ として a が属するバケットのタグを利用し，k 個以上の要素を含むバケット単位で取得する
ことで，k-匿名性による問合せ結果の安全性を保証する．
図1

ドメインの最小値，最大値に関する知識

一方，この方法では，問合せ結果中に含まれる偽陽性のフィルタリングコストと保証される安全性（匿名性）とがトレード
オフの関係にある．また，更新の結果として匿名性が保証されないバケットが生じた場合には，分割の境界を再構築する必要がある．しかし，その際のタプルの移動を追跡することによって，識別不能であったタプル間の順序関係が徐々に漏洩してしまう可能性がある．

3. 準

備

3. 1 提案手法の概要
図 2 部分的頻度分布および問合せ履歴に関する知識

従来，暗号化データに対する効率的検索を目指す研究では，

索引付けのためタプル単位での順序関係を漏洩することを許容してきた．一方，こうしたタプル単位の順序関係情報は攻撃者にとって有用な知識となり，利用者が委託する機密データに対する脅威を著しく増大させる危険性がある．そこで我々は，OPES [3] や Lu の研究 [5] において許容されるタプル単位の情
図 4 変換前と変換後のテーブル例

報漏洩を，ドメイン分割（バケット化） [1] [2] に類似する匿名化手法によってタプル集合単位まで粗くし，各タプルに対する推論攻撃のリスクを低減する索引手法を提案する．
この手法では，検索対象となるドメインを要素数と順序関係に基づき有限個のバケットに分割し，これらバケットを葉として暗号化 B+木を構築する．バケットに含まれる各タプルは互
いに識別できない形で暗号化しており，かつ平文の値が同一である複数の暗号文を異なるバケットに分配可能とする索引のキー定義を与えることで，タプル単位での情報漏洩が起きない

図 5 匿名化バケットと索引付け (s = 12 )ことを保証する．また，内部ノードが持つ暗号化キーの安全性，および分割に際してバケット内のタプルが追跡不能であること

メータ s (0 < s < 1) を入力として行う．具体的には，各バを保証し，偽陽性のフィルタリングコストと安全性を考慮したケット中での要素数が占める割合が s を超える属性値を偏りが動的なバケット更新手法を与える．

あると判断し，平滑化の対象とする．

3. 2 信用範囲と攻撃モデル

また，これらのパラメータのみを用いた平滑化では，ある値

本研究においては，図 3 のように表される DaaS モデル [1] [2]がバケット間を次々と移動して飛び（値 v がバケット Bi , Bi+2を想定する．このモデルは，データの所有者かつ検索者であるに含まれるが Bi+1 に含まれない等）が生じ，その値の問合せ

1 人の利用者（図 3 中の User と Client とを合わせて利用者と結果中に全要素が偽陽性となるバケットが含まれてしまう可呼ぶ）とデータベースサービスの提供者である 1 台のサーバで能性がある．このようなバケットの混入は，問合せ対象と同バ構成される．ここで，サーバは外部からの侵入に対して脆弱なケットに含まれ付随して得られる偽陽性に比べ，利用者による可能性があるため，委託された利用者の機密データに対して能フィルタリングコストを不必要に増大させてしまう．そこで，動的に攻撃を仕掛ける可能性がある潜在的な攻撃者であると見

平滑化の対象とする属性値がどのバケットに含まれているかをなす．したがって利用者はサーバを完全には信用しておらず，

あらかじめ把握し，飛びを生じさせる移動は許容しないという

情報は信頼できるクライアントを介し全て暗号化したうえで制約を付ける（以下，分配制約と呼ぶ）．これらの操作の基本

サーバに送信する．攻撃者はこれらの暗号化データを全て見渡的な流れを以下に示す．

すことができるが，利用者によって施された暗号化そのものを破ることは出来ない．また，利用者 - サーバ間の通信路は保護（ 1 ） ドメインの最小値 Vmin を始点とし，順に整数乱数 nされており安全だが，利用者から送信されるメッセージは攻撃(bmin <=n<= bmax ) 個のタプルを 1 つのバケットとしてランダ者にとって可視であるものとする．

ムなラベルを割り当てる．

攻撃者は，委託された暗号化データや利用者とのインタラク（ 2 ） 各バケット Bi 中での要素数が占める割合が s を超えションから得られる情報，および事前知識を駆使し，出来る限る属性値 d を，順序関係における前後のバケット Bi−1 中の d

り高い信頼度で各暗号文の真の値を推論しようとする．

を超えない最大値，もしくは Bi+1 中の d より大きい最小値

4. タプル情報の漏洩を防止する匿名化索引
4. 1 バケット分割と入れ替え，頻度を平滑化する．前後のバケットに交換可能な値が無ければ，bmin , bmax , および s の制約を破らない限りで dを分配する．

秘匿の対象となる属性のドメインを分割し，問合せの単位となるタプル集合（バケット）を生成する．この分割は，対象属性のドメインに出現する値の集合 V ，各値 v (∈ V ) の頻度

f (v) の集合 F ，および各バケットに含まれるタプル数の最小値と最大値を表すパラメータ bmin , bmax (∈ N, bmin < bmax )を入力として行う．
ここで，同じ属性値に対する暗号化タプルを必ず同一のバケットに格納すると定めると，分布や問合せ頻度に大きな偏りがある場合にバケット中の暗号化タプルの真値を高い信頼度で推定可能となってしまう危険がある．そこで，バケット内の属性値の偏りを緩和するための平滑化を，安全性に関するパラ

図 4 (a) は変換前のテーブル，(b) は属性 salary についてバケット分割による匿名化を行いレコード単位の暗号化を施した
うえでサーバに送信されるテーブルである．また，図 5 (a) は
上述の手順 1 で得られる初期分割後のバケット，(b) は手順 2により平滑化を施したバケットである．

4. 2 暗号化 B+木索引
先述のドメイン分割および頻度平滑化によって得られたバケットに対し，範囲述語暗号 (Range Predicate Encryption :RPE) を利用した暗号化 B+木による索引付けを施す．RPE は
公開鍵暗号をベースとしたもの [21] と 共通鍵暗号をベースとしたもの [22] [5] [17] に大別されるが，ここでは，Lu の研究 [5]示す．文献 [5] ではセグメント木を利用し効率化した構築手法

にて提案されている共通鍵方式による RPE を利用する．

を提案しているが，ここでは基本的な手法のみに言及する．

以下に，文献 [5] において提案されている共通鍵 RPE の暗号化スキームを概観する．ここでは，安全性に関する証明は省

RPE Setup(1k , [0, T − 1]): セキュリティパラメータ 1k およ

略する．この構築法は，Shen らの研究 [23] で提案されているび範囲 [0, T − 1] を入力とし，SSW Setup(1k ) によって共通鍵内積述語暗号（SSW と略記する）をベースとしている．

SSW の暗号化スキームは，以下の確率的多項式時間アルゴリズ
ムで与えられる．ここで G は，1k をセキュリティパラメータとし，組 (p, q, r, s, G, GT , e) を生成するアルゴリズムである．
ただし p, q, r, s は 4 つの相異なる素数であり，G, GT はそれらの積 N = pqrs を位数とする巡回群，e は e : G × G → GT を

RPE Encrypt(SK, t):

点 t を 入 力 と し ，i = t の とき xi = 1，i =| t の と き xi = 0 と し て ベ ク ト−→
ル x = (x0 , · · · , xi , · · · , xT −1 ) を 生 成 す る ．次 に ，→− を生成し，SSW Encrypt(SK, −x ) により暗号文 CT→
x

出力する．

RPE GenToken(SK, Q):

満たす双線形写像である．

SSW Setup(1 ): G(1 ) を実行し，組 (p, q, r, s, G, GT , e) をk

秘密鍵 SK を生成，出力する．

k

範囲クエリ Q を入力とし，i ∈ Q の と き v i = 0，i ∈/ Q の と き vi = 1 と→してベクトル −v = (v , · · · , v , · · · , v) を生成し，0i

T −1

得 る ．こ こ で ，位 数 p, q, r, s に 対 応 し た 部 分 群 に よ り，→−
SSW GetToken(SK, −v ) により検索トークン T K→
v を

G = Gp × Gq × Gr × Gs と表す．次に，Gp , Gq , Gr , Gs

生成，出力する．

−−−
v , CT→x ): SSW Query(T K, CT→x ) の結果か ら 生 成 元 gp , gq , gr , gs を そ れ ぞ れ 取 り 出 す．ま た ， RPE Query(T K→
を出力する．
h1,i , h2,i , u1,i , u2,i ∈ Gp を各 i (= 1, 2, · · · , n) に対して

ランダムに選ぶ．秘密鍵 SK は，以下のようになる．

暗号化 B+木の各内部ノードに格納する RPE キーに反映すSK = (gp , gq , gr , gs , {h1,i , h2,i , u1,i , u2,i }ni=1 ).

る点情報は，葉ノードにあたるバケットの内容からボトムアッ→→
SSW Encrypt(SK, −x ): −
x = (x1 , · · · , xn ) ∈ Zn
N とする．
y, z, α, β ∈ ZN ，S, S0 ∈ Gs をランダムに選び，R1,i , R2,i ∈
Gr を各 i (= 1, 2, · · · , n) に対しランダムに選ぶ．暗号文−
CT→
x は，以下のようになる．

プに決定する．ある内部ノード I の 2 つの子ノード Bi , Bi+1

0

ト Bi の最大値) を反映した RPE をキーとして格納する．
ここでは簡単のため，Lu らの研究 [5] と同様に，検索可能な
数値属性が暗号化テーブル上に 1 つだけしか存在しないものと→→SSW GenToken(SK, −v ): −v = (v1 , · · · , vn ) ∈ Zn
N とする．
f1 , f2 ∈ ZN ，R, R0 ∈ Gr をランダムに選び，r1,i , r2,i ∈ZN ，S1,i , S2,i ∈ Gs を各 i (= 1, 2, · · · , n) に対しランダム−に選ぶ．検索トークン T K→
v は，以下のようになる．
n
Y

−r

r

1

する．多次元範囲検索への拡張については，今後の課題とする．
初期動作として利用者はデータの暗号化，バケット分割，および暗号化 B+木による索引付けを自身の秘密鍵を用いて行った
後，それらをサーバに送信する．

4. 3 問 合 せ2,i
h1,i 1,i · h2,i, C
B K =R ·
C
B
i=1
C
B
C
B
n
Y −r1,iB−r2,i CB K0 =R0 ·u1,i · u2,i ,C
C.
B
−
T K→
v =B
C
i=1
C
B
C
B
B {K = g r1,i · g f1 vi · S , C
C
B
1,i
1,i
p
q
A
@

以下に，提案手法における範囲問合せの流れを示す．一致問
合せは範囲問合せの範囲の最小値と最大値が一致する特殊型と見なすことができ，同様の手続きによって実行可能である．ただし，検索対象のドメインを [Dmin , Dmax ] とし，秘密鍵 SK
を RPE Setup(1k , [Dmin , Dmax ]) によって予め生成していf2 v
r
K2,i =gp2,i · gq i · S2,i }n
i=1

るとする．

n
−
−
−
SSW Query(T K→
v , CT→x ): CT→x = (C, C0 , {C1,i , C2,i }i=1 )，n−SK→v = (K, K0 , {K1,i , K2,i }i=1 ) と表記する．SSW Query→→
は，以下の等式が成立するとき，すなわち条件 h−x,−vi=

0 mod N を満足するときだけ “1” を出力し，それ以外では “0” を出力する．

e(C, K) · e(C0 , K0 ) ·iの最小値, Bmax
: バケット Bi の最大値) を反映した RPE をii
範囲が無い場合，その I は二重化せず，Bmax
(Bmax
: バケッ

C
B
C
B
C0 = S0 · gpz ,C
BC.
CT = BCB
yz
αxC
B {C1,i = h1,i · u1,i · gq i · R1,i ,
A
@
y
z
βxi
n
C2,i = h2,i · u2,i · g· R2,i }i=1

0

i+1
i+1
i
IL , IR とし，IL に Bmax
，IR に Bmin
(Bmin
: バケット Bi+1

キーとして格納する．一方，図 5 (b) のように子ノードに重複

1

C = S · gpy ,が図 5 (a) のように重複範囲を持つ場合，その I を二重化して（ 1 ） 利用者は平文の範囲検索クエリ Q = [Qmin , Qmax ] を生成する．
（ 2 ） 利用者は RPE GenToken(SK, [Dmin , qmin − 1])によって検索トークン tkL ，RPE GenToken(SK, [qmax +1, Dmax ]) によって検索トークン tkR をそれぞれ生成し，サーnY?

e(C1,i , K1,i ) · e(C2,i , K2,i ) = 1.

i=1

バに送信する．
（ 3 ） サーバは tkL をもとに，暗号化 B+木の各内部ノー
ド キ ー ki (i = 1, · · · , m) を 昇 順 に 走 査 す る ．内 部 ノ ー

次に，SSW をベースとした RPE の暗号化スキームを以下にド I が 二 重 化 さ れ て い る 場 合 ，IL の キ ー と 照 合 を 行 う．

RPE Query(tkL , ki ) が “1” となる場合，枝 bi が指すノー（ 7 ） 利用者は更新後のバケット中の最大値を反映した述語

ドに進む．RPE Query(tkL , km ) も “1” にならない場合，枝暗号 E 0 を自身の秘密鍵で生成し，更新情報と共にサーバに送bm+1 が指すノードに進む．

信する．

（ 4 ） サーバは tkR をもとに，暗号化 B+木の各内部ノー（ 8 ） サーバは受け取った情報をもとに暗号化 B+木を更新

ド キ ー ki (i = 1, · · · , m) を 降 順 に 走 査 す る ．内 部 ノ ーする．

ド I が 二 重 化 さ れ て い る 場 合 ，IR の キ ー と 照 合 を 行 う．

RPE Query(tkR , ki ) が “1” となる場合，枝 bi+1 が指す
ノードに進む．RPE Query(tkR , k1 ) も “1” にならない場合，(3) で得られた枝が指すノードに進む．
（ 5 ） (3), (4) の走査が葉ノードのバケット Bmin , Bmax に達したら，バケット Bn (n = min, min + 1, · · · , max) を全て取得し結果として利用者に返す．
（ 6 ） 利用者は問合せ結果を受け取り，自身の秘密鍵で中身を復号して偽陽性をフィルタリングする．

図7

バケットの分割 (s = 21 )タプルの削除，バケットのマージ（ 1 ） 利用者は削除したいタプルの値を反映した述語暗号 Eを自身の秘密鍵を用いて生成し，サーバに送信する．
（ 2 ） サーバは E をもとに該当するバケット（もしくはバケット群） B を探索し，利用者に返す．
（ 3 ） 利用者は B を受け取り，対象タプルを削除する．こ図 6 範囲問合せの流れ (s = 12 )4. 4 バケットの更新
タプルの追加（削除）に伴い，匿名化バケットを分割（マージ）することを考える．以下に，利用者があるタプルを追加（削除）する際の手続きを示す．
タプルの追加，バケットの分割（ 1 ） 利用者は追加したいタプルの値を反映した述語暗号 Eを自身の秘密鍵を用いて生成し，サーバに送信する．
（ 2 ） サーバは E をもとに該当するバケット（もしくはバケット群） B を探索し，利用者に返す．

こで，バケットの要素数が下限を下回る場合は (4) に進み，そうでなければ (6) に進む．
（ 4 ） 利用者は，B 中の最小値および最大値に基づいて Bの前後の隣接するバケット B−1 , B+1 をサーバから取得し（※片側しか存在しない場合は一方），B とマージする．
（ 5 ） B−1 , B, B+1 中のタプルをソートし，4. 1 項に示す手法で分割・ラベル付けを行うことでバケット B1 , B2 を得る．
（ 6 ） 利用者は更新後のバケット中の最大値を反映した述語
暗号 E 0 を自身の秘密鍵で生成し，更新情報と共にサーバに送信する．
（ 7 ） サーバは受け取った情報をもとに暗号化 B+木を更新
する．

（ 3 ） 利用者は B を受け取り，対象タプルを追加する．ここで，要素の偏りが s を超える場合は (4)，バケットの要素数が上限を超える場合は (5)，に進み，そうでなければ (7) に進む．
（ 4 ） 利用者は，B 中の最小値および最大値に基づいて Bの前後の隣接するバケット B−1 , B+1 をサーバから取得し（※片側しか存在しない場合は一方），B とマージする．
（ 5 ） 利用者は B に含まれる最小値，最大値をそれぞれ反映した述語暗号 Emin , Emax を利用し，サーバから B 中の要素に関連する索引のノードを取得する（※ バケット分割における分配制約の判定に利用する）．
（ 6 ） 利用者は B 中のタプルをソートし，4. 1 項に示す手法
で分割・ラベル付けを行うことでバケット B1 , B2 を得る．こ

図 8 バケットのマージ (s = 12 )の際，全てのタプルは摂動を加えて暗号化しなおす．
本手法が利用するバケット化は，偽陽性を多く含むタプル集

合を結果として返すとフィルタリングコストが高くなり，偽陽返す．利用者はバケット B1 にタプルを追加するが，要素数が性の少ないタプル集合を返すと安全性が低下するというトレー

7 となり最大数を超過してしまう．そこで，利用者は B1 中のドオフを抱えている．そこで，4. 1 項にて述べたように，各バ

タプルを一旦全て復号し，4. 1 項の手続きにより分割されたバケットが保持できるタプル数を制限するパラメータを与え，要ケット B11 = {83, 85, 87}, B12 = {85, 87, 93, 95} を得る．こ

素数をベースとしたバケット分割およびマージを行うことでの際，バケット内のタプルは全て摂動を加えて再暗号化する．

安全性とフィルタリングコストのバランスを取る．一方，各バ

こ の 分 割 に よって B1 を 指 す ポ イ ン タ に 対 応 し た キ ー

ケットの中に含まれる暗号化タプルがサーバにとって可視であRPE Encrypt(SK, [93, 95]) (SK : 利 用 者 の 秘 密 鍵) をることを考慮すると，このようなバケット分割に伴い，当初は

更 新 す る 必 要 が 生 じ る た め ，利 用 者 は B11 と B12 に 付 加

匿名化されていたタプル単位の順序関係が徐々に漏洩してしましたラベルをテーブル内の各タプルに反映させると共に，う可能性がある．したがって，バケット分割の際には包含されRPE Encrypt(SK, [85, 87]) を IDX Insert によって挿入る全てのタプルを摂動を加えた上で再暗号化し，分割前後で追する．この例では，挿入先の内部ノードが格納するキー数が最跡不能とすることでタプル単位での順序関係漏洩を防ぐ．

大値を超えたとし，キー RPE Encrypt(SK, 120) が平衡化のため移動する．

索引の更新
暗号化 B+木索引については，以下の IDX 命令セットを介してサーバ側で更新する．
−−
IDX Insert(T K→
v , CT→x ):挿入したい索引キー k から

RPE Encrypt(SK, k)，RPE GenToken(SK, [k]) によ−−って利用者が生成した暗号文 CT→
x ，トークン T K→
v を受け取り，トークンによって指定された葉ノードの該当位置（二重化されたノードのキーを用いる場合，その最小値，最大値それぞれを用いて位置を定める）にキーを挿入する．ノードに格納できるキーの最大数を超えた場合，葉ノードを分割し，中央のキーを親ノードに挿入する．以後，分割と挿入を再帰的に行う．
−−
IDX Delete(T K→
v , CT→x ): 削 除 し た い 索 引 キ ー k か ら ，

RPE Encrypt(SK, k)，RPE GenToken(SK, [k]) によ−−って利用者が生成した暗号文 CT→
x ，トークン T K→
v を受け取り，トークンによって該当する葉ノードを発見する．この際，通過した内部ノードキーの位置を記憶しておく．続い
図9て葉ノード中の該当位置（二重化されたノードのキーを用

索引の更新 (s = 21 )いる場合，その最小値，最大値それぞれを用いて位置を定める）のキーを削除するが，ノードに格納できるキーの最小数を下回った場合，通過した内部ノードのキーをもとにノードをマージし，キーを置換・削除する．

5. まとめと今後の課題
従来の検索効率を重視するプライバシ保護型検索手法では，−−
IDX Replace(T K→
v , CT→x ): 置 換 対 象 と す る 索 引 キ ー k1

暗号化データに対する効率的な範囲検索をサポートすることにか ら RPE GenToken(SK, [k1 ]) に よって 利 用 者 が 生

主眼を置き，タプル単位での順序関係を漏洩することを許容し−成 し た ト ー ク ン T K→
v ，置 換 す る 新 キ ー k2 か らてきた．しかし，こうした順序関係情報の漏洩は完全な知識を

RPE Encrypt(SK, k2 )， によって利用者が生成した暗持たない攻撃者に対しても推論攻撃の糸口を与える危険性があ−
号文 CT→
x を受け取り，トークンによって指定された葉ノーる．そこで我々は，タプル集合単位でしか順序関係情報を漏洩

ドの該当位置のキーを置換する．

しない暗号化索引により，大きなオーバーヘッドを課すこと無く各タプルに対する推論攻撃のリスクを低減する手法を提案

以下に，この命令セットを用いた索引の更新動作の例を示す．
例 3:

図 9 に示すような索引に，値 85 を持つタプルを追加する際の動作を考える．ここで，各バケットは最小 3 個，最大6 個の要素を持つことができるとする．
利用者は値 85 を反映した述語暗号を自身の秘密鍵で生成し，サーバに送信する．サーバは与えられたトークンをもとにバケット B1 = {83, 85, 87, 87, 93, 95} を発見し，これを利用者にした．
今後の喫緊の課題として，提案手法の安全性や効率に関する評価実験，およびバケット内の偏りがどの程度許容できるのかに関する検討を行う予定である．また，本論文では，1 人の利用者と 1 台のサーバを想定し議論してきたが，DaaS の現実的なモデルとしては複数の利用者と複数のサーバを想定する必要があると考えられる．複数の利用者を想定する場合には，提案

手法の根幹である述語暗号化に用いる秘密鍵の運用が問題となる．これについては，Lu らの研究 [5] のように単一の信頼できる管理者を想定し，各利用者はその管理者を介してデータの暗[11]号化や検索用トークンの発行を行うようモデルを修正することが考えられる．この他に，岡本らが提案している階層的述語暗号 (Hierarchical Predicate Encryption : HPE) [24] を用いた

[12]

権限委譲が利用できると考えているが，これらの拡張は今後の課題である．一方，複数のサーバが存在する環境においても提[13]

案手法はそのまま適用できるのではないかと考えているが，これについても詳細な検討が必要である．
また，提案手法は複数の（秘匿の対象となる）検索可能属性[14]を有する暗号化リレーショナルデータベースに適用した場合，バケット分割・マージに際してタプルの追跡不能性を保証することができない．これについては，空間充填曲線および多次元[15]

空間分割手法を導入し，複数の検索可能属性を単一属性として表現することで解決できると考えている．一方，こうした多次元空間分割手法を導入すると，提案手法を 1 次元データにおいて運用した場合に比べ利用者側でフィルタリングすべき偽陽性が大きく増加する可能性が高い．この点についての検証，およ

[16]
[17]

び手法の修正も今後の課題である．

謝

辞
[18]

本論文の執筆にあたり，筑波大学大学院 システム情報工学研
究科の川本 淳平氏より多くの有益な助言を頂きました．心より感謝申し上げます．

[19]
文

献

[1] H. Hacıgümüş, B. Iyer, C. Li, and S. Mehrotra. Executing
SQL over encrypted data in the database-service-provider
model. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, 2002.
[2] B. Hore, S. Mehrotra, and G. Tsudik. A Privacy-Preserving
Index for Range Queries. Proceedings of 30th international
conference on Very large data bases, Vol. 30, pp. 720–731,
2004.
[3] R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Order Preserving Encryption for Numeric Data. SIGMOD ’04 Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pp. 563–574, 2004.
[4] H. Kadhem, T. Amagasa, and H. Kitagawa. MV-OPES:
Multivalued-Order Preserving Encryption Scheme: A Novel
Scheme for Encrypting Integer Value to Many Diﬀerent Values. IEICE TRANSACTIONS on Information and Systems, Vol. E93-D, No. 9, pp. 2520–2533, 2010.
[5] Y. Lu. Privacy-Preserving Logarithmic-time Search on Encrypted Data in Cloud. In 19th Annual Network andDistributed System Security Symposium (NDSS Symposium’12), 2012.
[6] A. Shamir. How to share a secret. Communications of theACM, Vol. 22, No. 11, pp. 612–613, 1979.
[7] G. R. Blakley and C. Meadows. Security of ramp schemes.
In Proceedings of CRYPTO’88, LNCS403, pp. 252–268,
1990.
[8] NRI セ キュア テ ク ノ ロ ジ ー ズ 株 式 会 社. SecureCube Secret Share, 2010. http://www.nri-secure.co.jp/service/
cube/secretshare.html.
[9] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano.
Public key encryption with keyword search. In Proceedingsof EUROCRYPT’04, Vol. LNCS 3027, pp. 506–522, 2004.
[10] D. X. Song, D. Wagner, and A. Perrig. Practical techniques

[20]

[21]

[22]

[23]

[24]

for searches on encrypted data. Proceedings of the 2000
IEEE Symposium on Security and Privacy, pp. 44–, 2000.
M. Bellare, A. Boldyreva, and A. ONeill. Deterministic andeﬃciently searchable encryption. CRYPTO’07 Proceedingsof the 27th annual international cryptology conference on
Advances in cryptology, pp. 535–552, 2007.
B. Chor, O. Goldreich, E. Kusheilevitz, and M. Sudan. Private Information Retrieval. J. ACM, Vol. 45, No. 6, pp.
965–982, 1998.
C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. EUROCRYPT’99 Proceedings of the 17th international conference on Theory and application of cryptographic techniques, pp. 402–414, 1999.
S. Wang, D. Agrawal, and A.E. Abbadi. Generalizing PIR
for Practical Private Retrieval of Public Data. Proceedingsof the 24th annual IFIP WG 11.3 working conference on
Data and applications security and privacy, pp. 1–16, 2010.
S. Kaneko and C. Watanabe. Semi-Shuﬄed BF : Performance Improvement of a Privacy-Preserving Query Method
for a DaaS Model using a Bloom Filter. The 2011 International Conference on Parallel and Distributed Processing
Techniques and Applications (PDPTA ’11), 2011.
E. Goh. Secure indexes, 2004. http://eprint.iacr.org/
2003/216/.
J. Kawamoto and M. Yoshikawa. Private Range Query by
Perturbation and Matrix Based Encryption. In 6th International Conference on Digital Information Management(ICDIM 2011), pp. 211–216, September 2011.
J. Kawamoto. A Locality Sensitive Hashing Filter for Encrypted Vector Databases. Proceedings of International
Workshop on Privacy-AwaRe Intelligent Systems (PARIS
2012), December 2012.
A. Boldyreva, N. Chenette, and A. O’Neill.
OrderPreserving Encryption Revisited: Improved Security Analysis and Alternative Solutions. Advances in Cryptology CRYPTO 2011 - 31st Annual Cryptology Conference, Vol.
6841, p. 575, 2011.
A. Boldyreva, N. Chenette, Y. Lee, and A. O’Neill. OrderPreserving Symmetric Encryption. EUROCRYPT ’09 Proceedings of the 28th Annual International Conference on
Advances in Cryptology: the Theory and Applications of
Cryptographic Techniques, pp. 224–241, 2009.
D. Boneh and B. Waters. Conjunctive, subset, and range
queries on encrypted data. Proceedings of the 4th conferenceon Theory of Cryptography, pp. 535–554, 2007.
C. Blundo, V. Lovino, and G. Persiano. Private-key hidden
vector encryption with key confidentiality. Cryptology and
Network Security Lecture Notes in Computer Science, Vol.
5888, pp. 259–277, 2009.
E. Shen, E. Shi, and B. Waters. Predicate Privacy in Encryption Systems. In Theory of Cryptography, Vol. 5444,
pp. 457–473, 2009.
T. Okamoto and K. Takashima. Hierarchical Predicate Encryption for Inner-Products. In 15th International Conference on the Theory and Application of Cryptology andInformation Security, pp. 214–231, 2009.