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

MapReduceによる大規模なRDFデータ復号化手法の評価

Title(English)
著者(和文)Vu Tuan Dat, 横田 治夫

Authors(English)

Tuan Dat Vu, Haruo Yokota

出典(和文)

第7回データ工学と情報マネジメントに関するフォーラム論文集, , ,Citation(English), , ,発行日 / Pub. date2015, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2015 E5-5

MapReduce による大規模な RDF データ復号化手法の評価
VuTuanDat†

横田

治夫†

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

近年，様々な情報が RDF で記述されることが増えている．RDF データが急激に増加する中，秘匿性のあるデータを保護するため，暗号化が求められる．しかし，RDF データを解析する場合，暗号化したままで処理できることは限られており，復号化してから処理を行わなければならない場合がある．大量データに対する復号化には時間がかかり，並列処理による高速化が望まれる．本研究は MapReduce を用いた大量な RDF データ復号化の並列化アルゴリズムを提案する．RDF は Subject，Predicate，Object の三つ組によって構成される．提案手法では同じ

Subject，Predicate，Object をグループ化して，復号化をすることで実行時間の短縮を試みる．MapReduce を実行するとき 1 Job(MapReduce の実行単位) で全要素を復号化すると各トリプル要素が異なるタスクに割り当てる場合があり，トリプル再構築する必要がある．本研究は，再構築する必要がなく，Subject，Predicate，Object それぞれの要
素を各 MapReduce Job で復号化をしてトリプルに代入する手法と Subject，Predicate，Object の三つを 1 Job で全要素を復号化してから再構築を行う手法を提案する．さらに，Hadoop 上でプロトタイプを実装し，提案手法の処理効率を評価する．
キーワード

RDF，RDF 復号化，MapReduce

1. は じ め に

暗号化を前提とした場合，単純に平均年齢を求めるような場
合には準同型暗号 (2. 2. 2 節に参照) を使うことで，復号化せず

Resource Discription Framework(RDF) は，ウェブ上にあるに算出できる場合がある．しかし，上述したような複雑な条件「リソース」を記述するための統一された枠組みであり，Worldの場合には全体を一旦復号化して処理することも必要になる．

Wide Web Consortium(W3C) により 1999 年 2 月に規格化さ複雑な条件ばかりでなく，単純な平均年齢を求めるような場合れている．RDF は意味を損なわずにアプリケーション間で情も想定して準同型暗号を使う場合には特に全体の復号化に時間報を交換することができる．共通の枠組みであるため，アプリがかかる．利用状況として，広域災害等を想定した場合には特ケーションの設計者は共通の RDF パーサや処理ツールを有効に対象データが増えることが予想されることから，膨大なデー利用できる．そのため，近年様々な情報が RDF で記述される．

タに対して処理時間がかかる．そのため，並列化による高速化

RDF データが急激に増加する中，個人情報のような秘匿性が求められる．本研究では，復号化に時間を要する暗号を用いが求められるデータも増えている．秘匿性を保証するためには，

た場合に，全体を復号する場合の処理の高速化を対象として，情報を暗号化するアプローチや，匿名化を行いノイズ情報を加並列処理による高速化の方法を検討する．

えるアプローチなどが考えられる．統計情報を集約する場合等

並列分散プログラミング環境として，MPI(Message Passingにも，匿名化のアプローチは有用であるが，多様な集約処理をInterface) ライブラリ [3] がよく使われているが，プログラムが前提にしたノイズ情報への制約や，個々の情報が扱いたい場合大規模になるに従い複雑化し，エラー処理や障害処理などを記等の要求を満たすためには，暗号化が有用である．

述する実装コストが高いことが知られている．一方で，並列プ

例えば，災害対応等を考えたとき，そのような秘匿性が求め

ログラミングに慣れていない開発者でも扱いやすい分散処理フられるデータの中から集約処理を行う必要がある．想定される

レームワーク MapReduce [2] が注目されている．MapReduce

集約処理としては，単に避難所毎の人数を数えるようなレベル

では，map 関数と reduce 関数を定義するだけで，データをグのものから，ある年齢以上の高齢者の人数や，平均年齢，薬をループ化することによって大規模なデータの並列処理が可能と処方するために血圧がある値より高い人の人数，必要な食糧をなるシンプルなフレームワークである．また，計算機の故障や算出するために成人男性を１とした場合に女性は 0.8，高齢者

追加にも対応できる．特に，本研究のように，同じようなデーは 0.6，12 歳以下の子供は 0.5 といった比率で算出する値等，タの出現が多いことを想定し，同じデータをまとめてから処理

様々な場合が考えられる．また，行政機関や医療従事者などが，を行うには MapReduce が向いている．

個々の避難者の情報を利用することも想定すると，ノイズ情報

このような背景から，本研究では，MapReduce を用い，暗付加ではなく，暗号化が有用となる．本研究では，暗号化され号化されたデータに対し，平均年齢のような準同型性が利用でたデータに対して，様々な集約処理を行うことを対象とする．

きる単純な演算の並列化だけでなく，複雑な条件で全体を一旦復号化して処理する場合の復号化の並列化を行う目的とする．

主語・述語・目的語の順にスペースで区切って表記するフォー

全体を一旦復号化する必要がある場合の復号化について，前提

マットである．本研究で使用する RDF データのフォーマット

として復号化に時間がかかることから，本研究では，同じ暗号文

は n-triples である．図 1 の RDF グラフは N-Triples で表示すをグループ化することによって効率化を行う方法をいくつか提案

ると以下のようになる．

する．RDF が Subject，Predicate，Object の三つ組みによって構成され，MapReduce を実行するとき 1 Job(MapReduceの実行単位) で全部復号化すると各トリプル要素が異なるタスクに割り当てる場合があり，トリプル再構築する必要がある．本
研究は，再構築する必要がなく，Subject，Predicate，Object

Person1 name Yamada .
Person1 age 30 .
Person2 name Sato .
Person2 age 30 .

それぞれの要素を各 MapReduce ジョブで復号化をしてトリプ

2. 2 暗ルに代入する手法（Element Job 法）と Subject，Predicate，

2. 2. 1 確率的暗号と確定的暗号

Object の三つを 1 Job で復号化してから再構築を行う手法

暗号化するに大きく分けると２つのタイプがあり，確率的（Triple Reconstruction 法）を提案する．

号

暗号 (probabilistic encryption) と確定的暗号 (deterministic

また，準同型性が利用できる単純な演算の場合，例えば災害

encryption) である．確率的暗号は，平文 m に対する暗号文が対応等を考えたとき，避難者の平均年齢を求める場合，人の情

複数存在し，同じ平文でも異なる暗号文に暗号化される．この報 (避難者かボランティアか等，年齢の情報) をグループ化し，ため、確率的暗号では，暗号文同士の比較による同等性チェッ

避難者かどうかを判定してから準同型性を利用して平均年齢をクすることができない．逆に，同じ平文は同じ暗号になる暗号計算する．また，準同型性を利用しない通常の手法を比較しては確定的暗号と呼ぶ．確定的暗号は確率的暗号より若干弱いが，評価を行う．

暗号化したままでもとの平文の同等性チェックすることができ，

本稿の構成は以下の通りである．まず，2. 節で前提知識とし同等フィルター，GROUP BY，COUNT，DISTINCT などのて RDF，暗号の種類と MapReduce を説明し，3. 節で MapRe-

SELECT 演算が可能となる [7]．本研究は確定的暗号で暗号化

duce を用いた並列化手法を提案する．次に 4. 節で実験を通じされたデータを対象する．

て，提案手法の評価を行う．5. 節で関連研究について述べ，最2. 2. 2 準同型暗号

後に 6. 節でまとめを述べる．

暗号文同士を演算することで，異なる暗号構えの平文に対応する暗号文が計算できる暗号方式は準同型暗号と呼ぶ．平2. 前 提 知 識

文 m1 ，m2 を暗号化した二つの暗号文 c1 ，c2 (c1 = Enc(m1 )2. 1 RDF，c2 = Enc(m2 )) とする．Enc が演算子 ⊗ と ⊙ に対して準同

Resource Description Framework(RDF) は，資源に対する構型性を持つとは，c1 ⊗ c2 = Enc(m1 ⊙ m2 ) をみたすことを造的なメタデータを記述するための基礎的な枠組である．RDF

いう．

のメタデータのモデルでは，主語 (subject:S)，述語 (predi-

例えば，RSA 暗号 [5] は暗号化したまま平文の乗算を行える

cate:P)，目的語 (object:O) の 3 つの要素でリソースに関する準同型性をもつ．RSA 暗号では c1 × c2 = Enc(m1 × m2 ) とな

関係情報を表現し，これをトリプル（triple）と呼ぶ．主語はる．また，Paillier 暗号 [6] は暗号化したまま平文の加算を行え

記述対象のリソースである．述語は主語の特徴や主語と目的語る準同型性をもつ．Paillier 暗号では c1 × c2 = Enc(m1 + m2 )との関係を示す．目的語は主語との関係のある物や述語の値でとなる．本研究は，準同型性を利用し，平均値を求めることをある．トリプルの集合は subject と object を頂点とし，述語提案している。

が有向辺に対応したラベル付き有向グラフの構造を表現する．

2. 3 Hadoop と MapReduce

RDF データが構成するラベル付き有向グラフを RDF グラフとHadoop [1] とは大規模なデータを複数のコンピューターで呼ぶ．図 1 は単純な RDF グラフの例である．RDF のモデルを分散処理できるようにしたオープンソースソフトウェアである．Hadoop は分散ファイルシステム Hadoop Distributed FileƉĞƌƐŽŶϭzĂŵĂĚĂ

System（HDFS），分散処理フレームワーク MapReduce という大きく二つのコンポーネントで構成される．

ϯϬ

MapReduce のデータは非常にシンプルで key と value の組
み合わせで管理する．MapReduce の処理は map 処理，shuﬄeƉĞƌƐŽŶϮ^ĂƚŽ
図 1 RDF グラフの例

記述する方法は，グラフ，XML 構文などがあるが，扱いやす
く，並列フレームワークで扱いやすい記法として N-Triples がよく使われている．N-Triples は 1 行ごとに 1 つのトリプルを，& sort 処理と reduce 処理の 3 段階に分けて実行される仕組みになっている．このうち，ユーザーが外部から処理内容を与えるのが map と reduce である．
それぞれのフェーズでは，「〈key ，value〉ペア」または「〈key ，value のリスト〉ペア」を入出力として扱っている．MapReduce 処理の流れは図 2 を示し，以降では，各フェーズの詳細を述べる．Map フェーズでは，入力データは細かいブロックに分RDF は Subject，Predicate，Object の三つ組みによって構成
ศ๭㸯



ศ๭㸰

0DS
5HGXFH



ධຊ
ࢹ࣮ࢱ


され，MapReduce を実行するとき 1 job(MapReduce の実行単

Shuffle&Sort

位) で全要素を復号化すると各トリプル要素が異なるタスクに
ฟຊ㸯

ศ๭㸲

0DS

れぞれの要素を各 MapReduce ジョブで復号化をしてトリプルに代入する Element Job 法（手法 1）と Subject，Predicate，割り当てる場合があり，トリプル再構築する必要がある．本研
究は，再構築する必要がなく，Subject，Predicate，Object そศ๭㸱

5HGXFH

ศ๭㸳

咄
咄
咄

ฟຊ㸰

0DS

図 2 MapReduce 処理の流れ

Object の三つを 1 job で復号化してから再構築を行う Triple
Reconstruction 法（手法 2）を提案する．
Element Job 法は MapReduce の 3 job で行い，各 job では
各トリプル要素を復号化し，復号化した要素をトリプルに代入する．この手法は RDF データの一部，たとえば Object だ

割され，多くのマシンに分散される．一つのブロックは一つのmap 処理を実行する単位である map タスクへ割り当てられる．
map タスクはブロックを読み込み，ユーザーが定義した map
関数を実行する．map 関数は入力された 1 個の〈key ，value〉ペア を内部で処理して，新たな〈key ，value〉ペア として出
力する．出力する〈key ，value〉ペア は 2 個以上になることもあるし，1 個もないこともある．

Shuﬄe & Sort フェー ズ は ，map フェー ズ が 出 力 し た〈key ，value〉ペア をマージしてソートし，同じ key を持つ〈key ，value〉ペア 同士を集約する．key ごとに value をリストアップして，reduce タスクに振り分ける．この処理は Hadoop
側が面倒を見てくれるので，ユーザーは何もする必要がない．

Reduce フェーズは〈key ，value のリスト〉ペア を受け取って，内部で処理した結果を新たな〈key ，value〉ペア として出力する．

け，を復号化する場合に適する．Triple Reconstruction 法は

MapReduce の 2 job で行い，1 job 目はトリプルの Subject，Predicate，Object の同じ要素をグループ化し，復号化を行い，2 job 目はトリプルの再構築を行う．Triple Reconstruction 法
は Element Job 法と違って，ある Subject とある Object が同じ場合もまとめられる．あるトリプルの Subject とほかのトリ
プルの Object が同じ場合が多いと予想しており，この手法はRDF データの全要素を復号化する場合に適する．
3. 1. 1 Element Job 法
MapReduce を実行するとき 1 job で全要素を復号化すると各トリプル要素が異なるタスクに割り当てる場合があり，トリ
プル再構築する必要がある．トリプルの Subject，Predicate，Object をそれぞれの要素を復号化してトリプルに代入すると再構築する必要がない．そこで，Element Job 法はそれぞれの要素を各 MapReduce ジョブで復号化を行う．各段で，暗号化されたトリプル要素を key，そのトリプルを value とし，

3. 提 案 手 法
本研究では，個人情報を記述する枠組みとして RDF を想定する．RDF は，Subject，Predicate，Object の三つ組みで表
現され，それぞれに暗号化することができ，本研究がやろうとしていることに向いている．
並列化のアプローチとしては，MapReduce の枠組みを利用することを想定する．MapReduce では，今回のように大量のデータに対して条件を満たすデータをまとめて同様の処理を行うような場合に向いている．
本研究では，準同型性を利用できる単純な集約処理の場合と，複雑な集合処理で全体を一旦復号化して処理する場合を想定す
る．準同型性が利用できる場合，MapReduce を用いた準同型性を利用した・しない手法を提案し，その比較を行う．全体を一旦復号化して処理する場合 MapReduce を用いた復号化手法
を 2 種類提案し，その比較を行う．
以下，f は暗号関数として，各手法を詳細に説明する．

3. 1 全体を一旦復号化する必要がある場合の復号化手法
一般に考えると RDF データに対して，RDF トリプルが一個づつ復号化する手法 (手法 0) があるが，復号化時間が長く，また RDF データの中に同じトリプル要素の出現が多いことを想定し，同じ要素をまとめてから復号化を行う手法を提案する．

MapReduce により key をグループ化され，key を復号化し，トリプルに代入する．

Element Job 法における MapReduce 1 job 目はアルゴリズ
ム 1 のように行われる．まず，Map フェーズでは，トリプルを解析し（行 2），暗号化された Subject を key，トリプルを valueとなる〈key，value〉ペアを出力する（行 4）．Shuﬄe & Sort
フェーズは暗号化された Subject をグループ化し，暗号化された Subject（encSubject）とトリプルのリスト（tripleList）をReduce に振り分ける．次に，Reduce フェーズでは暗号化された Subject を復号化（行 7）し，トリプルのリストの各トリプ
ルに対し，復号化した Subject を代入し，トリプルを出力する（行 8-11）．1 段目では，Subject が復号化されたトリプルが得られる．同様に 2 job 目と 3 job 目で Predicate，Object を復号化してトリプルに代入する．
図 3 は実例である．図は青色を key，紫色を value で表現する．

3. 1. 2 Triple Reconstruction 法
RDF データの中にあるトリプルの Subject とほかのトリプ
ルの Object が同じ場合もあり，MapReduce の 1 job で全要素を復号化するとそのような Subject と Object がまとめられる．
そこで，Triple Reconstruction 法の MapReduce 1 job 目は暗号化されたトリプル要素をグループ化することによりトリプル

アルゴリズム 1 Element Job 法 MapReduce 1 job 目 Subject

MapReduce 2 job 目（アルゴリズム 3）の Map フェーズでの復号化

は，トリプル要素のリストの各トリプル要素（termInfo）に

入力: n-triples 形のトリプル，トリプルの Id

対して，termInfo からトリプル要素の位置とトリプルの id

出力: 暗号化された Subject，トリプルを取得する．トリプルの id を key，termObject（トリプル要

1: function map(tripleString, tripleId)
2:

triple ← parse(tripleString)3:

subject ← triple.getSubject()4:

emit(subject, triple)

素，その要素の位置）を value となる〈key，value〉ペアを出▷ トリプルを解析▷ 暗号化された Subject，トリプルを

key-value として出力力する（行 6）．Shuﬄe & Sort フェーズはトリプルの id をグ
ループ化し，トリプルの id（tripleId）と termObject のリスト（termObjectList）を Reduce に振り分ける．次に，Reduce
フェーズでは termObject のリストの各 termObject に対して，

5: end function

termObject から要素の内容と位置を取得し，トリプル (triple)
入力: 暗号化された Subject，トリプルのリストに代入する（行 10-18）．最後に，トリプルを出力する．

出力: 暗号化された Subject，トリプル

図 4 と図 5 は実例である．

6: function reduce(encSubject, tripleList)
7:

subject ← decrypt(encSubject) ▷ 暗号化された Subject を復号化

8:

全要素の復号化

for all triple ∈ tripleList do

入力: n-triples 形のトリプル，トリプルの Id

subject を triple に代入▷ 復号化した Subject をトリプル

9:

アルゴリズム 2 Triple Reconstruction 法 MapReduce 1 段目

出力: 暗号化されたトリプル要素，termInfo(トリプル Id，その要素の

に代入
10:
11:

位置 (S か P か O か))emit(subject, triple)

1: function map(tripleString ，tripleId)

end for

12: end function   
   
   
    ŵĂƉĨ;WĞƌƐŽŶϭͿ͕dϭ

Ĩ;WĞƌƐŽŶϭͿ͕dϮ

ධຊ䝕䞊䝍

^ŚƵĨĨůĞΘ^ŽƌƚĨ;WĞƌƐŽŶϭͿ͕΀dϭ ͕dϮ΁

triple ← parse(tripleString)3:

subject ← triple.getSubject()

4:

termInf o ← (tripleId，
“S”)

5:

emit(subject, termInf o)6:predicate ← triple.getP redicate()

7:

termInf o ← (tripleId，
“P”)

8:

emit(predicate, termInf o)9:object ← triple.getObject()10:

termInf o ← (tripleId，
“O”)

11:

emit(object, termInf o)▷ トリプルを解析

12: end function

Ĩ;WĞƌƐŽŶϮͿ͕΀dϯ ͕dϰ΁ƌĞĚƵĐĞ
䜢᚟ྕ໬䛧䚸
᚟ྕ໬䛥䜜䛯
䜢ฟຊĨ;WĞƌƐŽŶϭͿ͕Ĩ;WĞƌƐŽŶϮͿ^ƵďũĞĐƚ

入力: 暗号化されたトリプルの要素，(トリプル id と要素の位置) のリ䛜dϭ͕dϮ͕dϯ͕dϰ

図 3 Element Job 法

2:

MapReduce 1 job 目 Subject の復号化

スト
出力: 復号化されたトリプルの要素，(トリプル id と要素の位置) のリ
スト
13: function reduce(encT erm，termInf oList)
14:

term ← decrypt(encT erm) ▷ 暗号化されたトリプル要素を復号化

要素を復号化する．2 job 目はトリプル id をグループ化するこ

15:とによりトリプルの再構築を行う．

16: end function

emit(term, termInf oList)

Triple Reconstruction 法における MapReduce の手順はアルゴリズム 2 とアルゴリズム 3 のように行われる．まず，MapRe-duce 1 job 目（アルゴリズム 2）の Map フェーズでは，トリプルを解析し（行 2），各トリプルの要素に対して，暗号化さ

3. 2 準同型暗号データ間の演算を用いる場合の手法
避難所の情報から，避難者 (evacuee) の平均年齢を計算する
集約を例として説明する．集約のクエリーが以下のようになる．

れたトリプルの要素を key，トリプル要素の情報（termInfo=
トリプル Id，その要素の位置 (S か P か O か)）を value とな

SELECT AVG(?X) WHERE {る〈key，value〉ペアを出力する（行 3-11）．Shuﬄe & Sort
フェーズは暗号化されたトリプル要素をグループ化し，暗号化された要素（encTerm）と要素情報のリスト（termInfoList）
を Reduce に振り分ける．次に，Reduce フェーズでは暗号化されたトリプル要素（term）を復号化し（行 14），復号化した要素を key，トリプル要素情報のリストを value となる〈key，value〉ペアを出力する（行 15）．

?Personrdf:type:evacuee .

?Person

:age

?X

}
MapReduce により，人の情報 (避難者かボランティアか等，年
齢の情報) をグループ化し，避難者かどうかを判定し，避難者の年齢の暗号が得られる．準同型性が利用できない場合，復号化してから平文を利用して平均を算出する手法があるが，準同アルゴリズム 3 Triple Reconstruction 法 MapReduce 2 job
目 トリプルの再構築
入力: 復号化されたトリプルの要素，(トリプル id と要素の位置) のリ
スト
出力: トリプルの id，復号化されたトリプルの要素とその要素の位置
1: function map(term，termInf oList)
2:
3:

for all termInf o ∈ termInf oList do
termP osition ← termInf o.getP osition()
tripleId ← termInf o.getT ripleId()

5:

termObject ← (term，termP osition)

6:emit(tripleId, termObject)

7:

ධຊ䝕䞊䝍

Ĩ;WĞƌƐŽŶϭͿ͕;dϭ͕^ͿĨ;ĂŐĞͿ͕;dϭ͕WͿĨ;ϯϬͿ͕;dϭ͕KͿĨ;WĞƌƐŽŶϭͿ͕;dϮ͕^ͿĨ;ŶĂŵĞͿ͕;dϮ͕WͿĨ;zĂŵĂĚĂͿ͕;dϮ͕KͿĨ;WĞƌƐŽŶϮͿ͕;dϯ͕^ͿĨ;ĂŐĞͿ͕;dϯ͕WͿĨ;ϯϬͿ͕;dϯ͕KͿĨ;WĞƌƐŽŶϮͿ͕;dϰ͕^ͿĨ;ŶĂŵĞͿ͕;dϰ͕WͿĨ;^ĂƚŽͿ͕;dϰ͕KͿ▷ トリプル

要素の位置 (S か P か O か) を取得
4:dϭ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ĂŐĞͿ͕Ĩ;ϯϬͿ
dϮ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŶĂŵĞͿ͕Ĩ;zĂŵĂĚĂͿdϯ͗Ĩ;WĞƌƐŽŶϮͿ͕Ĩ;ĂŐĞͿ͕Ĩ;ϯϬͿ
dϰ͗Ĩ;WĞƌƐŽŶϮͿ͕Ĩ;ŶĂŵĞͿ͕Ĩ;^ĂƚŽͿŵĂƉ^ŚƵĨĨůĞΘ^Žƌƚ

end for

8: end function

Ĩ;WĞƌƐŽŶϭͿ͕΀;dϭ͕^Ϳ͕;dϮ͕^Ϳ΁Ĩ;ŶĂŵĞͿ͕΀;dϮ͕WͿ͕;dϰ͕WͿ΁

Ĩ;WĞƌƐŽŶϮͿ͕΀;dϯ͕^Ϳ͕;dϰ͕^Ϳ΁Ĩ;ĂŐĞͿ͕΀;dϭ͕WͿ͕;dϯ͕WͿ΁

入力: トリプルの id，(復号化されたトリプルの要素とその要素の位置)
Ĩ;ϯϬͿ͕΀;dϭ͕KͿ͕;dϰ͕KͿ΁

のリスト

Ĩ;zĂŵĂĚĂͿ͕΀;dϮ͕KͿ΁

ƌĞĚƵĐĞ

出力: トリプル
9: function reduce(tripleId，termObjectList)10:

for all termObject ∈ termObjectList do

11:

if termObject.getP osition =“S” then12:

triple.subject ← termObject.getT erm()

13:

else if termObject.getP osition =“P” then14:WĞƌƐŽŶϭ͕΀;dϭ͕^Ϳ͕;dϮ͕^Ϳ΁WĞƌƐŽŶϮ͕΀;dϯ͕^Ϳ͕;dϰ͕^Ϳ΁ŶĂŵĞ͕΀;dϮ͕WͿ͕;dϰ͕WͿ΁ ĂŐĞ͕΀;dϭ͕WͿ͕;dϯ͕WͿ΁
ϯϬ͕΀;dϭ͕KͿ͕;dϰ͕KͿ΁zĂŵĂĚĂ͕΀;dϮ͕KͿ΁ ^ĂƚŽ͕΀;dϮ͕KͿ΁
図 4 Triple Reconstruction 法 MapReduce 1 job 目 全要素の復号化

triple.predicate ← termObject.getT erm()

15:

else if termObject.getP osition =“O” then16:

triple.object ← termObject.getT erm()

17:Ĩ;^ĂƚŽͿ͕΀;dϮ͕KͿ΁

WĞƌƐŽŶϭ͕΀;dϭ͕^Ϳ͕;dϮ͕^Ϳ΁WĞƌƐŽŶϮ͕΀;dϯ͕^Ϳ͕;dϰ͕^Ϳ΁ŶĂŵĞ͕΀;dϮ͕WͿ͕;dϰ͕WͿ΁ĂŐĞ͕΀;dϭ͕WͿ͕;dϯ͕WͿ΁
ϯϬ͕΀;dϭ͕KͿ͕;dϯ͕KͿ΁zĂŵĂĚĂ͕΀;dϮ͕KͿ΁ ^ĂƚŽ͕΀;dϰ͕KͿ΁

end if18:

end for19:emit(triple)

ධຊ䝕䞊䝍

ŵĂƉ
dϭ͕;WĞƌƐŽŶϭ͕^ͿdϮ͕;ŶĂŵĞ͕WͿ

dϯ͕;WĞƌƐŽŶϮ͕^ͿdϮ͕;WĞƌƐŽŶϭ͕^Ϳdϰ͕;ŶĂŵĞ͕WͿ

dϭ͕;ĂŐĞ͕WͿ

dϰ͕;WĞƌƐŽŶϮ͕^Ϳdϭ͕;ĂŐĞ͕WͿ

20: end functiondϭ͕;ϯϬ͕KͿ

dϯ͕;ϯϬ͕WͿ

dϮ͕;zĂŵĂĚĂ͕WͿ

dϰ͕;^ĂƚŽ͕KͿ

^ŚƵĨĨůĞΘ^Žƌƚ

型暗号が利用できる場合，加法準同型性を利用して暗号化したままの暗号文で年齢の合計が求められ，人数で割ることで平均dϭ͕΀;WĞƌƐŽŶϭ͕^Ϳ͕;ϯϬ͕KͿ ͕;ĂŐĞ͕WͿ΁

dϮ͕΀;WĞƌƐŽŶϭ͕^Ϳ͕;ŶĂŵĞ͕WͿ ͕;zĂŵĂĚĂ͕KͿ΁

年齢が計算できる．

dϯ͕΀;WĞƌƐŽŶϮ͕^Ϳ ͕;ĂŐĞ͕WͿ͕;ϯϬ͕KͿ΁

dϰ͕΀;WĞƌƐŽŶϮ͕^Ϳ͕;ŶĂŵĞ͕WͿ ͕;^ĂƚŽ͕KͿ΁

ƌĞĚƵĐĞ

3. 2. 1 準同型性を利用した場合
集約処理は 2 ステップに分けられる．ステップ 1 は MapRe-dϭ͗WĞƌƐŽŶϭ͕dϮ͗WĞƌƐŽŶϭ͕dϯ͗WĞƌƐŽŶϮ͕dϰ͗WĞƌƐŽŶϮ͕

duce で結合を実行し，暗号化された年齢が得られる．ステップ
2 はステップ 1 から得られたデータを集計し，平均年齢を求める．ステップ 1 における MapReduce の手順はアルゴリズム 4のように行われる．ステップ 2 はアルゴリズム 5 のようになる．

ĂŐĞ͕ϯϬŶĂŵĞ͕zĂŵĂĚĂ
ĂŐĞ͕ϯϬŶĂŵĞ͕^ĂƚŽ

図 5 Triple Reconstruction 法

MapReduce 2 job 目 トリプル再構築

まず，ステップ 1 の MapReduce（アルゴリズム 4）の Map
フェーズでは，そのトリプルは年齢の情報（Predicate は “:age”

めた情報が避難者の情報かどうかを判定する（行 18:サイズがの暗号と等しい）（行 3）があれば，トリプルの subject（人），2 以上なら避難者である）．避難者の場合，年齢の情報を取りobject（年齢）を出力する．そのトリプルは避難者を指すトリ（行 20），避難者数を加算され（行 21），加法準同型性を利用

プル（Predicate は “rdf:type” の暗号と等しく，かつ Object

して合計年齢の暗号を計算する．各 Reduce タスクが終わる前

は “:evacuee” の暗号と等しい）であれば，トリプルの subjectに求めた避難者数と合計年齢の暗号を出力する．

（人），object（避難者）を出力する．

ステップ 2（アルゴリズム 5）では，各 Reduce タスクから，

Shuﬄe & Sort フェーズは暗号化された Subject をグルー

全体の避難者数を計算し，加法準同型性を利用して全体の合計

プ化し，暗号化された Subject（encSubject）と暗号化された年齢の暗号を計算（行 6）して復号化する（行 8）．全体の避難

Object のリスト（encObjectList）を Reduce に振り分ける．

者数と全体の合計年齢から平均年齢を計算（行 9）して結果をこのフェーズは人ごとに年齢の情報と避難者かどうかの情報を出力する．

グループ化する．
次に，Reduce フェーズでは encObjectList のサイズでまと

図 6 は MapReduce 実行例である．

アルゴリズム 4 準同型性を利用した場合の手法のステップ 1

アルゴリズム 5 準同型性を利用した場合の手法のステップ 2 平

MapReduce job

均年齢の計算入力: n-triples 形のトリプル，トリプルの Id

入力: 各 reduce タスクからの避難者数，暗号化された年齢の合計

出力: 暗号化された Subject，暗号化された年齢，または暗号化された

出力: 平均年齢

避難者の URI(:evacuee)

1: function getAverageAge(reduceT askOutputList)

1: function map(tripleString ，tripleId)
2:

triple ← parse(tripleString)3:

if triple.getP redicate() = f (“ : age′′ ) then

▷ トリプルを解析

2:

totalEvacuee ← 0

3:

encT otalAge ← 0

4:

for all out ∈ reduceT askOutputList do
totalEvacuee ← totalEvacuee+out.getN umEvacuee()4:subject ← triple.getSubject()5:5:object ← triple.getObject()6:6:emit(subject，object)

7:

end forencT otalAge ← encT otalAge × out.getSumAge()7:else if triple.getP redicate() = f (“rdf : type′′ ) then8:

totalAge ← decrypt(encT otalAge)

8:

if triple.getObject() = f (“ : evacuee′′ ) then9:averageAge ← totalAge ÷ totalEvacuee
return averageAge

9:subject ← triple.getSubject()

10:

10:

object ← triple.getObject()

11: end function

emit(subject，object)

11:
12:
13:

ධຊ䝕䞊䝍

end ifend if
 
!

#

14: end function

入力: 暗号化された Subject，暗号化された Object のリスト
出力: 避難者数，暗号化された年齢の合計
15: numEvacuee ← 0
16: encSumAge ← 1                  "      19:

Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ϱϬͿ

for all encObject ∈ objectList do
if encObject =| f (“ : evacuee′′ ) then ▷ Object は暗

21:

numEvacuee ← numEvacuee + 1

22:

encSumAge ← encSumAge

×  

^ŚƵĨĨůĞΘ^Žƌƚ
object ▷ 加法準同型性を利用し，年齢の合計の暗号を計算する．この場合はĨ;WĞƌƐŽŶϭͿ͕΀Ĩ;ϱϬͿ ͕ Ĩ;͗ĞǀĂĐƵĞĞͿ΁ 25:ƌĞĚƵĐĞ

end ifŶƵŵǀĂĐƵĞĞ сϯĞŶĐ^ƵŵŐĞ сĨ;ϱϬнϭϬͿ

end forend if

26: end function   

Paillier 暗号の場合の計算である．
24: 

号化された年齢かどうかを判定する

23:



ŵĂƉ

if encObjectList.size() >= 2 then ▷ 避難者かどうかを判定

20:



͘͘͘

17: function reduce(encSubject，encObjectList)
18:



図6

準同型暗号データ間の演算を用いる場合の手法

ステップ 1

27: function reduceCleanUp ▷ reduce タスクの全部 reduce 関数の実行が終わった後，Reduce タスクが終わる前に呼ばれる．
28:

emit(numEvacuee, encSumAge)

29: end function

3. 2. 2 準同型性を利用しない場合
準同型性を利用した場合と同じく，個人情報をもとめて，避難者の数を数え，避難者の年齢の暗号を取るが年齢の暗号を一旦復号化してから平均年齢を計算する．

4. 実

表1

実験機材

CPU

Intel Xeon E5620OS

Core 数

8(16 threads)

CoreFrequency

2.40GHz

メモリ

24GB

OS
Java

Ubuntu11.10
1.6

HadoopVersion 1.0.4

Ethernet

1GB/s

験

4. 1 実験の環境
マシン台数 1 台〜4 台 (表 1) を利用して実験を行った．

4. 1. 1 暗号アルゴリズム
本実験は RSA-2048bit と Paillier-2048bit を利用して，実験が行った．但し，Paillier 暗号は確定的暗号ではないので乱数を定数にして暗号化した．

4. 1. 2 データセット
本実験で使用するデータセットは RDF ベンチマークの Lehigh

University Benchmark(LUBM [11]) である．仮想的な大学組
織の大学数をパラメータとして生成した RDF データである．
全体を一旦復号化する必要がある場合の復号化手法の実験では 50 大学のデータ (LUBM50) を生成した．また，準同型暗号

データ間の演算を用いる場合の手法の実験では学部生の平均点を計算するため各学生に平均点 (ub:averageScore) を追加し，

ᐇ⾜᫬㛫䠄༓⛊䠅

50 大学のデータ (LUBM50EX) を生成した．生成したデータ
を Jena [4] により n-triples の形に変換し，RSA，Paillier アル
ゴリズムで暗号化したデータを入力データとする．データの詳
細は表 2 で示す．
全体を一旦復号化する必要がある場合の復号化手法の実験では LUBM50 のデータセットを利用し，RSA，Paillier アルゴ
リズムでそれぞれの暗号化したデータに対して，Element Job
法と Triple Reconstruction 法を比較する．準同型暗号データ間の演算を用いる場合の手法の実験は，LUBM50EX のデータ

ϮϬϬ
ϭϴϬ
ϭϲϬ
ϭϰϬ
ϭϮϬ
ϭϬϬ
ϴϬ
ϲϬ
ϰϬ
ϮϬ
Ϭ

ᡭἲϬ͗ĂƐĞůŝŶĞᡭἲϭ͗ůĞŵĞŶƚ:ŽďἲᡭἲϮ͗dƌŝƉůĞZĞĐŽŶƐƚƌƵĐƚŝŽŶἲϭ

セットを利用し，加算準同型性をもっていない RSA 暗号で通常の手法と加法準同型性をもつ Paillier 暗号で準同型を利用し

図8

Ϯ
䝬䝅䞁ྎᩘ

ϰ

全体を一旦復号化する必要がある場合の復号化手法 Paillier 暗号

た手法を比較する．
表2

くなり，同じ暗号文のまとめてから復号化する手法の効果があ

実験データ

データセット

LUBM50 LUBM50EX

トリプル数

6,865,225

7,425,365

また，Triple Reconstruction 法は Element Job 法より早い

人数549,818

618,235と分かった．その理由については，図 9 に示すように Element

暗号しないサイズ

1.09 GB

1.16 GBRSA 暗号サイズ

6.32 GB

6.71 GB

Paillier 暗号サイズ

13.1 GB14.2 GBることが分かる．

Job 法の場合は各要素が別々の MapReduce Job で復号化が行うのである Subject とある Object の同じ暗号文になる場合でもまとめることにならなく，Triple Reconstruction 法より復号化回数が多くなり，実行時間が遅くなったと考えられる．

4. 2 実験の結果
4. 2. 1 全体を一旦復号化する必要がある場合の復号化手法

dϭ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϮͿdϮ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϯͿdϯ͗Ĩ;WĞƌƐŽŶϯͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϭͿの実験結果

50 大学のデータ (LUBM50)(表 2) を RSA，Paillier アルゴᡭἲϭůĞŵĞŶƚ:Žď ἲ

リズムで暗号化されたデータを利用し，マシン台数を増やしたdϭ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϮͿdϮ͗ Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϯͿdϯ͗Ĩ;WĞƌƐŽŶϯͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϭͿ

場合の実行時間をそれぞれ図 7 と図 8 に示す．手法 0 は同じ要素をまとめなく，各トリプルの一個づつを復号化した場合の実dϭ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϮͿdϮ͗Ĩ;WĞƌƐŽŶϭͿ͕Ĩ;ŬŶŽǁƐͿ͕ Ĩ;WĞƌƐŽŶϯͿdϯ͗Ĩ;WĞƌƐŽŶϯͿ͕Ĩ;ŬŶŽǁƐͿ͕Ĩ;WĞƌƐŽŶϭͿ

図 9 Element Job 法と Triple Reconstruction 法のグループ化

行時間である．

ϲϬ

4. 2. 2 準同型暗号データ間の演算を用いる場合の手法の実ᡭἲϬ͗ĂƐĞůŝŶĞ験結果ϱϬᐇ⾜᫬㛫䠄༓⛊䠅ᡭἲϮdƌŝƉůĞ ZĞĐŽŶƐƚƌƵĐƚŝŽŶἲᡭἲϭ͗ůĞŵĞŶƚ:ŽďἲϰϬ

各学生に平均点 (ub:averageScore) を追加した 50 大学のデーᡭἲϮ͗dƌŝƉůĞZĞĐŽŶƐƚƌƵĐƚŝŽŶἲタ (LUBM50EX) を RSA，Paillier アルゴリズムで暗号化されϯϬたデータを利用した．集約のクエリーが以下のようになる．

ϮϬ

SELECT AVG(?X) WHERE {?Person rdf:type ub:UndergraduateStudent ,ϭϬ?Person ub:averageScore ?X
}

Ϭ
ϭ

Ϯ
䝬䝅䞁ྎᩘ

ϰ
準同型性の手法は Paillier アルゴリズムで暗号化されたデータ，
通常の手法は RSA アルゴリズムで暗号化されたデータを利用

図7

全体を一旦復号化する必要がある場合の復号化手法 RSA 暗号

し，マシン台数を増やした場合の実行時間を図 10 に示す．図10 より，どちらの手法でもマシン台数が増えることによって実図 7 と図 8 より，RSA 暗号が Paillier 暗号より復号化時間

行時間が短くなり，並列化の効果が見える．また，マシン台数が早いが，どちらの暗号アルゴリズムでもシン台数が増えるが増えると準同型性を利用しない場合と準同型性を利用した場ことによって手法 1 と手法 2 とも実行時間が短くなり，並列合の実行時間の比が小さくなり，同じ暗号文をまとめる効果が化の効果が見える．また，Element Job 法（手法 1）と Tripleあると考えられる．

Reconstruction 法（手法 2）は手法 0 より実行時間が約 5 倍短

ϯ
Ϯ͘ϱ
Ϯ
ϭ͘ϱ
ϭ
Ϭ͘ϱ
Ϭ

と準同型性を利用した場合の実行時間の比が小さくなり，同じ

ϲ
ϱ
ϰ
ϯ
Ϯ
ϭ

ϭ
図 10

きた．また，マシン台数が増えると準同型性を利用しない場合

Ϯ
䝬䝅䞁ྎᩘ

ᐇ⾜᫬㛫䛾ẚ䠄ಸ䠅ᐇ⾜᫬㛫䠄༓⛊䠅‽ྠᆺᛶ฼⏝䛧䛺䛔ᡭἲ;yͿ‽ྠᆺᛶ฼⏝䛾ᡭἲ;zͿᐇ⾜᫬㛫䛾ẚ;yͬzͿϰ

準同型暗号データ間の演算を用いる場合の手法

暗号文をまとめる効果があると考えられる．
今後の課題として，暗号アルゴリズムを変えた実験を行う必要がある．暗号アルゴリズムによって復号化時間が異なるので，データ転送時間よりどのぐらい効果があるかを確認することが必要である．また，各プライバシーが異なる部分データに対して異なる暗号 key で暗号化されるレベル別暗号もあるので，そのような暗号に向けて，復号化手法も検討する必要がある．

謝

辞本研究の一部は，日本学術振興会科学研究費補助金基盤研究

5. 関 連 研 究(A)(#25240014) の助成により行われた．

データベースにおいて暗号化されたデータに対して演算を実現するための研究としては，CryptDB [7] が挙げられる．

CryptDB は，R. A. Popa ら [5] によって提案された手法である．暗号化されたデータに対して全ての演算を可能とする暗号化アルゴリズムは現在現実的ではない．CryptDB では，暗号化されたデータに対して複数の演算が行えるために複数の暗号化
アルゴリズムを利用して，複数の暗号を作成する．CryptDB は
様々な演算が実行できるが “W HEREsalary > age ∗ 2 + 10”のような複雑な条件の演算は実行できない [7]．

RDF 暗号化の研究としては，M. Giereth により提案したPRE [9] が挙げられる．XML 暗号化手法を利用して，RDF
データを暗号化する．PRE は部分的 RDF 暗号化と復号化手法を提案したが膨大な RDF データの復号化を考慮していない．

MapReduce を用いた大規模な RDF データの処理について
は，M.F. Husain によって提案した RDF データに対してクエリ処理を高速化する HadoopRDF がある。RDF データを事前に Predicate，Object によって複数のファイルに分け，複数のMapReduce ジョブにより集約を行う。また，J. Urbani らにより提案した RDF データ圧縮手法は辞書を利用し，各 RDF ト
リプルの要素は id で代入し，同じ要素をまとめて id で代入することでデータ量を減少する．これらの研究は暗号化データを考慮していない．

6. ま と め
本研究では，MapReduce を用いた暗号化されたデータに対し，平均年齢のような準同型性が利用できる単純な演算の手法と複雑な条件で全体を一旦復号化する必要がある場合の復号化手法を提案し，提案手法を評価した．
実験により全体を一旦復号化する必要がある場合の復号化手法について，マシン台数が増えるとどちらの手法も実行時間が短くなり，並列化の効果が確認できた．同じ暗号文をまとめる
ことにより実行時間が約 5 倍早くなり，同じ暗号文のまとめてから復号化する手法の効果があることが分かった．
準同型暗号データ間の演算を用いる場合，準同型性を利用した手法，利用しない手法のどちらの手法もマシン台数が増えるとどちらの手法も実行時間が短くなり，並列化の効果が確認で

文

献[1] Apache Hadoop.
http://hadoop.apache.org，2014[2] Jeﬀrey Dean，Sanjay Ghemawat，“Mapreduce: Simplied
data processing on large clusters”，Proceedings of the 6th
Symposium on Operating Systems Design and Implementation (OSDI ’04)，pp.137-149，2004[3] Message Passing Interface Forum
http://www.mpi-forum.org，2012[4] Jena
http://jena.apache.org，2014[5] R. L. Rivest，A. Shamir and L. Adleman，“A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems”，Communication of the ACM，21，2，pp. 120―126，
1978.
[6] P. Paillier，“ Public-Key Cryptosystems Based on Composite Degree Residuosity Classes”，EUROCRYPT 1999，
pp223-238，1999[7] R.A. Popa，N. Zeldovich，H. Balakrishnan，“CryptDB: A
Practical Encrypted Relational DBMS”，Technical Report
MIT-CSAIL-TR-2011-005, MIT (2011)[8] M. Giereth，“PRE4J - A Partial RDF Encryption API forJena”，Academic Medicine，70(3):216―223，2006.
[9] M. Giereth，“Partial Encryption of RDF
Graphs”
ISWC
2005, pp. 308―322，Springer，2005.
[10] J. Urbani, J. Maassen, N. Drost, F. Seinstra, H. Bal， “Scalable RDF data compression with MapReduce. Concurrency
and Computation”， Practice and Experience 25(1), 24―
39, 2013.
[11] Y. Guo, Z. Pan, J. Heﬂin，“LUBM: A Benchmark for OWL
Knowledge Base Systems”，Journal of Web Semantics 3(2),158―182, 2005.
[12] M.F. Husain, J.P. McGlothlin, M.M. Masud, L.R. Khan,
B.M. Thuraisingham，“Heuristics-based query processing
for large RDF graphs using cloud computing”，IEEE Trans.
Knowl. Data Eng. 23(9), 1312―1327, 2011.
[13] C. Gentry，“Fully homomorphic encryption using ideal lattices”，Proceedings of the 41st ACM Symposium on Theory of Computing (STOC 2009), pp. 169-178, ACM, 2009.
[14] HElib
https://github.com/shaih/HElib，2014[15] S. Halevi，“Performance of HElib”，2012
http://mpclounge.files.wordpress.com/2013/04/hespeed.pdf[16] C. Moore, M. O’Neill, E. O’Sullivan, Y. Doroz, B. Sunar,“Practical homomorphic encryption: A survey”，Circuits
and Systems (ISCAS), 2014 IEEE International Symposium
on , vol., no., pp.2792,2795, 2014