DEIM Forum 2016 F8-1

リンケージポリシ執行を保証するレコードリンケージ
海寳

貴人†

陸

文杰†

佐久間

淳††,†††† 筑波大学システム情報工学研究科 〒 305-8573 つくば市天王台 1-1-1†† 筑波大学システム情報系 〒 305-8573 つくば市天王台 1-1-1††† 科学技術振興機構 CREST 〒 102-0076 東京都千代田区五番町 7K’s 五番町
E-mail: †{takahito,riku}@mdl.cs.tsukuba.ac.jp, ††jun@cs.tsukuba.ac.jp
あらまし

個人情報を個別に集積した複数のデータベースに対して同一人物のレコードを連結するレコードリンケー

ジは, 新たな知見の獲得に貢献するが, 個人の望まない, あるいは意図しない連結はプライバシ侵害を招く. 本研究では, 個人が主体的にデータベース間の任意の 2 データベース間のレコードリンケージの可否についてプライバシポリ
シを定め, 個人が望まないレコードリンケージは実行できないような準同型暗号に基づく暗号プロトコルを提案する.
論文では, N データベース中の任意の 2 データベース間の連携の拒否を指定するホワイトリスト方式と, 同様に任意の2 データベース間の連携を拒否するブラックリスト方式の二通りのプライバシポリシを定式化し, そのようなポリシに従うレコードリンケージの制御を実現する暗号プロトコルの正しさとセキュリティを示す. また実験により, データ
ベース数 50 個のレコードリンケージについては, 各データ登録者に対してホワイトリスト方式では 1 秒未満, ブラッ
クリスト方式では約 23 秒でプロトコルを実施できることを示した.
キーワード

リンケージポリシ, 準同型暗号, プライバシ保護, 秘密計算, 表結合

1. は じ め にる. しかし, 無制限にレコードリンケージを実施した場合にデー
タ登録者のプライバシが侵害されるリスクがある. 具体的には,

インターネットの技術発達により, サイトに個人情報を登録

データ登録者が特定の事業者に対してのみ連結を許していた情することでサービスを受けられるシステムが増加している. 例報が異なる事業者の保持する情報に意図せず連結される可能性

として, サイトに登録された住所へユーザが注文した商品を配がある. ( 2 ) のサービスが実現した場合を例に考える. 保険会

達する電子商取引のサービスが挙げられる. サイト内の個人情

社と病院のデータをリンケージした後, 最寄りの病院の推薦を報は, データの集積を行うデータベースにレコード形式で保管目的としてデータの分析者が病院と SNS サイトのデータベーされている. 個人情報を保管した複数のデータベースについて,スをリンケージした場合, SNS サイト事業者が別途保険会社か同一のユーザに関するレコードを連結し共通点や関連性などをらデータ提供をうけたときに, 病院のデータを手掛かりにして分析することによって新たなサービスの創出や新たな知識の発保険会社と SNS サイトのデータをリンケージできる. このとき

見につながることが期待されている. 例として, 以下のようなデータ登録者は, 自身の疾患, 保険料に関する情報など, 保険会

サービスが挙げられる.

社と病院にのみ公開したい情報が SNS サイトのデータと結合（ 1 ） インターネットの利用時, 検索サイトで検索したワーすることでに SNS 事業者に知られる恐れがある.

ドにしたがって, 電子通販サイトや各種サイト内の広告バナー

近年, データ登録者のプライバシを考慮したレコードリンケーに, 検索ワード関連した商品を表示する.

ジについての研究が行われているが, いずれの手法においても,（ 2 ） 保険会社が, 自社の利用者のデータと病院が管理する

d 個のデータべースのリンケージによって得られる d2 個のリデータを組み合わせることで, 利用者に最適のプランを紹介

レーションの管理や, データ登録者の意思に対する配慮がなさする.

れていない. 本研究では, これらを考慮したレコードリンケー( 1 ) の例はすでに実現されている例であり, ( 2 ) はこれから予ジをコントロールするためのプロトコルを提案する.

想されるサービスの例である.

1. 1 関連研究：プライバシ保護レコードリンケージ

複数のデータベースに対するデータの分析を行うときに有用

レコードリンケージとは, 複数のデータベースに対して同一な技術の一つとしてレコードリンケージが挙げられる. レコーの人物についてのデータを結合する技術であり, 複数のデータ

ドリンケージとは, 異なるデータベースから共通の要素を持つ

ベースに対してデータマイニングや統計値の分析などを行うとデータレコードを発見し, そのレコードの組を結合する技術できに有用である. 現在, わが国において官公庁や企業間で統一ある.

されている識別子は少ないが, マイナンバー法の施行によりレ

より多くのデータベースの共通の要素を連結するレコードリ

コードリンケージを用いた情報分析への期待が高まっている.

ンケージを実施することで, データに対してさらに詳しい分析

データ登録者のプライバシを保護しながらレコードリンケーを行える. 日本に限っていえば, 2015 年に成立した改正個人情ジを行うプライバシ保護レコードリンケージについて紹介する.

報保護法では, 匿名加工情報の同意なき移転, 流通を認めていプライバシ保護レコードリンケージでは, 識別子やデータその利用者 ID

メールアドレス

購入金額総計住所

ID

購入金額総計（商取引）

預金額（銀行）

001

one@ex.com¥5,900

東京都○○区……

001¥5,900¥332,000

002

two@ex.ac.jp¥8.500茨城県□□市……

002¥8,500¥169,000

003

three@ex.co.jp¥14,200

千葉県××市……

003¥14,200¥562,000004

four@ex.com¥7,300神奈川県△△市……

004¥7,300¥234,000

表 3 例：表結合の結果の一部

表 1 例：電子商取引サイトの Database が保管するデータの一部
口座 ID

電話番号

預金額

住所

001

080-www-wwww ¥332,000

東京都○○区……

002

090-xxx-xxxx ¥169,000

茨城県□□市……

003

090-yyy-yyyy ¥562,000

千葉県××市……

004

080-zzz-zzzz ¥234,000 神奈川県△△市……

表2

i

∈I

各 DC の識別子c∈N

DC の総数j∈J

各 Database の識別子

d∈N

Database の総数

lst (i) ∈ {0, 1} DC i がもつ Database(s, t) のポリシ
xij

例：銀行の Database が保管するデータの一部

q∈X

DC i が Database j に登録するデータ
Analyst が LM へ送信するクエリ
表4

ノーテーション

ものの暗号化, 匿名化を行うことでユーザのデータを公開せずに安全なレコードリンケージを達成することを目的とする. 具
体的には, 偽のデータを含めたデータレコードの暗号化を行う
手法 [1], フォネティックコードを用いてデータの変換を行う手
法 [2], Bloom Filter を用いて暗号化した文字列が一致するか否かを確かめる手法 [3], データをブロックごとに分け各ブロッ
クの差分プライバシを考慮する手法 [4] などが挙げられる. 論
文 [5] では, 元データの改変, データに付与されるラベルの暗号化, データの曖昧化を行うことでデータ登録者の情報を匿名化
し, データ登録者のプライバシを保護する手法が現在までの研究として示されている.

1. 2 貢献

本研究が既存の手法と異なる点は大きく二つある. 一つ目は,データの分析結果の相違である. データの匿名化を行う手法では, データの本来のデータとは異なるデータを用いてリンケージを行うため正確なデータ分析を実施することが困難である.
本研究では, 暗号上の加減算が可能な準同型暗号を用いてデータを加工せずにリンケージを行うため, 正しい分析結果を得る
ことができる. 二つ目は, システム管理者に対してポリシの執行を強制できることである. 既存の研究ではデータ登録者のデー
タに対する処理のみを行っており, データ登録者の意思を考慮していない. 本研究では, ユーザのポリシを暗号化することで,システム管理者に悪意がある場合でも安全にレコードリンケージを行うことができる.
本研究では, データ登録者のプライバシに配慮しながら正確な情報を用いたレコードリンケージを実現するため, データ登
録者がデータ分析者に対してプライバシポリシを執行, すなわ
ち連結の可否を任意の二つのデータベースに対して指定できるプロトコルを提案する. ポリシを保護しながらデータ結合を行うことを可能とするため, 準同型暗号の一種である Paillier 暗号を導入した. また, 提案したプロトコルの実行時間を検証し,本手法が現実的な時間で実施可能であることを示す.

2. 問 題 設 定
2. 1 ステークホルダ
本研究のデータの操作に関連するステークホルダを以下に示す.

•

Database … Data Contributor からデータを受け取り,管理を行う. Database は複数存在しており, Database 一つ一つに保持者が存在すると仮定する. Database の保持者の例として, 銀行, 商取引サイト, 病院, IC カードの管理会社などが挙げられる. これらのサイトには, 表 1, 表 2 のような形式で個人ごとにデータが保管されている.

•

Data Contributor (以下, DC) … Database にレコード形式でデータを登録する. DC は複数存在している. 各 DC には一意な識別子が割り当てられており, すべての Database にデータを識別子とともに登録していると仮定する. 1 レコード
は 1 人の個人情報を表す.
表 1, 表 2 を結合することで得られる結果の一部を表 3 に示す. 以上の表から各個人の電子商取引サイトの購入総額と銀行の預金額が明らかになる. このとき, 預金額と購入金額総計を同時に公開することで, DC は商取引サイトに銀行の預金額を把握される. 商取引サイトに銀行のデータを閲覧されたくない

DC は, 結合を拒否する意向を示すことで自身のデータを結合
結果から取り除くことができる. 具体的には, DC は任意の二つの Database からなる各組に対して, 自分自身のデータレコー
ドの結合を許可するか拒否するかを決定できる. 結合を「許可」するか「拒否」するかを示す意向を本研究ではポリシとよぶ.

•

Analyst … 任意の二つのデータベースや属性を指定し,レコードリンケージを実施する結合クエリを発行し, 結合表を得て統計的な知識の獲得や分析を行う. Analyst は Database である場合も, 第三者である場合も想定する. Analyst は, Linkage

Manager に対してクエリを送信し, Database 内のデータの結合表を Linkage Manager から受け取る. 例として, 電子商取引
サイトでの購入総額と銀行の預金額に相関性があるかどうかを分析したい Analyst は, 表 3 を得るために Linkage Manager
へ該当する二つのデータベースの購入金額と預金額についてリ
ンケージ依頼をクエリとして送信する.

•

Linkage Manager (以下, LM) … Analyst からのリクエストに応じ, 指定された Database 間に存在するデータの結合が可能かどうかを各 DC ごとに調べ, 結合表を返す.

図 1 システムの全体像

図 3 ブラックリストの例：ブラックリストの辺を破線で示す. 各

Database は honest である.

図 2 ホワイトリストの例：ホワイトリストの辺を実線で示す.

システムの全体像, 動作の様子を 図 1 に, ノーテーションを
表 4 に記す.

2. 2 ポリシの表現について
各 DC が所有するポリシを表現するために, 頂点はシステム
内の Database に, 辺は Database 間のポリシに対応した無向図 4 連結履歴によってポリシが相違する例：ブラックリストの辺を破線で, クエリ履歴を太線で示す.

グラフを用いる. 本研究では, この無向グラフをポリシグラフとよぶ. c 人の DC が d 個の Database それぞれにデータを登録しているとき, ポリシグラフは DC 一人につき一つ生成され, シ
ステム全体に c 個のポリシグラフが存在している. Database を区別するために, 各 Database には番号 j ∈ J が割り振られている. ポリシグラフの表現方法として, 以下の 2 種類を挙げる.

2. 2. 1 ホワイトリスト方式
ポリシグラフの辺が連携許可を表す場合, この方式をホワイ
トリスト方式とよぶ. ホワイトリスト方式のポリシグラフの頂点間に辺が存在しない場合, 対応する Database 間の連結は拒否されているものとみなす. ホワイトリストのポリシグラフを表現する例として, 図 2 を挙げる. 頂点の番号は各 Database に割り振られている番号を表す. 図 2 の例では, Database 1（電図 5 Database(1,2) と Database(2,3) の連携から Database(1,3) が連携される例

子商取引サイトの Database） と 2（コンビニエンスストアの

Database）, および Database 3（銀行の Database） と 5（電拒否するブラックリストである. Analyst が 1 回目のクエリで子マネーカードの Database） の連携のみが許可されており,

Database 1 と 2 の連結を行う場合をケース (1,2), Database 2

他の任意の二つの Database 間は連携拒否である状態を表す.

と 3 の連結を行う場合をケース (2,3) とし, 以上の二つのケー

2. 2. 2 ブラックリスト方式

スについて考える. 図下段の二つのポリシグラフは, ケースごポリシグラフの辺が連携拒否を表す場合, この方式をブラッとのデータ連結後のグラフである. ケース (1,2) 以降のクエリ

クリスト方式とよぶ (図 3). ブラックリスト方式のポリシグラ

において, Database 2 と 3 の連結を行うと, (1,2) の連結を経

フの頂点間に辺が存在しない場合, 対応する Database 間に関由して, ブラックリストである Database 1 と 3 が連結されるするポリシは, これまでの辺の連結によって決定される. 図 4

ため, Database 2 と 3 の連結は拒否されるべきである. 同様は連結の履歴によって現在許可できる連結が異なる例を示しに, ケース (2,3) においても, これ以降のクエリで Database 1ている. 図上段のポリシグラフは Database 1 と 3 の連結をと 2 の連結は拒否されるべきである. 具体例を図 5 に示す.

DC Database LM Analyst
i-th DC のデータ xij

○

○

×

2. 4. 2 ブラックリスト方式△

Analyst は LM へ二つの Database の番号 s, t を送る. LM

i-th DC のポリシグラフ Gi

○

×

×

×

は, DC が保持するブラックリスト, および Analyst がそれまで

i-th DC についてのクエリ履歴 Qi

○

×

○

△

に実施したクエリの履歴をもとに, Database s, t の連結を行っ

表 5 セキュリティモデル：クエリ履歴は Analyst がクエリを行ったてもブラックリストが連結されない DC のレコードを連結した

後に連携が許可された Database の組が辺に対応する無向グラ

表を Analyst へ送る. これら一連の処理をセキュリティモデル

フを表す. 「○」は, 自分自身がデータの保持者であるとき閲覧可能であることをあらわす. 「△」は, 対象の DC のポリシが許可である場合のみ閲覧可能であることをあらわす. 「×」は閲覧に違反せずに実施する.

3. 要 素 技 術

不可能であることをあらわす.

本章では, セキュリティモデルに基づいたプロトコルを実現
各 DC が個別に Database 間の連結をコントロールする状況
において, 特定の Database 間の結合を許可するホワイトリス
ト方式よりも, 結合を拒否するブラックリスト方式がより現実的である. 一方, ブラックリスト方式の連結許可は過去の連結の履歴によって変化するため, ホワイトリスト方式と比較してポリシが不安定である.

2. 3 セキュリティモデル
ステークホルダ間において閲覧可能なデータ, 閲覧不可能なデータを明確にするため, 当事者とデータの関係を明記したセキュリティモデルを表 5 に示す.
データ xij の閲覧が可能なステークホルダは, データの保持者である i-th DC および DC のデータを管理する j-th Databaseである. LM はデータレコードの結合表のみを返すため, DCが保持するデータを閲覧する必要がない. Analyst は結合表に応じてデータ閲覧の可否が異なり, クエリの対象となる二つのDatabase 間のポリシが許可ならばリンケージの結果であるデー
タを閲覧できる.
ポリシグラフ Gi の閲覧が可能なステークホルダは, ポリシ
グラフの保持者である i-th DC のみである. DC 以外のステークホルダがポリシグラフを閲覧できる場合, 悪意のあるステークホルダが DC に無断でポリシを変更することで, 拒否のポリシが指定されている二つの Database に対してもレコードが結合できる可能性がある.
クエリ履歴 Qi の閲覧が可能なステークホルダは, クエリの対象となるデータを持つ i-th DC, およびクエリの連結を行う

するための要素技術を導入する.

3. 1 reachability matrix
ブラックリスト方式では, クエリごとにポリシが許可であるか否かをクエリ履歴を用いて調べる必要がある. この処理を行うためにポリシグラフの各頂点の連結を reachability matrix で表現する. グラフに対する reachability matrix を生成する際には隣接行列を用いる. 隣接行列はサイズが |V | × |V | である行列である. 頂点 s, 頂点 t をつなぐ辺が存在する場合には, 隣接
行列の (s, t) 要素は 1, そうでなければ 0 をとる. 隣接行列の定義から, 重みなしのグラフの隣接行列 A のべき乗 An の (i, j)
成分は, 頂点 i から頂点 j への長さ n のパスが存在するか否かをあらわす. 頂点数 |V | のグラフにおける reachability matrix

R は以下の式であらわせる [7].
R = A + A2 + · · · + A|V |(1)

R の (i, j) 成分が 1 以上であれば, i から j へのパスが存在するといえる.

3. 1. 1 Paillier 暗号
Paillier 暗号 [8] は加法準同型性をみたす公開鍵暗号方式である. 加法準同型暗号とは, 暗号化された整数どうしの加算を平文同様に行うことが可能である暗号である. 乱数 r ∈ Zn と公開
鍵 pk を用いて平文 m ∈ Zn を暗号化する処理を c = Enc(m; r)と記述する. また, 秘密鍵 sk を用いて暗号文 c を復号する処理
を m = Dec(c) と記述する. Paillier 暗号は以下の性質をもつ.

Enc(m1 ; r1 )Enc(m2 ; r2 ) = Enc(m1 + m2 ; r1 + r2 )LM である. ブラックリスト方式において, LM は各クエリに対m2

Enc(m1 ; r1 )= Enc(m1 m2 ; r1 m2 )

(2)
(3)

応する二つの Database の連結が許可されるか否かを逐一判断するため, クエリ履歴を閲覧する必要がある. Analyst は結合表に応じてクエリ履歴閲覧の可否が異なり, クエリの対象となる二つの Database 間のポリシが許可ならばその結果としてク
エリ履歴を閲覧できる.

以降, 暗号化, および復号の記述を簡略化するため, それぞれEnc(·), Dec(·) と記述する. また, 準同型暗号上の加算を「⊕」,
暗号文と平文との乗算を「⊗」と表記する.

4. 提 案 方 式

2. 4 問 題 定 義
グラフの表現方式別に問題定義を示す.

2. 4. 1 ホワイトリスト方式
Analyst は LM へ二つの Database の番号 s, t を送る. LM
は, DC が保持するホワイトリストをもとに, lst (i) = 1 である

DC のレコードを連結した表を Analyst へ送る. これら一連の処理をセキュリティモデルに違反せずに実施する.

本節では, ポリシグラフの表現別に定式化したアルゴリズムを示す.

4. 1 ホワイトリスト方式
ホワイトリスト方式のポリシグラフを Wi とすると, 対応するプロトコルは以下の手順によって実現される.

•

i-th DC は以下の操作を行う.

（ 1 ） データの連携を許可したい Database の組をすべて選択し, Wi を構成する. 構成する Wi 内の部分集合はすべてクリークとなるよう加工する.

Algorithm 2 Query White（ 2 ） Wi の 0, 1 を反転した Wi ′ を生成する.

Input: s ∈ N, t ∈ N, pk′

Output: {L1 , · · · , Lc }（ 3 ） Wi ′ から, 隣接行列 AWを構成する.
i′（ 4 ） 各 Database に対し, データレコード (i, xij , (AWi ))を登録する.

•

データレコードの登録後, Analyst が次の操作を任意の

回数行う.

′

1: Database s および t は, Enc(AW ), および Enc(x1s ), · · · , Enc(xcs ),Enc(x1t ), · · · , Enc(xct ) を LM へわたす.
2: LM は, 乱数 r を生成する.
3: for i = 1 to c do′

4:

Enc(ai ) ← r ⊗ Enc((AWi )st )

（ 1 ） LM に対して, q = (s, t) を問合わせる.

5:

Li ← Enc(xis + ai )|Enc(xit + ai )（ 2 ） クエリの結果として Li = Enc(xis + ai )|Enc(xit + ai )6: end forを得る. ここで x|y は, データ x, y の結合をあらわす. また, ai

7: LM は, {L1 , · · · , Lc } を Analyst へわたす.

は条件に応じて次の値をとる. r は Zn 上の乱数を示す.

{
ai =

0

(s, t) ∈ Wirotherwise

4. 1. 2 Query Whiteア ル ゴ リ ズ ム Query White を Algorithm 2 に 記 す.

Query White では, Analyst が Database の識別子をあらわす
ホワイトリストの部分集合がクリークでないとき, 不自
然 な ポリシ が発 生す る.

整数の組 (s, t) を LM へ入力する. LM は, 与えられた s, t,

例と して, Database(1,2), およ び

および W ′ の隣接行列に基づいて Enc(ai ) を計算し, 表結合(2,3) のポリシが連結許可であるホワイトリストを考える.

Enc(xis + ai )|Enc(xit + ai ) を生成する. Paillier 暗号は加法

このとき, Database(1,3) のポリシは禁止と設定されているについて準同型性をもつため, LM は xi , および ai に関するが, Database(1,2), および (2,3) のリンケージを行ったときに情報を得ずに Enc(xi + ai ) = Enc(xi ) ⊕ Enc(ai ) を計算でき

Database (1,3) のデータは連結できるため, ホワイトリストのる. i-th DC のポリシが許可であるとき, ai = 0 であるため観点から Database (1,3) のポリシが禁止であることは不自然

xis |xit = Dec(Li ) が成立する. 一方, i-th DC のポリシが拒である. したがって, ホワイトリスト方式のグラフはクリーク

否であるとき, Zn 上の乱数を r1 , r2 として, 表結合の結果はとなるよう加工する必要がある.

r1 |r2 = Dec(Li ) とあらわせるため, Analyst は正しい結合結果

以降, ホワイト方式のプロトコルを実現するアルゴリズムを得られない.

LinkageProtocol White および, Analyst がシステムに送信したクエリを入力として各 DC の結合表を出力するアルゴリズム

4. 2 ブラックリスト方式

Query White について述べる.

ブラックリスト方式のポリシグラフを Bi とすると, 対応するプロトコルは以下の手順によって実現される.

4. 1. 1 LinkageProtocol White•i-th DC は以下の操作を行う.

Algorithm 1 LinkageProtocol White（ 1 ） Bi から隣接行列 AB
i を構成する.

Input of DC: Wi（ 2 ） 各 Database に対し, データレコード (i, xij , (ABi )) を

Output of Analyst: xis |xit (∀ i lst (i) = 1)
1: Analyst は, 公開鍵 pk, 秘密鍵 sk を生成する.
2: i-th DC は, Wi の隣接行列の 0 と 1 を反転させたグラフ Wi ′ を

生成する.

•

データレコードの登録後, 隣接行列が零行列であるグラ

フ Qi を生成し, Analyst が次の操作を任意の回数行う.
（ 1 ） LM に対して, q = (s, t) を問合わせる.

3: i-th DC は以下の処理を行う.

（ 2 ） クエリの結果として, Li = Enc(xis + ai )|Enc(xit + ai )4: for j = 1 to d do
5:

登録する.

′

i-th DC は, pk を用いて Enc(AWi ), および Enc(xij ) を j-thを得る. ここで x|y は, データ x, y の結合をあらわす. また, ai

Database へ登録する.

は条件に応じて次の値をとる. r は Zn 上の乱数を示す.

6: end for
7: SendQuery: Analyst は,{L1 , · · · , Lc } ← Query White(s, t, pk) を得る.

{
ai =

0

Rst = 0rotherwise∀(s, t) ∈ Bi

8: i-th DC のポリシが許可ならば, Analyst は sk を用いて xis |xit =Dec(Li ) を得る.
9: 新たな分析を望む Analyst は SendQuery 以降の処理をふたたび実行する.

（ 3 ） クエリの結果を得た後, 結合結果が正しければ Qi を更新する.

LM は reachability matrix を用いてクエリのたびにポリシの連結が許可されているかどうか確認し, ポリシが侵害されアルゴリズム LinkageProtocol White を Algorithm 1 に記る場合にはデータの連結を防ぐ必要がある. そこで, ブラック

す. LM が行う演算はすべて暗号上で行われるため, DC のポリ

リスト方式では, ホワイトリスト方式で用いたアルゴリズムにシを閲覧できない. また, Analyst は, LM から最終的な計算結

reachability matrix を計算する処理を加えてアルゴリズムの設果を得るのみであるため, 結合表以外の情報を閲覧できない.

計を行う. 以降, ブラック方式のプロトコルを実現するアルゴ
リズム LinkageProtocol Black, Query Black について述べる.

4. 2. 1 LinkageProtocol Black
Algorithm 3 LinkageProtocol Black
Input of DC: Bi
Output of Analyst: xis |xit (∀ i lst (i) =| 0)
1: Analyst は, 公開鍵 pk, 秘密鍵 sk を生成する.
2: i-th DC は以下の処理を行う.
3: for j = 1 to d do
4:

Rk = A × (I + Rk−1 )(4)

R0 = 0(5)|V | 個の点からなる隣接行列 A であるグラフの reachability
matrix は R|V | に相当する. 式 (4), (5) を用いることで, reachability matrix 内の加乗算の演算回数を O(|V |2 ) 回から O(|V |)回へ削減できる.

i-th DC は, pk を用いて Enc(ABi ), および Enc(xij ) を j-th

4. 3 計算量, 通信ラウンドの比較

Database へ登録する.

ホワイトリスト方式とブラックリスト方式の演算回数を比較

5: end forする. ホワイトリスト, ブラックリストの両方式において暗号

6: LM は零行列 Q1 , · · · , Qc を生成する.

文と平文の乗算回数は O(1), 準同型暗号上の加算回数は最悪

7: SendQuery: Anlyst は,

で O(d2 ) 回である. また, ブラックリスト方式の reachability{L1 , · · · , Lc } ← Query Black(s, t, pk) を得る.
8: i-th DC のポリシが許可ならば, Analyst は sk を用いて xis |xit =Dec(Li ) を得る.

matrix を生成する処理に用いる平文の加乗算の回数は, 行列積をもとめる処理から O(cd3 ) 回である.

9: 正しい結果が得られたならば, Analyst は Database(s, t) の連携

以上のことから, Database の数, および DC の数が増えるごを許可であるとみなし, (Qi )st ← 1, (Qi )ts ← 1 を実施する.

とに, ホワイトリスト方式による処理時間とブラックリスト方10: 新たな分析を望む Analyst は SendQuery 以降の処理をふたたび実行する.

式による処理時間の差が大きくなることが考えられる.

5. 実

験

LinkageProtocol Black のアルゴリズムを Algorithm 3 に記提案する各プロトコルについて, 時間の計測を行う. 実験にす. 行列 Qi は各 DC に対するクエリの履歴をあらわす. Query

用いた計算機の CPU は intel Core i7-2600 3.5GHz, メモリ量を実施するごとに, 各 DC が連携許可か否かを確認し, 連携がは 8GB である. プログラムは, ローカル環境で C++を用いて許可されているならば 9 行目でクエリ履歴の更新を行う.

実装した.

4. 2. 2 Query Black

5. 1 実 験 設 定
DC 一人のポリシグラフに対する, プロトコル内のアルゴ

Algorithm 4 Query Black
Input: s ∈ N, t ∈ N, pk, Qi ,Output: {L1 , · · · , Lc }1: Database s および t は, Enc(AB ), および Enc(x1s ), · · · , Enc(xcs ),Enc(x1t ), · · · , Enc(xct ) を LM へわたす.

リ ズ ム Query White, Query Black に か か る 時 間, お よ び グ
ラフの隣接行列を暗号化する処理にかかる時間を計測する.

LinakgeProtocol では, DC がグラフの隣接行列を暗号化する処理が実行時間の大半を占めている. ブラックリスト方式につい2: LM は次の処理を行う. R′ ← 0ては, Query Black において reachability matrix を生成する処

3: for i = 1 to c do

理にかかる時間を加えて計測する. d を 5 から 50 まで 5 刻み

4:for j = 1 to d do

5:

Ri ← Qi · (I + R′i )6:

R′i ← Ri

7:

end for8:

LM は, 点集合 Si := {p|(Ri )sp > 0} を生成する.

9:

LM は, 点集合 Ti := {q|(Ri )qt > 0} を生成する.

10:
11:

LM は, 乱数 r を生成する.
⊕Enc(ai ) ← r ⊗ s′ ∈Si ,t′ ∈Ti Enc((ABi )s′ t′ )12:Li ← Enc(xis + ai )|Enc(xit + ai )で 10 回異なるポリシグラフに対して同一のクエリを送信する

LinkageProtocol を実施し, 該当するプロトコルにかかる時間の平均を計測した. 各 LinkageProtocol において Query を呼び出す回数は 1 回である. また, Paillier 暗号の鍵長は 1024bit とした.

5. 2 結果と考察
c = 1 のときの Query White, および Query Black の実行時間

13: end for
14: LM は, {L1 , · · · , Lc } を Analyst へわたす.

Query Black のアルゴリズムを Algorithm 4 に記す. ここで, 0 は零行列, I は単位行列である. 3 行目から 6 行目の処理
では, クエリ履歴をあらわす隣接行列 Q の reachability matrix

R をもとめる. 頂点 s, t を連結する際にブラックリストが連結するか否かを確認するために 11 行目の処理を行う.
ここで, reachability matrix の生成を行う第 3 章の式 (1) は次のかたちに書き直すことができる.
図6

Query White, Query Black の実行時間 [sec]ト方式では LM の計算が複雑であり, データ登録者が意識してポリシを指定できない場合がある. そこで混合方式では, デー
タ登録者にとって確保したいデータは保持しつつ, Analyst にとって柔軟な分析が実現することを目指す. 二つ目は, ポリシに属性を付与する方式である. データ登録者, また分析者の属性
ごとにポリシを指定することで, データ分析者がその用途に応じて適切なレコードリンケージを行えることを目指す. この方式の実現のために, 属性ベース暗号を用いる予定である. 属性
ベース暗号とは, 複数の公開鍵, 秘密鍵を設け, 各鍵が一対一で対応している公開鍵暗号方式である. 例としては, 医療調査者
や予備校の関係者など, 分析が制限されている sensitive なデー
図 7 サイズ d × d の行列の暗号化に要する時間 [sec]タに対して分析を行えるような者のみが, 適切なデータベース
に対してアクセスができるようなことを可能にする.

の計測結果を図 6 に示す. Query White における計算回数が d に依存しない一方, Query Black では, サイズ d × d の reachability

謝辞matrix を生成するため, d が増加するごとに指数関数的に計算本研究は, JST CREST「ビッグデータ統合利活用のための時間が増加する. c 人の DC についてレコードリンケージを行

次世代基盤技術の創出・体系化」領域におけるプロジェクトおう場合, Query White, Query Black の所要時間は, 図 6 に示し

よび科学研究費 24680015 の助成を受けました.

た各プロトコルの所要時間と DC の人数 c の積であらわせる.

LinkageProtocol White, LinkageProtocol Black の両プロトコルにおいて, サイズ d × d の行列を暗号化する処理がもとめられる. サイズ d × d の行列の暗号化に要する時間を図 7 に示す.

d = 5 の際は 1 sec 未満で, d = 50 の際は約 23 sec で行列の暗号化を行える. 図 7 より, 行列の暗号化の処理時間は d に応じて指数関数的に増大することがわかる. 行列の暗号化の処理はプロトコルの最初に実行するため, システム内の Database の個数が増加しない限り一回のみで済む. また DC 一人一人が行列の暗号化を行うため, プロトコル全体で行列の暗号化にかかる処理は図 7 に示す時間で完了すると考えてよい.

6. お わ り に
本論文では, データ登録者が任意のデータベース間のプライ
バシポリシを保持することで, データ登録者が望まないレコー
ドリンケージが実行できないような準同型暗号に基づいた暗号
プロトコルを, グラフで表現したポリシの方式に応じて二通り提案した. 一つ目の手法は連結許可のポリシを定めるホワイト
リスト方式であり, 隣接行列のポリシのマスクを行うことでポリシの改ざんを防ぐことを実現した. 二つ目の手法は連結拒否のポリシを定めるブラックリスト方式であり, グラフの隣接行列を用いた reachability test を実施することでポリシの秘匿を実現した. プライバシに対するデータ登録者の需要からブラッ
クリスト方式がより実用的である. 一方, ホワイトリスト方式
はブラックリスト方式に比べ計算量が小さいため高速なレコー
ドリンケージを行える. また, 実行時間の観点から二手法のプロトコルを提案した. また, クエリ単位の実行時間についても現実的に実行可能であることを示した.
本研究の主な発展的課題を二点述べる. 一つ目はホワイトリ
ストとブラックリストの混合方式の実現である. ホワイトリス
ト方式では分析者が柔軟な分析をできない一方, ブラックリス

文

献[1] Alexandros Karakasidis and Vassilios S. Verykios, ”Secure
blocking+ secure matching= secure record linkage”, Journalof Computing Science and Engineering, pp. 223–235, 2011.
[2] Alexandros Karakasidis and Vassilios S. Verykios, ”Privacy
preserving record linkage using phonetic codes”, In: Informatics, 2009. BCI’09. Fourth Balkan Conference in IEEE,
pp. 101–106, 2009.
[3] Rainer Schnell, Tobias Bachteler, et al, ”Privacy-preserving
record linkage using Bloom filters”, BMC medical informatics and decision making, 2009.
[4] Mehmet Kuzu, et al, ”Eﬃcient privacy-aware record integration”, In: Proceedings of the 16th International Conference on Extending Database Technology. pp. 167–178.
ACM, 2013.
[5] Hye-Cheng Kum and Ashok Krishnamurthy, et al, ”Privacy
preserving interactive record linkage (PPIRL)”, Journal of
American Medical Informatics Association, 2013.
[6] Nigel P Smart and Frederik Vercauteren, ”Fully homomorphic SIMD operations.” Designs, codes and cryptography,
71(1) pp.57–81, 2014.
[7] Jean-Paul Tremblay and G. A. Cheston, ”Data Strucutres
oftware Development in an Object-Oriented Environment.
Java Edition”, Prentice Hall, 2003.
[8] Pascal Paillier, ”Public-key cryptosystems based on composite degree residuosity classes”, In Proceedings of the
17th international conference on Theory and application of
cryptographic techniques, EUROCRYPT’99, pp. 223–238,
Berlin, Heidelberg, Springer-Verlag, 1999.