Semi-ShuﬄedBF:ブルームフィルタを用いた安全かつより高速なプライバシ保護検索手法の提案
金子静花

1(指導教員：渡辺知恵美)♦テーブル変換
クライアント側のテーブル testtable に対して，サーバ側には etuple と bﬁndex という 2 つの属性で構成されているテーブル testtables が用意される．etupleには，タプル全体を暗号化した値が格納され，bﬁndexはタプルに関する検索用索引である．
♦ブルームフィルタ索引の生成
bﬁndex を生成するための語は属性名と属性値からなっており (➀)，まずそれらに対して複数のハッシュ関数を適用する (➁)．ハッシュ関数には HMAC(かぎ付きハッシュによるメッセージ認証関数) を用い，必要なハッシュ関数の数だけ鍵を用いる．次にこれらのハッシュ値に対して etuple を鍵として再び HMAC を適用する (➂)．
これにより，複数のタプルが同じ値を持っていた場合も 2 回目のハッシュ関数適用により異なる場所にビットが立ち，攻撃者がビットパターンから元データの特徴を推測することができなくなっている．
なお etuple によるハッシュ関数の適用を行わず，一度目のハッシュ関数の結果を用いて生成するブルームフィルタを NonShuﬄedBF(NSBF) と呼ぶことにする．

はじめに

DaaS サービスでは，ユーザはインターネット上の外部の第三者が管理するデータベースの機能をネットワーク経由でサービスとして利用することができる．
このような環境でユーザがデータ管理者から機密情報を守るための手段として，プライバシ保護検索というデータを暗号化した状態でデータベースに保存し，暗号化したまま問合せを施す手法がこれまで多く研究されており，我々もまた先行研究 [1] にてブルームフィルタを用いたスキーマ情報を隠蔽するプライバシ保護検索手法を提案した．
先行研究では，各 taple に対して問い合わせ用のブルームフィルタを生成し，taple 毎のキーを用いてシャッフルする (ShuﬄedBF) ことにより，ブルームフィルタのビットパターンの漏えいを防いでいたが，この手法
では，問い合わせの際，各 taple でハッシュ関数を適応するので，安全であるが時間がかかってしまう．逆に，ブルームフィルタのシャッフルを行わない (NonShuﬄedBF) と，ビットパターンの推測が可能である．
そこで，問い合わせの際 1 段階の絞り込みに NonShuﬄedBF をもちい，2 段階の絞り込みに ShuﬄedBFを用いる手法 (Semi-ShuﬄedBF) を提案する．

2

2.2

問合せ

問合せ変換とサーバでの問合せ処理を図 2 に示す．

ShuﬄedBF

ShuﬄedBF(SBF) はブルームフィルタを用いることで属性毎ではなくタプル毎に索引を構成したプライバ
シ保護検索手法である．ブルームフィルタとは，集合にある要素が含まれるかどうかを高速に検索するための索引で，空間効率がよく検索が高速，or 演算が可能，偽陽性 (false positive) を持つ．
2.1 検索索引の生成
先行研究 [1] にて提案した手法におけるテーブル変換とブルームフィルタ索引の生成例を図 1 に示す．

図 2: 変換前後の SQL と問合せ処理手順♦問合せ変換サーバに発行される問合せ文は，各タプルの属性に対する検索条件が索引 bﬁndex に対する条件に置き換えられているため，データベース管理者は何の属性値を用いてどのような検索条件を指定したか読み取ることができない．
♦問合せ処理まずクライアントで検索条件文から検索用の語を生成し (➀)，1 回目のハッシュ関数を適用し (➁) た SQL
文をサーバに送る．サーバ側ではタプル毎に smatch関数が実行され，各タプルが問合せ条件に合致するかチェックされる．smatch 関数ではクライアントで生成されたハッシュ値に対して etuple を鍵にしてハッシュ関数を適用し (➃)，その値でブルームフィルタへのマッチングを行う (➄)．

図 1: 変換前後のテーブルとブルームフィルタ索引生成75

3

Semi-ShuﬄedBF

3.1

基本的な考え方A2 : g2 (x) = −2x + 9，A3 : g3 (x) = 3x + 2 を用意している．
まず ShuﬄedBF と同様に検索語を生成し，式 (1)を適用し，ブルームフィルタを生成する．次に ShufﬂedBF 生成 (2．1 項参照)．そして NonShuﬄedBF とShuﬄedBF とを合成した結果を Semi-ShuﬄedBF として bﬁndex に保存する．

Semi-ShuﬄedBF では ShuﬄedBF による索引に加えて，NonShuﬄedBF による索引を付与することでShuﬄedBF 索引によるハッシュ適用回数を減らし処理速度を向上させる．
NonShuﬄedBF 索引では以下のハッシュ関数を適用する．
′hi (x) = ⌈|gj (hi (x) mod ⌈m/l⌉)|⌉ mod m … (1)
ここで m はブルームフィルタのビット長， l は 2以上の整数をとるパラメタとし，関数 gj は元テーブ
ル R(A1 , …, An ) における属性 Aj 毎に設定する．
ShuﬄedBF ではハッシュ値に対してブルームフィルタのビット長である m の剰余を求めていたのに対し，NonShuﬄedBF では ⌈m/l⌉ の剰余を求めている． l の値を大きくすることで NonShuﬄedBF による擬陽性をあえて高くし，ブルームフィルタによる元データの推測が難しくしている．関数 gj は，属性 Aj ごとにビットの立つ位置を定めるための関数で，単一のブルームフィルタ内でのビットを立てる位置の重複を防ぐ．
また，NonShuﬄedBF と ShuﬄedBF を別々に用意するのではなく，これらを合成し一つのブルームフィルタとすることによって NonShuﬄedBF における元データの推測をより難しくすることができる．合成により擬陽性は高くなる可能性はあるが，これはブルームフィルタのビット長 m を少し長くすることによって調整が可能であると考えられる．

3.3 問合せの方法
Semi-ShuﬄedBF の問合せの方法は，(1)NonShuﬄedBF で検索し，問合せ条件に該当すると判断したもののみ(2)ShuﬄedBF で検索する，という 2 段階で行われる．
以下図 4 に Semi-ShuﬄedBF の問合せ手法を示す．

3.2 データの挿入方法
Semi-ShuﬄuedBF のデータの挿入方法は以下の 3 段階に分けられる．
(1)NonShuﬄedBF の生成 (図 3 : 1〜3)
(2)ShuﬄedBF の生成 (図 1)(3)ShuﬄedBF と NonShuﬄedBF とを合成 (図 3 : 4)
した結果を Semi-ShuﬄedBF として bﬁndex に保存
以下図 3 に Semi-ShuﬄedBF の生成例を示す．

図 4: 問合せ実行例
まずクライアントで検索条件文から検索用の語を生成し，NonShuﬄedBF 用ハッシュ関数，ShuﬄedBF 用ハッシュ関数を各々適用しサーバに送る．サーバ側ではまず NonShuﬄedBF 用ハッシュ関数から得られた値(NSBF) でマッチングを行い，そこから得られたものにだけ ShuﬄedBF 用ハッシュ関数から得られたブルー
ムフィルタ索引タプル毎に etuple を鍵にしてハッシュ関数を適用し，その値 (SBF) でブルームフィルタへのマッチングを行う．
2 段階の絞り込みにすることでサーバ側でハッシュ関数の適応回数を減らすことができ，すべてのタプルにテーブルのスキーマ情報や検索条件に数や演算の種類の隠蔽をしつつ処理速度も向上させることができる．

4

まとめと今後の課題

本稿では先行研究の提案手法 (ShuﬄedBF) に変換関数を適用せずに生成されたブルームフィルタ (NonShuﬄedBF) を組み合わせることで安全性を損なわず高速にプライバシ保護検索ができる Semi-ShuﬄedBFを提案した．
今後は性能測定を実施し，Semi-ShuﬄedBF における更なる安全性と性能のトレードオフを見極めて行きたい．

参考文献

図 3: Semi-ShuﬄedBF の生成例

[1] Watanabe C. and Arai Y.:“Privacy-Preserving
Queries for a DAS model using Two-Phase Encrypted
Bloomfilter,” International Conference on Database
Systems for Advanced Applications, pp.491-495 (2009)

例では m = 512，l = 16 とし， 属性 A1 : ID，A2 : name，A3 : age に対して A1 : g1 (x) = 2x + 1，76