論文 / 著書情報
Article / Book Information
論題(和文)

階層的なアクセスレベル制御を行うRDFデータに対する集約計算結果の推定

Title(English)
著者(和文)

三上 英明, 杉原 弘祐, 横田 治夫

Authors(English)

Hideaki Mikami, Kousuke Sugihara, Haruo Yokota

出典(和文)

第8回データ工学と情報マネジメントに関するフォーラム論文集, , ,F8-4

Citation(English), , ,発行日 / Pub. date

2016, 3

F8-4

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2016 F8-4

階層的なアクセスレベル制御を行う
RDF データに対する集約計算結果の推定
三上 英明†

杉原 弘祐†

横田 治夫†† 東京工業大学大学院情報理工学研究科計算工学専攻 〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †{mikami,sugihara}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし

被災地における救援物資提供のための対象人数調査など, 個人情報を含むデータの集計が必要な場合がある. 従来は, プライバシーに関わる情報の特定を防ぐため, 属性単位等のアクセス範囲に対する集計値を返さないようにしたり乱数を付加して返したりする方法がとられていた. 本研究では, より細かいアクセス制御を行うために, RDF
によるグラフデータベースを想定し, グラフのノード単位で, 情報の持ち主の意向を取り入れた階層的なアクセスレベ
ル制御を行い, ユーザのクラスに応じた集約計算を行うことを目指す. プライバシーに関わる情報が特定できないように配慮しながら, それぞれのユーザクラスがアクセス可能なノード数の割合を利用し集計値を推定する. 被災情報に関する RDF ベンチマークを用いて, 集計値の精度の評価を行う.
キーワード

情報セキュリティ, プライバシー, RDF

1. は じ め に

実な集計値を提供するために, ユーザがアクセス可能な部分の集計値から全体の集計値を実用に堪える速度で推定する手法を

近年, 災害発生時や発生後の被災地における復旧活動におい提案する. 全てのデータにアクセス可能なアクセス権限をもつて情報技術を活用することが注目され, 安否確認を含む情報共

ユーザには全体の集計値と誤差のない集計値が提供されるが,有システムが利用されている. 実現されたシステムとしては, 利

アクセス権限が低くアクセス可能なデータが少ないユーザには用者の安否回答の状況を地図上に表示し, 家族や同僚, 友人同

アクセス不可能な部分の値を特定できないような全体の集計値

士でその情報を確認できるアプリケーションなどが挙げられる.

との誤差が大きい集計値が提供されることを示す. また, RDF

このようなシステムで利用するデータの中には, 個人のプライを利用した, 個々のデータに階層的なアクセスレベルを設定す

バシーに関係するものが含まれる可能性があるため, システム

ることが可能な暗号化データベース上で提案手法を実装し, 被の利用にあたっては不正利用を防止するためのアクセス制御や災地の避難者情報を再現したベンチマークを用いて性能を評価

データの暗号化が必要不可欠である. しかしながら, 必要があする.

ればそのデータを個人のプライバシーを侵害することがないよ
うに提供することも同時に必要である.

本論文は, 本章を含めて 6 章により構成される. 第 2 章では本論文に関して前提となる知識を述べる. 第 3 章では関連する

例えば, 被災者支援団体が救援物資の提供のために支援対象

既存研究を紹介する. 第 4 章では提案する手法について述べる.

である被災者の総数を知りたいという場合, 被災者の情報を保第 5 章で評価実験の方法を述べ, その結果を考察する. 最後に,存したデータベース上でユーザが指定した条件を満たす被災者

第 6 章で本論文のまとめと今後の課題を述べる.

数の集計計算を行いユーザに提供するシステムが必要になる.
このとき, 悪意を持つユーザがシステムに集計計算を要求し, 集

2. 前 提 知 識

計計算の検索条件と集計計算結果からプライバシーに関わる情2. 1 アクセス制御

報を特定する危険があるため, その危険に対処しなければならアクセス制御とは, ある情報資源に対し, 特別に認可された利ない.

用者のみがアクセスできるようにすることである [1]. アクセス

既存手法では集計計算結果からプライバシーにかかわる情報

制御ポリシーとは, どの利用者がどの情報資源にアクセスできを特定可能と考えられる場合に集計計算結果を返さないようにるようにするかを判断する基準である. システムは, ユーザにしたり, 雑音として乱数を加算したりするといった方法がとらよるアクセス要求があると, まず認証により登録されたユーザ

れていた. しかし, これらの手法は得られる集計計算結果が確であるかを確認し, 登録されたユーザであればそのユーザ情報

実でないことや, ユーザがアクセス可能なデータ数を考慮してを取得する. そして, システムはユーザの属性・ユーザがアクおらず, アクセス可能なデータ数の多いユーザがより正確な集

セスしようとしている情報資源の属性・ユーザが要求するアク計計算結果を得られるようにすることができないことなどの問セスの種類などの情報をアクセス制御ポリシーと照らし合わせ,

題点がある.

最終的にユーザのアクセス要求に対し認可を与えるかどうかのそこで本論文では, アクセス制御が行われた暗号化データベー判断を行う. このような仕組みにより, システムは情報資源に対スに対してユーザのアクセス可能なデータ数に応じた精度で確し管理者の意図しないアクセスが行われないことを保証できる.

ただし, 情報資源内の情報をその情報の所有者が意図しない

常の SQL と同様に SELECT 節, WHERE 節を持つ. SPARQL

アクセスから守るには, このようなアクセス制御だけでは不十クエリによるデータの検索は, WHERE 節に記述されるグラフ分である. 情報資源の管理者がシステムのアクセス制御設定をパターンとのマッチングにより行われる. 以下に SPARQL ク

不正に書き換え, 情報資源に許可なくアクセスする場合がある

エリの一例を示す.

からである. このような場合に備えて, 公開範囲を制限すべき

SELECT ?age WHERE

情報については暗号化による保護も必要である. 所有者や許可{された利用者のみが保持する鍵で個々のデータを暗号化するこ

ex:Alice age ?ageとにより, たとえ管理者が情報資源に許可なくアクセスして内}部のデータを取得しようとしても, それを利用するために復号

グラフパターンはトリプルパターンの集合であり, トリプルすることができないからである.

パターンの主語, 述語, 目的語部分には RDF グラフにおいてこのような暗号化による情報資源の保護技術の応用として,

それらになりうる要素に加えて, どの値にもマッチする変数をPopa らが提案した手法 [2] がある. この手法では, ユーザとデー置くことができる. 変数は頭文字に?をつけることで表現する.

タベースサーバの間に CryptDB と呼ばれるアプリケーション

また, 同じ変数が置かれた要素については同じ値であることをが設けられ, プロキシとして暗号や復号に関わる処理を行う.

示す. クエリ結果は WHERE 節にマッチするグラフパターン

CryptDB は, データを暗号化したまま演算が可能な暗号化手法の中で SELECT 節に書かれた変数にマッチした要素となる.

を利用し, それらの暗号化をデータに対して複数回行い, 最後にSELECT 節では変数そのものだけでなく COUNT などの集計

どの演算も不可能な暗号化をデータに施す. ユーザが検索要求計算を行った結果を取得するようにすることも可能である. 例を出すと, そのクエリで計算が必要になるデータベース内の属に示したクエリは ex:Alice に対応する人の年齢を取得するクエ性列の値を, 対応する演算が可能な暗号化を施された状態になリである. 図 1 のグラフに対してこのクエリを発行した場合,るまで復号してから処理を行う. CryptDB はこのような仕組

クエリ結果は {{?age =: 24 }} となる.

みを利用しているので, 検索時にデータベースの内容を全て復RDF でデータを記述すると, SPRAQL クエリなどを用いて号化する必要がないため, データベースの管理者が暗号化前の他の RDF で記述されたデータも対象にした検索や集計を行う

データを取得する危険を最小限に抑えることが可能である.

ことが可能である. この性質から, RDF は日本を含む世界にお2. 2 RDF

いて相互にリンクするオープンデータ (Linked Open Data [4])

情報共有においては情報への不正なアクセスの防止の他に,を実現する手段として普及し始めている. 特に日本においては情報をどのように表現し保存するかということも重要である.

東日本大震災以降避難所情報を RDF 形式で公開する自治体が

特に災害時は避難所情報を速やかに被災者へ提供することが出てきており [6], 災害時の情報共有に用いる情報の表現に RDF重要であり, そのためには自動処理プログラムにより二次利用を用いることが今後標準になっていくのではないかと考えられのための編集や加工などが可能な形式で避難所情報を表現する. したがって, 災害時の情報共有に関係している本研究におる必要がある. 政府はこのようなデータ形式での情報公開を

いて情報表現の手段として最も適していると考えられるため,行っており [3], これはオープンデータと呼ばれる. これを実本研究においては使用するデータを RDF で表現する.

現するデータ表現のモデルとして RDF(Resource Description

Framework) [4] が注目されている.
RDF は, 情報を 3 つの要素からなるトリプル単位で表現す

3. 関 連 研 究
3. 1 プロキシ再暗号化を用いた暗号化データ検索

る. トリプルはある事物を指す識別子である主語と, 他の事物

児玉らはデータやユーザの効率的な追加および削除を効率的の識別子あるいは主語の持つ属性値を表すリテラル値である目に行うために, データに対し論理的なクラスを単位とした暗号的語と, 主語と目的語の関係を示す有向辺である述語で構成さ化を行う手法を提案した [7]. この手法は, プロキシ再暗号化可RDF

れる. 例えば, Alice さんという人物に対し一意な識別子が与え能な暗号を利用することにより, アクセス制御の柔軟性を維持

られ, その省略形が ex:Alice と表現できたとする. Alice が 24

しながら, 従来の暗号化手法と比較して少ない計算量でデータ

歳であるという情報は図 1 に示すトリプルとして表現される.

やユーザの追加および削除を行うことを可能にしている. また,トリプルの集合も RDF グラフとよばれ, 同様に可視化できる.

2. 2 で説明したような理由から, データを表現する形式としては

age

RDF を用いている. この手法を用いて実装された暗号化デー

ex:Alice24	
図 1 RDF トリプル (ex:Alice, age, 24)

タ検索システムは, 暗号化されたデータを保存するデータベースと以下の要素を組み合せている.
アプリケーション ユーザが直接通信するアプリケーション
プロキシサーバ 暗号化されたデータが保存されたデータベー
スとアプリケーションの間にあり, データを再暗号化する能RDF グ ラ フ か ら デ ー タ を 検 索 す る た め の 言 語 と し て は
SPARQL が標準的に用いられている [5]. SPARQL クエリは通力をもつ
アクセス制御情報 ユーザがどのクラスに属するか・どのクラ

スがどのアクセスレベルに対応するかという情報と, アクセを施した結果を, 個別のデータの値が特定できないように公スレベル間の階層関係が保存される
秘密鍵生成局

出力プライバシー データ群に集計計算などのマイニング処理

アクセスレベルの公開鍵, ユーザの公開鍵・秘密鍵およびアクセスレベルからユーザへ再暗号化のために使開する（狭義の）PPDM 所有者の異なる複数のデータ群に対する計算結果を, 各所有者に対し他の所有者の所有するデータの用する鍵を提供する
これらの要素を組み合わせて暗号化データベースで検索を行う

値を特定できないないように計算し公開する

手順は以下のとおりである. また, 各要素間の連携を図 2 に示

入力プライバシーに関する技術としては, 個々のデータのもつした.

値が特定の範囲内であることまではわかるようにしながらも元（ 1 ） アプリケーションはユーザの認証を行うと, ユーザのクエリを受け付け, ユーザの id に紐づく公開鍵でクエリに含まれる RDF タームを暗号化し, ユーザの id とともにプロキの値がわからないようにする手法 (匿名化) や, 各データ内で個人を特定しうる属性を隠す手法 (抑圧) などが挙げられる. 出力
プライバシーに関する技術としては, 集計計算結果から個々のデータのもつ値を特定できないように集計計算結果を歪ませる

シサーバに送信する（ 2 ） プロキシサーバはユーザの id からユーザのクラスと対応付けられたアクセスレベル l を取得し, l およびそれ以下のアクセスレベルが設定されそのレベルで暗号化されたデー
タを検索可能なようにクエリの RDF タームを再暗号化し手法 (摂動法) や, 同一のユーザから類似した集計計算クエリが連続して送信された場合に集計計算結果を返さないようにする
手法 (クエリ監査) などが挙げられる. 摂動法としては雑音として乱数を加算する手法などがある.
摂動法により歪められた集計値の安全性を評価する基準としデータベースに送信する（ 3 ） プロキシサーバはデータベースにおける検索結果を受け取ると, 結果に含まれる暗号文をアクセスレベルからユーザの id に紐づくように再暗号化してアプリケーションに送て, Dwork は差分プライバシーという概念を提唱した [9]. これは, データベースを入力とし歪められた集計計算結果を出力とするメカニズムを f とし, あるデータベース D とその中にある
任意の個人のデータ t に対して, D から t のみを除外したデー

信する（ 4 ） ユーザはアプリケーションから結果を受け取ると, ユーザの秘密鍵で結果を復号化する

基盤システム[児玉ら 2015]

タベース D′ を考えたときに, f (D) と f (D ′ ) の区別がほとんどつかなければ f は安全であるとみなすものである. 差分プライ
バシーを満たすメカニズムとしては, 集計計算結果にラプラス
ε|x|

ε − ∆
分布 L( ∆
) = 2∆e(∆ = maxD,D′ |f (D) − f (D′ )|) にしε

ユーザの公開鍵pkid ,・復号鍵skid

ユーザ⇔レベル再暗号化鍵
rkid→l, rkl→id

クエリはユーザの公開鍵で暗号化

ユーザ

結果をユーザが復号可能なように再暗号化 プロキシサーバ

たがう乱数を加算するものなどが同氏らの研究により発見され
鍵生成局

クエリをレベルに紐づくように再暗号化
暗号化DB

id

保存：レベルの公開鍵で暗号化ている [10].
これらの動きに加えて, 近年ではデータの所有者によるプラ
イバシー意識の多様性に対応するため, PPDM の保護レベルをパラメータ化しユーザが調整できるようにする動き (Multilevel

Trust [11] の導入) も見られる. Yaping らは入力プライバシー

ユーザ情報

クラス

ユーザからクラスへの写像

レベル l

ユーザクラス情報
クラスからレベルへの写像
レベル間の階層関係

図 2 児玉らの手法の保護レベルをパラメータ化し, データから作成した分散共分
散行列とパラメータに比例する値の積で定義される分散をもつ
正規雑音を各データに加算する手法とともにこの概念を提唱した [11]. また, 出力プライバシーに関する研究としては, データ

3. 2 プライバシー保護データマイニングの所有者が指定した確率でデータの値を別の値に置き換えて個人の行動に関連した実社会情報を扱う広告モデルや SNS

サーバに送信し, サーバが値が特定のカテゴリに属すユーザ数などのオンラインサービスが登場している近年では, サービスを集計するという状況において, 所有者が指定した確率・ユーの提供者が個人のプライバシーに関わる情報を利用できないこ

ザ数・カテゴリ数などの値を利用して真の集計計算結果を推定とは経済的な機会損失につながるため, そのような情報の利用する手法が提案されている [12].

は必要不可欠となっているが, 利用に際しては所有者が望まな

本研究は出力プライバシーに深く関係している. 既存の摂動

い流出が起こることもある. プライバシー保護データマイニン

法は乱数が関わるため, 歪められた集計計算結果の正しい集計

グ (以下 PPDM) とは, 個人のプライバシーに関わる情報を含計算結果との誤差が膨大になる場合があるので, 集計計算結果

むデータ群から個人のプライバシーが流出しないように保護しの値が確実性に欠ける. クエリ監査ではシステムの規模が大きつつ有用な情報を抽出するための技術の総称である.

くなった場合に記録するログの量が膨大になるという問題点がPPDM に関する研究は大きく分けて次の 3 つに分類される [8].
入力プライバシー 1 つ 1 つのデータをある個人のものと特定できないように公開するある. また, 両者ともに, データベース内の同じ属性列に対して,ユーザがその中の一部にのみアクセス可能とするようなアクセス制御を考えた場合に, アクセス可能な属性列が多いユーザが少ないユーザよりも正確な集計計算結果を得られるようにする

ことができない. Multilevel Trust を導入した PPDM に関する既存研究においても, 先述のような集計計算結果を提供する
ためのパラメータ設定を個々のデータ所有者の意向とユーザの

SF =

s
m

(3)
∏

σJ = SFJ ×

|N |

(4)

N ∈{ 結合に関わる関係 }アクセス権限から求める手法が確立されていない. 本研究では個々のデータ所有者がデータに設定したアクセスレベルとユー

本研究では選択性推定の手法を, データベース上のデータに

ザのクラスに対応付けられたアクセスレベルの高低関係を考慮

対する集計結果をユーザのアクセス可能なデータから推定するした上で先述のような集計計算結果をユーザが得られるようにために使用する. 特に Hou らの手法に対し, ユーザがアクセスする. 災害時や災害後の復興にあたり被災者や自治体関係者, 被可能なデータのみを利用することを考える. こうすることによ

災者支援団体との情報共有を考える上でそれぞれのユーザに提り, アクセス権限が十分に高く全てのデータにアクセス可能な供する集計結果が出力プライバシーを守れるようにすることもユーザに対しては正しい選択率を推定できるが, アクセス権限

考えていく.

が限定され一部のデータにしかアクセスできないユーザに対しては誤差を含んだ選択率を推定することになると考えられる.

3. 3 データベースにおける選択性推定
データベースにおいて結合を含むクエリを実行する際には,

3. 4 避難場所情報に対する RDF データセットベンチマーク

実行速度や使用メモリの削減のために各結合演算の対象となる

Nguyen らは被災地の避難所場所の情報や, 避難所における作

タプルの数ができるだけ小さくなるような結合順序で結合を行業の関係者の情報を表現する RDF データを自動的に生成する

う必要がある. 選択性推定 (Selectivity estimation) とは, 結合

ベンチマークツール SIBM(Shelter Information Benchmark)

対象となるそれぞれの途中計算結果について, タプル数やデーを開発した [16].
既存の RDF によるベンチマークツールとしては LUBM [17]タサイズを推定することである [13].
データベースにおいてデータの検索を行う演算は選択 (SE-があるが, 生成されるデータは大学の学部ごとの学生や職員のLECT) であり, これは属性列の値が特定の値になっているタプ

個人情報や授業履修・担当情報であり, 学生同士の細かい個人

ルを取得するなどの処理である. 関係 R に対して選択演算 F

間関係を含んでいるわけではないため, 避難所における避難者を行った結果に含まれるタプル数の推定のためには, R に対し間の個人間関係を再現できず, 被災地における情報共有システて F がどの程度の割合でタプルを取得するかを推定する必要がムの評価には適さないという問題点があった.

あり, これを選択率 (selectivity factor) と呼ぶ [14]. R に対しそれに対し SIBM は避難所における避難者間の家族関係や,て F を行った結果を σF (R) とし, F に対する選択率を SF (F )LUBM よりも詳細な個人情報, また避難所における災害の発生とすると, σF (R) に含まれるタプル数は式 (1) のようにして求状況や物資の備蓄情報なども含んでいるため, LUBM よりも被められる [14].

災地における情報共有システムの評価に適していると考えられ|σF (R)| = SF (F ) × |R|(1)

る. それに加えて SIBM は, 生成する避難所情報は実際に存在し避難所として利用可能な施設の情報をもとにしていることや,結合を行う場合, 結合結果に含まれるタプル数が最も大きく生成する個人の情報は日本の人口構造情報をもとにしているこ

なるのは, お互いに含まれるタプル全てに対して結合が成り立とから, 現実と近いデータセットの作成が可能である. これら

ち結合結果が結合に関わる関係の直積集合となる場合である.

の理由から, 本研究ではこのベンチマークを利用して提案手法

この濃度に対してどれだけ結合が成立するかを選択率とすればの評価を行う. SIBM が生成するデータの詳細を図 3 に示す.

避難所全体の構成

式 (1) と同様に結合結果に含まれるタプル数を推定できる. 関
係 R と S の結合に対し, 選択率を SFJ とすれば, R ▷◁ S に含まれるタプル数は式 (2) のようにして推定できる [14].

|R ▷◁ S| = SFJ × |R||S|

年齢

氏名

(2)

避難所情報

避難者情報

メール

性別

電話番号

座標

住所

備蓄情報

行政区域コード

収容量

家族関係

選択率の求め方には, データベース全体の統計情報を利用する手法と, データベース内の一部のタプルを利用する手法など

病気・怪我の状態

避難者情報がある. データベース全体の統計情報を利用する手法では, 関
図3係に含まれるタプルにおける演算に利用する属性値の値域や最避難所情報

大値・最小値などから選択率を推定する [14].
データベース全体に対する統計情報ではなく, データベース
内の一部のタプルから選択率を推定する手法もある. Hou らはランダムに抽出したタプルの総数 m と, その中で選択演算の論
理式を満たすタプルの総数 s を用いて選択率を式 (3) のように論理式を満たすタプルの割合として求めた [15]. なお, このとベンチマークは, ユーザが指定した被災地と中心からの距離d(d > 0) を引数とするプログラムが作成する. ユーザが指定した被災地の中心地を中心とし, 半径 dkm 以内に存在する避難所とその避難所に避難している人の情報が生成される.

4. 提 案 手 法

き複数の関係を含む結合演算結果に含まれるタプル数 σJ は式(2) と同様に考えると式 (4) のようにして求められる [15].

アクセス制御が行われた RDF データベース内で, ユーザの

ALLG,u = SFG,u TG

アクセス可能なデータ数に対応した集計計算結果を推定する手法を説明する. 本研究では集計計算の中でも COUNT(条件を満たす結果の総数) 計算の結果の推定を行う. 以下では, RDF
データベースに含まれるトリプル全体の集合を R とする.

具体的な例として, RDF データベース R に対する以下のクエリの集計計算結果の推定を考える.

SELECT (COUNT(*) AS

SPARQL クエリの結合パターンとしては主語-主語が圧倒

SPARQL クエリの WHERE 節は述語に変数でない値が, 主語に変数がそれぞれ指定されているトリプルパターンの集合に一般化できる. 以降ではこれを踏まえ, クエリのトリプルパター
ンはこの構成であると仮定する.

?CNT) WHERE{?p stayAt <shelter1>

的に多く, 主語-目的語が後を追い, それ以外の組み合わせは 2者に比べて非常に少ない [18] ことを利用すると, ほとんどの(9)?p state<flu>}
stayAt は主語が目的語である避難所に避難していることを表し,state は主語が目的語である病気に罹っていることを表す. これは避難所 shelter1 に避難しており, インフルエンザに罹っている人の総数を取得するクエリである. このクエリの WHERE 節

SPARQL クエリの WHERE 節を G とすると, G はトリプ内のグラフパターンを P とする. あるユーザ u1 が, このクエ

ルパターンの集合である. G にマッチするグラフパターンは R

リを児玉らのシステムに対し発行して, {{?CNT=10}} という内のトリプルの結合により得られるので, その最大数を Hou ら∏による選択性推定手法の式 (4) の |N | に対応させることがで結果が得られたとする. このとき SAP,u1 = 10 である. P にきる. さらに (4) の選択率 SFJ は式 (3) の SF のように推定できることを利用する. ユーザ u がクエリを発行したとき, 児玉らの RDF データベースシステムは, G にマッチするグラフパ
ターンのうち全ての要素に u の所属するクラスからアクセス可能なグラフパターンのみに対する検索結果を返す. これを利用するとユーザがアクセス可能なデータのみに対する COUNT 計

含まれるトリプルパターンは (?p, stayAt, <shelter1>) と (?pstate <flu>) であるので, TP は u1 がアクセス不可能なトリプ
ルも含めた R 全体で述語が stayAt であるトリプルの総数と述語が state であるトリプルの総数の積になる. 同様に考えるとT AP,u1 は u1 がアクセス可能で述語が stayAt であるトリプルの総数と述語が state であるトリプルの総数の積になる. このとき R に対し次の 2 つのクエリが発行される.

算結果と, G に含まれる各トリプルパターンと述語部分がマッ

SELECT (COUNT(*) AS ?CNT1) WHERE

チする R 内のトリプルの中でユーザがアクセス可能なトリプ{?p stayAt <shelter1>}

ルの総数を取得できる. G にマッチするグラフパターンは R 内

SELECT (COUNT(*) AS ?CNT2) WHERE{?p state <flu>}のトリプルの結合により得られるので, 式 (3) の s を前者に, まR 全 体 に 対 す る 集 計 結 果 が そ れ ぞ れ {{?CNT1=3000}},

たユーザがアクセス可能なトリプルパターンの結合により得ら{{?CNT2=1500}} な ら ば, TP = 3000 × 1500 = 4500000

れるグラフパターン数は多くともユーザがアクセス可能で述語

で あ る.

同 様 に, ユ ー ザ u1 が ア ク セ ス 可 能 な ト リ プ ル の部分がマッチするトリプルパターンの直積集合の濃度なので m

みに限定した場合の集計結果がそれぞれ {{?CNT1=2000}},を後者の総積に対応させることができる.

{{?CNT2=500}} ならば, T AP,u1 = 2000 × 500 = 1000000 で以上の過程を経てユーザ u が発行したクエリのグラフパター
ン G にマッチするグラフパターンの総数の推定値 ALLG,u をある. 結果として ALLP,u1 = 10 × 4500000= 45 となる.
1000000
なお, ここで発行する COUNT クエリの計算は, 児玉らのシ推定するにあたって, Hou らの手法と対応させた部分の詳細な∏計算式を以下に示す. 式 (4) の |N | に対応する値を TG , 式

データベース内でデータを暗号化したま行っている. クライア

(3) の s に対応する値を SAG,u , m に対応する値を T AG,u とす

ント側で値を復号して検索条件と比較し集計するよりも高速にる. (4) の SFJ に対応する値を SFG,u とする. 以下では, ユー

集計が行えると考えられるからである.

ステムに機能を追加して SPARQL の COUNT 関数を用いて

ザ u がアクセス可能なアクセスレベルの集合を Lu とし, RDF

ここで推定した COUNT 計算結果は, ユーザがアクセス不可要素 e に設定されたアクセスレベルを le と表現する. また, G

能な RDF 要素の値に関する情報を使用していないため, ユーに含まれるトリプルパターンの数を |G| とする.

∏

TG =

|{(s, p, o) ∈ R|p = pG }|ザに提供してもユーザがアクセス不可能な情報を露出したこと(5)

タベースの内容とユーザのクラスが同じであれば常に同じであ(sG ,pG ,oG )∈G

る. さらに, ユーザがアクセス可能なアクセスレベルが増え, そT AG,u =∏|{(s, p, o) ∈ R|ls , lp , lo ∈ Lu ∧ p = pG }|(6)に近づくので, 推定結果の誤差が小さくなる.

5. 実

SAG,u =|G|

SFG,u =

れに伴ってアクセス可能な RDF 要素が増加するにつれて, Gにマッチするグラフパターンの選択率 (= SFG,u ) が真の割合(sG ,pG ,oG )∈G|{g ∈ Rにはならない. 乱数を使用していないため, 得られる値はデー験|g が G にマッチ ∧ ∀(s, p, o) ∈ g ls , lp , lo ∈ Lu }|提案手法と, 差分プライバシーを満たすラプラス乱数の加算(7)による出力プライバシー保護技術の性能を比較する. 両者とも

SAG,u
T AG,u(8)に児玉ら [7] の提案した手法を利用した RDF データベースシ

表1

ステム上での評価を行った. また, 実行時間について, 児玉らのデータセットの詳細システムに機能を追加しデータベース内で集計する場合にかかる時間と, クエリ結果に含まれるリテラル値をクライアント側
で復号し検索条件を満たすか確認してカウントして集計結果を

d 避難所総数 避難者総数 トリプル数 (暗号化前) 真の集計結果
2.0

15

3289

49994

236

3.0

24

7514

114093509

求めた場合にかかる時間を比較した. また, RDF データベース

4.0

37

10674

162022

748の作成, 検索にあたっては Java で開発された Jena [19] という

4.5

54

14712

223494986

ライブラリを使用した.

4.7

61

17724

269262

1205

5.1

73

21621

3275921443

5. 1 環境とデータセット・アクセス制御ポリシー¤£1­²¢¸:¤£´¬³&3q¹VOº
つのアクセスレベルを想定し, 図 4 のように設定した.

実験には, 以下の環境を用いた.

CPU Intel Xeon E5620
RAM DDR3 SDRAM 24GB

Medical:Person

Very:HighOS Ubuntu 11.10 64bit
Public:Oﬃcer

Java 1.7.0 51
Jena 2.13.0

High
Middle

実験にあたり, 個人のプライバシーにかかわる情報を含んだデー

Volunteer|vacueeLow

タセットとして, SIBM [16] を利用した. 被災地は福島県とし,Very:Low

中心からの距離を 2.0, 3.0, 4.0, 4.5, 4.7, 5.1km と変更しなが
ら 6 種類のデータセットを生成した.

Press

図 4 アクセスレベルとユーザクラスの対応関係

実験で発行したクエリは以下の通りである.

PREFIX sibm: <http://lab.ene.im/Sibm/property#>
SELECT (COUNT(*) AS ?CNT)

また, SIBM に含まれる述語へのアクセスレベルの設定は, 所有者の意向が多様であることを想定し, 所有者により異なるア

WHERE{

クセスレベルを設定できるようにした. 各述語に対し, 各アク?psibm:isOld

true

?p

sibm:stayAt?shelter

セスレベルに設定される確率を決めておき, 乱数を利用してその確率でアクセスレベルが設定されるようにした. 今回の実験
アクセス制御ポリシー?shelter sibm:administrativeAreaCode 7203 アクセス制御ポリシーで実行したクエリ内の述語に対するアクセスレベル設定確率のアクセスレベル確率分布(省略版)
分布は図 5 と図 6 に示してある.

}

アクセスレベル確率分布(省

このクエリ内で, 述語 stayAt は主語である人が目的語である避stayAt1
難所に避難していることを表し, 述語 administrativeAreaCode
0.9

設 0.8
は目的語が主語である避難所の行政区域コードであることを示
定 0.7
さ 0.6
れ 0.5
す. また, 述語 isOld は生成したデータセットに対し実験用に追
る 0.4
0.3
確 0.2
加したものであり, 目的語の値 (true or 率false)
が主語である人
0.1
0の年齢が 60 以上か否かに対応することを示す. 児玉らの手法

isOld

1
0.9

1
0.9

設 0.8
定 0.7
さ 0.6
れ 0.5
る 0.4
0.3
確 0.2
率 0.1

設 0.8
定 0.7
さ 0.6
れ 0.5
る 0.4
0.3
確 0.2
率 0.1

0

0

0

アクセスレベル

アクセスレベルでは数値データの大小比較ができないので, 大小比較でなく等価か否かの比較だけで集計計算が行えるようにするために追加

stayAt

1
0.9

設 0.8
定 0.7
さ 0.6
れ 0.5
る 0.4
0.3
確 0.2
率 0.1

図 5 設定確率分布

アクセスレベル

図 6 設定確率分布

した. このクエリは行政区域コード 7203(福島県郡山市) の避難所に避難している 60 歳以上の人の総数を取得するクエリであなお, administrativeAreaCode などの避難所情報は個人情る. このクエリに含まれるリテラル値は true と 7203 であるの報でないため, アクセスレベルは Very Low よりも低いアクセ

で, クライアント側で復号する手法ではそれらを変数に置き換

スレベルを設定しており, どのユーザからでもアクセス可能にえてそれらの値を取得するクエリを発行し, それらの変数の値なっている.

が true および 7203 であるようなグラフパターンの総数をカウントする.

暗号方式としては, 児玉らの実験と同様に Blaze らの BBS ア
ルゴリズム [20] を使用した. 比較対象で使用したラプラス乱数

なお, 今回生成した 6 種類のデータセットの詳細と発行する

1
L(λ) のパラメータ λ = ∆は 0.1に設定した. COUNT 計算に
ε

クエリに対する真の集計結果は表 1 のとおりである. クエリ

対して差分プライバシーを満たすラプラス雑音の ∆ は 1 になの発行元ユーザは, Press(報道関係者), Volunteer(ボランティ

ることが知られている [21] ためである.

ア), Evacuee(避難者), Public Oﬃcer(自治体関係者), Medical

5. 2 集計計算結果の相対誤差

Person(医療関係者) の 5 種類とし, それぞれについて検索を提案手法で推定した集計計算結果と, 真の集計計算結果 (アク行った. なお, クライアント側でリテラルを復号する場合の検索

セスレベルを無視した集計計算結果) にラプラス雑音を加算し時間の計測については Volunteer ユーザのみで行った. 実験にた値のそれぞれについて, 真の集計計算結果との相対誤差を算出おけるアクセスレベルと前述のユーザクラスとの対応関係は, 5

し, 暗号化前のトリプル数を横軸とするグラフにまとめたのが

is

アクセ

図 7 である. 凡例は noisy は真の集計結果にラプラス雑音を加ると考えられる. また, 相対誤差の差はデータセットの規模が算した値の平均値 (試行回数は 10 回) の相対誤差を示し, noisy

大きくなるにつれて小さくなる傾向があることもわかった.

以外はクエリ発行元のユーザクラスを示す. noisy については信

5. 3 集計計算の実行時間

頼区間も求め, その範囲もグラフ内に示した. 信頼度は 95%と( )2
( 1 )2し, 分散はラプラス乱数の分散 2 × ∆= 2 × 0.1
= 200ε

提案手法は検索対象のデータに含まれるリテラル値を暗号化されたままデータベース内で検索を行っている. そのため検索を用いた. 図 7 のグラフより, 提案手法で推定した集計計算結結果からリテラル値を復号して検索条件に指定した値と等しい

実行結果グラフ(相対誤差)

かどうか確認するよりも高速に集計計算を実行できるのではな
トリプル数-相対誤差

いかと考えられる. このことを確かめるため, 集計計算結果の0.3

相対誤差のほかに集計計算の実行時間も計測した.

0.25

medical_person
0.2

public_officer

相
対
誤
差

0.15

evacuee
0.1

100000150000200000250000300000350000

図 9 のグラフにまとめた. 図 9 のグラフより, 実行時間の差はデータセットが増加するにつれ大きくなっていることがわかる.

noisy

また, 性能比は最大で 14 倍になった. データベース内で暗号化

-0.05
-0.1

イアント側で復号して集計を行った場合の実行時間を比較し,

press
0
50000

ス内で集計計算を行った場合の実行時間と, リテラル値をクラvolunteer
0.05

0Volunteer に属するユーザからのクエリについて, データベーしたまま検索を行うことにより, 値をクライアント側で復号しトリプル数(暗号化前)

図 7 ユーザクラスごとの相対誤差比較て確認するよりも集計計算がより高速に行えることがわかった.
しかしながら, 実用化を目指すにあたってはさらなる高速化が必要であることも考えられる. 今回使用したデータセットの果は, データセットの規模が大きくなるにつれて, 真の集計計算中で最も規模の大きい d = 5.1 のデータセットに対しては集計

結果との相対誤差が小さくなる傾向があることがわかる.

計算に 2 時間以上もの時間を要している.

ユーザクラスごとに考えると, isOld と stayAt の両方につい6. お わ り にて全てにアクセス可能な Medical Person および Public Oﬃcer
は誤差のない集計計算結果を得ることができ, isOld へアクセ

6. 1 ま と め

ス可能な割合が 2 割だけ減少した Evacuee は noisy の信頼区間

階層的なアクセス制御を行ったデータベース上で, ユーザがの最大値よりも小さい相対誤差で集計計算結果を得られた一方

アクセス可能なデータのみに対する集計計算結果と個人情報ので, 両者ともに約半分までしかアクセスできない Volunteer は値と無関係なデータベース内の統計情報からユーザがアクセス実行結果グラフ(クエリごと)

noisy の信頼区間の最大値と同程度か 2∼3 倍の相対誤差がある
集計計算結果しか得られず, さらに両者へのアクセス可能な割

クエリごとの相対誤差比較

0.12

合が減少した Press が得た集計計算結果に至っては, noisy の信
0.1

頼区間の最大値と比較しても最大で約 7 倍の相対誤差があった.

トリプルパターン数:3(福島県郡山市の高齢者)

0.08

さらに, 図 7 で noisy の相対誤差の平均値と信頼区間を観察すると, ラプラス雑音が加算された集計計算結果は相対誤差が

相
対
誤
差

0.06
0.04

トリプルパターン数:1(全ての高齢者)

ほぼ 0 から 1 割に及ぶこともあるので, 実用に際し得られた集0.02

計計算結果の確実性が低いことによる問題が発生することが考0えられる. 一方, 提案手法で得られた集計計算結果はデータセッ
トとアクセス制御と問い合わせ元ユーザのクラスが同じであれ
ば常に同じ結果が返ってくるため, 確実性は高いと考えられる.

0

100000200000

考えられる. データセットの規模との関係も含めて観察するた

1.2E+14

め, Volunteer が属するユーザからのクエリについて, 5. 1 で紹

1E+14

検
索
時
間

クライアント側で
復号

6E+13
4E+13

とめたものである. 図 8 のグラフより, 推定した集計計算結果

2E+13と大きくなる傾向があることがわかる. これはユーザクラスにDB内で集計8E+13

結果を推定し, 相対誤差を計測した. 図 8 は, それをグラフにまの相対誤差は, クエリに含まれるトリプルパターン数が大きい

トリプル数-検索時間

1.4E+14を利用しているため, クエリによって相対誤差が変わることがであるトリプルパターンのみにしたクエリに対しても集計計算

400000

実行結果グラフ(検索実行時間)2
図 8 クエリごとの相対誤差比較

提案手法はクエリが含むトリプルパターンに関係する統計値

介したクエリの他に, 含まれるトリプルパターンを述語が isOld

300000

トリプル数(暗号化前)

0

0

50000

100000150000200000250000300000

データセットが含むトリプル数(暗号化前)与えられたアクセス権限と無関係に集計計算結果の精度が低下することを示す. 提案手法にはこの点において改善の余地があ

図9

集計計算の実行時間

350000できないデータも含めたデータ全体に対する集計計算結果を推定する方法を提案した.
被災地の避難所情報を再現したデータセット上で階層的なアクセス制御を行い, 提案手法の評価を行った結果, 提案手法で[3]推定した集計計算結果の相対誤差は, ユーザのアクセス権限が高く全てのデータにアクセス可能なときは 0 であり, アクセス

[4]

可能なデータ数が 8 割以上であれば差分プライバシーを考慮した処理を施した集計計算結果の信頼区間の最大値よりも小さい[5]が, ユーザのアクセス権限が低くなりアクセス可能なデータ数が減少するにつれて差分プライバシーを考慮した処理を施した
集計計算結果の信頼区間の最大値より大きくなる傾向が見られ[6]た. クエリに含まれるトリプル数が増加すると集計計算結果の相対誤差が大きくなる傾向も見られた. また, リテラル値を暗[7]号化したままデータベース内で集計計算を行う場合とクライアント側でリテラル値を復号して集計を行う場合の実行時間を比[8]較すると, データベース内で集計する方が最大で 14 倍高速に集計計算を行えることがわかった. 実行時間は実用化にあたりさ[9]らなる削減が必要である.

6. 2 今後の課題
まず, クエリに含まれるトリプルパターン数が増加するとユー[10]

ザのアクセス権限と無関係に集計計算結果の相対誤差が大きくなる傾向がある点について改善が必要である. 提案手法はトリプルの結合結果に含まれるグラフパターン数がトリプルの直積[11]

集合と等しくなる場合をグラフパターン数の上限としており,結合が成立する確率が 100%でない場合を反映できていないことが原因であると考えられる. 式 (5) の TG や式 (6) の T AG,u[12]を求める際に, 結合が成立する確率を考慮してトリプル数を掛け合わせることで, 相対誤差の増加抑制を図れるのではないかと考えられる.
次に, データセットによる相対誤差の違いについて, 今回使

[13]
[14]

用したデータセットとは異なるデータセットを使用した実験による観察が必要である. 同じ SIBM を使用するとしても, 被災[15]

地を変更すると異なる避難所の情報が生成されるので, その違
いが相対誤差に与える影響について考察する必要がある. また,

SIBM と構成そのものが異なっているデータセットを使用した[16]場合の相対誤差がどうなるかについても実験の後考察が必要である.
最後に, 本研究で推定の対象にした集計計算は COUNT のみ[17]であるが, 集計計算としては SUM(総和), AVERAGE(平均) なども存在する. これらの集計計算にも対象にする必要がある.
特に SUM 計算結果の推定は準同型暗号を使用することで値を[18]暗号化したまま安全に行えるのではないかと考えられる.

謝

辞

[19]

本研究の一部は, 日本学術振興会科学研究費補助金基盤研究[20](A)(#25240014) の助成により行われた. ここに謝意を表す.

文

献[1] Glossary of computer security terms (ncsc-tg-04), 1988.
[2] Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zel-

[21]

dovich, and Hari Balakrishnan. Cryptdb: Protecting confidentiality with encrypted query processing. In Proceedingsof the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP ’11, pp. 85–100. ACM, 2011.
総務省情報流通行政局情報流通振興課. オープンデータ戦略の推進. Retrieved January 8, 2016, from: http://www.soumu.
go.jp/menu_seisaku/ictseisaku/ictriyou/opendata/.
David Wood, Marsha Zaidman, Luke Ruth, and Michael
Hausenblas. Linked Data. Manning Publications Co., 1stedition, 2014.
Florian Haag, Steﬀen Lohmann, and Thomas Ertl. Sparqlfilterflow: Sparql query composition for everyone. In The
Semantic Web: ESWC 2014 Satellite Events, pp. 362–367.
Springer, 2014.
［オープンデータ＋ QGIS］ 統計・防災・環境情報がひと目でわかる地図の作り方. 株式会社技術評論社, 2014.
児玉快, 横田治夫. データやユーザの効率的な追加・削除が可能
な秘匿情報アクセス手法. 第 7 回データ工学と情報マネジメン
トに関するフォーラム, 2015.
佐久間淳. プライバシー保護データマイニング (私のブックマー
ク). 人工知能学会誌, 第 26 巻, pp. 533–536. 社団法人人工知能学会, 2011.
Cynthia Dwork. Diﬀerential privacy. In Automata, Languages and Programming, Vol. 4052 of Lecture Notes in
Computer Science, pp. 1–12. Springer Berlin Heidelberg,
2006.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam
Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of
Cryptography, TCC’06, pp. 265–284. Springer-Verlag, 2006.
Yaping Li, Minghua Chen, Qiwei Li, and Wei Zhang. Enabling multilevel trust in privacy preserving data mining.
Knowledge and Data Engineering, IEEE Transactions on,
Vol. 24, No. 9, pp. 1598–1612, 2012.
清雄一, 大須賀昭彦. Randomized response を用いた柔軟な匿
名データ収集. 電子情報通信学会論文誌 D, Vol. 97, No. 5, pp.
953–963, 2014.
Evaggelia Pitoura. Selectivity estimation. In Encyclopediaof Database Systems, p. 2548. Springer US, 2009.
M. Tamer Özsu and Patrick Valduriez. Principles of Distributed Database Systems. Computer science. Springer, 3
edition, 2011.
Wen-Chi Hou, Gultekin Ozsoyoglu, and Baldeo K. Taneja.
Statistical estimators for relational algebra expressions.
In Proceedings of the Seventh ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems,
PODS ’88, pp. 276–287. ACM, 1988.
Nguyen Hoai Nam, 荒堀喜貴, 横田治夫. SIBM: 避難場所情報に対する RDF データセットベンチマークツール. 第 7 回デー
タ工学と情報マネジメントに関するフォーラム, 2015.
Yuanbo Guo, Zhengxiang Pan, and Jeﬀ Heflin. Lubm: A
benchmark for owl knowledge base systems. Web Semantics: Science, Services and Agents on the World Wide Web,
Vol. 3, No. 2–3, pp. 158–182, 2005.
Mario Arias Gallego, Javier D Fernández, Miguel A
Martı́nez-Prieto, and Pablo de la Fuente. An empirical study of real-world sparql queries.
CoRR, Vol.
abs/1103.5043, , 2011.
Apache jena – home. Retrieved January 8, 2016, from:http://jena.apache.org/.
Matt Blaze, Gerrit Bleumer, and Martin Strauss. Divertible protocols and atomic proxy cryptography. In Advancesin Cryptology—EUROCRYPT’98, pp. 127–144. Springer,
1998.
寺田雅之, 竹内大二朗, 齊藤克哉, 本郷節之. 差分プライバシー基準に基づく情報秘匿手法の一考察. マルチメディア、分散協調とモバイルシンポジウム 2014 論文集, pp. 224–233, 2014.