DEIM Forum 2013 F8-2

分散データベースにおける共有データの k -匿名化フレームワーク
櫻田潤一†

上土井陽子††

若林 真一††† 広島市立大学大学院情報科学研究科 〒 731-3194 広島市安佐南区大塚東 3-4-1†† 広島市立大学大学院情報科学研究科 〒 731-3194 広島市安佐南区大塚東 3-4-1
E-mail: †sakurada@lcs.info.hiroshima-cu.ac.jp, ††{yoko,wakaba}@hiroshima-cu.ac.jp
あらまし

異なる機関に保存された分散データベースを結合し，解析することで有益な情報を得ることができる．しかし，データ保有者のプライバシ保護を行うことができないのであればデータの共有・結合は実現されない．プライバシ保護の方法として k-匿名化が用いられている．従来研究では同じ ID の集合間での k-匿名化を満たす結合を行うためのフレームワークが提案されている．本稿では，異なる ID 要素集合の共通集合のみを安全に匿名化するためのフレームワークを提案する．
キーワード分散データベース，k-匿名化

Jun’ichi SAKURADA† , Yoko KAMIDOI†† , and Shin’ichi WAKABAYASHI††† Graduate School of Information Sciences, Hiroshima City University
3-4-1 Otuka-higashi, Asaminami-ku, Hiroshima, 731-3194, Japan†† Graduate School of Information Sciences, Hiroshima City University
3-4-1 Otuka-higashi, Asaminami-ku, Hiroshima, 731-3194, Japan
E-mail: †sakurada@lcs.info.hiroshima-cu.ac.jp, ††{yoko,wakaba}@hiroshima-cu.ac.jp
Key words distributed databases，k-anonimization

1. は じ め に
近年，様々な機関で蓄積された情報を共有，統合しデータマ
イニングに利用することの有効性が検討され始めた．データマされている．従来研究では完全なデータセットが２つのサイト上に別々に保存されており，共通の識別子を用いた結合が可能であるとの仮定で，双方のプライバシ情報を保護しながら協調して k-匿名性を満たすフレームワークが提案されている．

イニングは大規模なデータベースを解析することで有益な情報

本研究で扱うデータセットは表 1 のように表現されているとを抽出する技術であるが，データ保有者のプライバシ保護を行する．各行は個人情報を表し，各列は属性値を表すとする．属

うことができないのであればデータの共有は実現されない．プ性 ID は各行異なる値をもつが個人を特定できない非識別子とライバシ保護の方法としてデータセット内に同一データが k 個する．属性勤務地，年齢，給与は準識別子と呼ばれる属性であ以上存在するまで一般化する k-匿名化が用いられている．本研り，組み合わせることにより個人を特定できる情報を含んでい究では複数の機関で分散管理されているデータベースをプライる可能性がある．以降では表での各個人の情報に対応する行をバシを保護した上で統合する分散 k-匿名化問題について考察

レコードと呼ぶ．つまり，本研究で対象とするデータセットはする．

従来研究とは異なり統合したときに部分的に属性値を欠いてい本研究で考察する分散 k-匿名化問題は，複数の機関が別々にる行が存在してもよい．

保存している部分データを，他の機関に最終結果として出力す

本稿では，2 つの機関 P1 , P2 がそれぞれ保持するデータセッ

るデータより読み取れる情報以外の情報を漏らすことなく，k-ト T1 , T2 双方において，識別子を表現する属性が存在するとす

匿名性を満たす１つのデータに統合して出力する問題である．

る．このとき，データセット T1 , T2 において共に有する識別子

分散 k-匿名化問題に対する従来研究 [1] では各サイトで局所的をもつタプルを結合し，かつ，k-匿名化する共有データ k-匿名に k-匿名部分データを作成し，２つのサイトの局所的な k-匿化問題を考える．そのとき，分散 k-匿名化問題に対する従来分

名データの結合後にも k-匿名性を満たすデータとなるかを判定

散フレームワークを拡張し，より広い分散データベースのクラするため，２つの集合間の積集合の要素数に関する判定問題をスを対象とする共有データ k-匿名化問題に対する分散フレーム

機密性を保ちながら解く k-匿名化の分散フレームワークが提案ワークを提案する．

表 1 対象とするデータセットの例

ID 勤務地 年齢

ID

給与

1千葉

34

1370,000

2

東京

33

2410,000

3

岡山

46

3390,000

4

広島

26

4250,000

5

山口

49

5410,000

6

鳥取

26

6220,000

7

埼玉

34

7370,000

8

広島

48

8430,000

9210,000

9

広島

2610

岡山

4511

大阪

32

12

奈良

34

13

京都

30
14 310,000

図 2 従来分散 k-匿名化フレームワーク

15 350,000
16 320,000

2. 準備

2. 1 k-匿 名 化
本稿では，データセットはレコードの集合とし，各レコードは複数の属性の値の組合せで表現されているとする．k-匿名化とは元のデータセットを k-匿名性を満たすデータセットに変換することでプライバシ保護を行うものである．ここで k-匿名性を満たすとは，データセット内の各レコードと同じ値の組合せ

図3

年齢の値一般化階層

図4

給与の値一般化階層を持つレコードが少なくとも (k − 1) 個存在することとする．
データを匿名化するため，特定の値を一般化する．一般化の規則は入力として各属性に対して値一般化階層の形式で与えられている．
例えば図 1 のように値一般化階層が設定されている場合，福岡，大分出身を九州出身と一般化することができる．

可となったデータセットの属性｛給与｝に関してさらに値を一般化する．それにより，結合後も 3-匿名性を持つデータセット
表 2 を作成することができる．また，分散管理されているデータの局所的 k-匿名化は文献 [4] に記されている Datafly で行う．
図 1 勤務地の値一般化階層

2. 2 従来分散 k-匿名化フレームワーク
従来研究における分散 k-匿名化フレームワークを図 2 に示す．
例を用いて従来分散 k-匿名化フレームワークについて説明する．表 1 の２つのデータセットにおいて ID[1-9] を含むデータセットを 3-匿名性を保つよう結合する場合を考察する．まず属性｛勤務地，年齢｝を持つデータセットは図 1, 図 3 の値一般
化階層より 1 段階一般化する．また属性｛給与｝を持つデータセットも図 4 から値を一般化する．しかし，給与を 1 段階あげただけでは結合後に 3-匿名性を保てない．よって判定で結合不局所的な匿名化後の同じ値のレコードの集合において積集合の要素数を調べることで結合後に匿名性を満たすかどうか判定する．
例えば，勤務地が中国地方，年齢が 45-49 となる ID の集合
を D1 = {3, 5, 8} とし，給与が 360-450 となる ID の集合を

D2 = {1, 2, 3, 5, 7, 8} としたとき，|D1 ∩ D2 | = 3 ≧ k を判定
する．

2. 3 要素数判定問題
ここでは別々に管理されている k-匿名化データセットの結合後も k-匿名性を満たすか判定するときに用いる要素数判定問題

を定義する．ここで整数集合 {1, ..., m} の部分集合 D1 , D2 は化データを結合可能かどうか判定することができる．ここで，２つの機関 P1 , P2 それぞれがもつ情報とする．m は２つの集従来フレームワークが対象とする分散 k-匿名化問題では識別合の要素が存在する値域の最大値とする．

子順に並べた k-匿名化データを結合することでそのまま k-匿名化結合データを得ることができる．一方，本研究で対象とす[要素数判定問題] 整数集合 {1, ..., m} の部分集合 D1 , D2 において，|D1 ∩ D2 | ≧ k を満たすか，否か．

⋄る共有 k-匿名化問題では，識別子順に並べた k-匿名化データを互いに公開することは相手に自分が保持している，または，2. 4 結合可能判定

保持していないデータの識別子を明かすことになってしまうの結合可能判定を行う回数は秘匿でないならば最低 |G1 | × |G2 |で，安全ではない．よって，新たに結合データを作成するため回の要素数判定を行えば結合可能と判定可能である．このとき，のフェーズを必要とする．従来フレームワークに新しい秘匿要

要素数判定は |D1 ∩ D2 | = 0 も true である．従来分散 k-匿名

素数判定と結合データ作成フェーズを組み込んだ提案フレーム化フレームワークにおいて秘匿要素数判定の入力に要素 i を含ワークを図 5 に示す．

む集合を入力としている．これは秘匿要素数判定において互いの |D1 |, |D2 | の情報を相手に漏らさないためである．このため，従来分散 k-匿名化フレームワークにおいて最低 O(m) 回の秘匿要素数判定が必要となる．

3. 提案分散共有 k-匿名化フレームワーク
本稿では，2 つの機関 P1 , P2 がそれぞれ保持するデータセッ
ト T1 , T2 双方において，識別子を表現する属性が存在するとする．このとき，データセット T1 , T2 において共に有する識別子をもつタプルを結合し，かつ，k-匿名化する共有データ k-匿名化問題を考える．２つの機関に保存されたデータセットは表 1のように各 ID に該当するデータを保持する場合と保持しない

図5

提案分散共有 k-匿名化フレームワーク

場合があるものとし，それぞれの機関を P1 , P2 とし，それぞれのデータセットを T1 , T2 とし，全体のデータセットの識別子の最大値を m とする．このとき，各機関が局所的に k-匿名化した k-匿名化データを表現する各データセットのグループ分けを表現するための用語を以下に定義する．ここで i = 1, 2 とする．

•データセット Ti の分割 Gi•

分割 Gi 内の集合数 ni = |Gi |•分割 Gi の要素 Dij (1 <=j<= ni )．

つまり，Gi = {Di1 , Di2 , ..., Di i } と表現できる．
n

従来研究において表 1 のように ID[10-16] のように一方のみが固有の ID を含む場合，秘匿要素数判定の入力として要素 iを含む集合を作成できない．また，空集合を入力として要素数判定を行うと false の判定のみが出力されてしまう．そこで本研

図 6 結合データ作成プロトコル

究では秘匿要素数判定において |D1 ∩ D2 | = 0，|D1 ∩ D2 | ≧ kのどちらかを満たすか否かを判定するものとする．つまり，また，結合データ作成のフェーズのプロトコルの概要を図 60 < |D1 ∩ D2 | < k を判定すればよい．この変形判定問題を要に示す．結合可能判定後，G1 ，G2 内に空集合 ∅ を追加する．そ

素数閉区間判定問題とする．このとき，要素数閉区間判定が全の後，G1 ，G2 内の集合を入力に |D1 ∩ D2 | = 0 を判定する秘て f alse だったときに，２つの匿名化データを結合可能と判定

匿要素数 0 判定を行う．結合後に要素数が 0 でない場合，そのするようにフレームワークを変更する．

集合での結合後の要素数を判定し要素数分のデータセットを結[要 素 数 閉 区 間 判 定 問 題] 整 数 集 合 {1, ..., m} の 部 分 集 合
D1 , D2 において，0 < |D1 ∩ D2 | < k を満たすか，否か．
⋄合する．このとき，属性 ID はデータに含まない．結合データ作成の具体例を以下に示す．

3. 1 両者の実際のやりとり
例えば，ID の値が 11 を含む集合を D1 = {11, 12, 13}, D2 =∅ としたとき，|D1 ∩ D2 | = 0 なので f alse と判定する．
従来フレームワークの秘匿要素数判定を秘匿要素数閉区間判

結合可能データセット T1 , T2 の分割 G1 = {{1, 2, 7}, {3, 5, 8,10}, {4, 6, 9}},G2 = {{1, 2, 3, 5, 7, 8}, {4, 6, 9}, {14, 15, 16}} を入力とする．

定に変更することで一方のみしか属性値を保持していない識別[フレームワーク]

子を結合データの対象外として両機関が提出した局所的 k-匿名

・両者が要素 i をもつ場合

|{1, 2, 7} ∩ {1, 2, 3, 5, 7, 8}| ≧ 3(1)|{3, 5, 8, 10} ∩ {1, 2, 3, 5, 7, 8}| ≧ 3(2)|{4, 6, 9} ∩ {4, 6, 9}| ≧ 3(3)

表 3 結合後 3-匿名データセット
勤務地

年齢

給与（千円）

関東

30-34

360-450関東

30-34

360-450関東

30-34

360-450

・一方または両者が要素 i をもたない場合

中国

25-29

360-450|{11, 12, 13} ∩ ∅| = 0中国25-29360-450|∅ ∩ {14, 15, 16}| = 0

中国

25-29

360-450以上の判定で結合可能と判定を得る．

中国

45-49

210-250

中国

45-49210-250

中国

45-49

210-250[プロトコル]・要素数 0 判定が true の場合
一方または両者が要素 i を含まない集合を入力としたときである．

（文献 [1] の SSI プロトコル，または，文献 [2] のプロトコル）|{1, 2, 7} ∩ {4, 6, 9}| = 0を拡張することで実現できる．したがって，本研究では従来フ|{1, 2, 7} ∩ {14, 15, 16}| = 0

レームワークと大きく異なる結合データ作成フェーズの安全性|{1, 2, 7} ∩ ∅| = 0

に関して先ず考察する．
結合データ作成フェーズの安全性の検証では，結合可能と判|∅ ∩ ∅| = 0...etc
・要素数 0 判定が false の場合定された結合データセットを入力としてプロトコルを実行する

両者が要素 i を含む集合を入力としたとき，つまり式 (1),(2),(3)間に最終的に出力される結合データから得られる情報以外の相のときである．このとき，それぞれ要素数を判定し P1 側では手機関の情報が漏えいしているか否かを判定する．

属性 { 勤務地，年齢 } = { 関東，30 − 34} のデータ，P2 側では上記のような安全性の検証で用いられる方法の 1 つとして，属性 { 給与 } = {360 − 450} のデータを 3 つ結合する．その後，シミュレーションがある [3]．本研究では提案するフレームワー{ 勤務地，年齢 } = { 中国，25 − 29}，{ 給与 } = {360 − 450}

クにおいてそれぞれの機関で実際のやりとりをフレームワークを 3 つ結合する．最後に { 勤務地，年齢 } = { 中国，45 − 49}，を用いて分散データベースを結合後，出力される k-匿名化デー{ 給与 } = {210 − 250} を 3 つ結合し表 3 を得る．

タセットを用いてシミュレート可能であるか否かを検証する．
本稿では，まず，シミュレーションに用いる擬似データ作成方

表 2 結合可能データセット法を提案する．次に，結合可能判定後に表 2 を機関 P1 ，P2 はID 勤務地

年齢ID 給与（千円）

1

関東

30-34

1360-450

2

関東

30-34

2360-450

3

中国

45-49

3360-450

4. 1 擬似データの作成

4

中国

25-29

4210-250

P1 , P2 がそれぞれシミュレーションで使用する擬似データを

5

中国

45-49

5360-450

結合後作成される匿名データセットと自分の保有する結合可能

6

中国

25-29

6210-250

データセットから作成する方法を提案する．その方法を以下に

7

関東

30-34

7360-450

示す．

8

中国

45-49

8360-450

9

中国

25-29

9210-250(1) 自分がもっている結合可能 k-匿名化データセット Tinitial を10

中国

45-4911関西

30-34する．ここで各 Di は同じデータ値を持っているレコードの識それぞれもつものと提案擬似データ作成方法を用いて作成した擬似データを入力とした．シミュレーションの具体例を示す．

値の種類ごとに分割し，それを Ginitial = {D1 , D2 , ..., Dn } と

12

関西

30-34

別子の集合とする．また，結合後のデータセット Tf inal を値の13

関西

30-34種類ごとに分割し，それを Gf inal = {A1 , A2 , ..., An′ } とする．
14 310-350

ここで各 Ai は Tf inal で同じデータ値を持っているレコードの15 310-350集合とする．また，Tinitial に含まれない識別子の集合を N ID

16 310-350とし，作成中の擬似データを Gsimulate とし，初期値を ∅ とする．

4. 結合データ作成プロトコルの安全性(2)Gf inal に属するレコードの集合 A を選択する．

本節では提案分散 k-匿名化フレームワークの安全性についタセット Tf inal において同じ値の組合せをもつレコードの識別て考察する．提案フレームワーク全体としての安全性を示すに子の集合で，かつ，Ginitial に含まれる識別子の集合を見つけ，(3) レコードの集合 A と自分の保持している属性に関して，デーは，結合可能判定までの安全性の検証と結合データ作成フェー

これを D とする．

ズの安全性を検証する必要がある．結合可能判定までは，秘匿(4) 集合 A の要素数 ∥A∥ を p とし，集合 D の要素数 ∥D∥ を qとする（p >= q ）．p = q ならばステップ (5.a) へ．p > q ならば要素数閉区間判定を用いる以外，従来フレームワークとほぼ等しい．秘匿要素数閉区間判定は秘匿要素数判定のプロトコル

ステップ (5.b) へ．

(4),(5),(6) のときである．このとき，それぞれの要素数を判定(5.a)(p >= q の場合)
相手機関は D 内に含まれる全ての識別子のデータを持っていしたとき式 (4) から式 (1) を，(5) から式 (2) を，式 (6) から式る．よって，Gsimulate に D をそのまま追加する．Gsimulate ←Gsimulate ∪ {D}．

(3) をシミュレートし表 3 を得ることが可能である．
4. 3 P2 のシミュレーション
結合後のデータセット表 3 と自身のデータセット T2 からシ

その後，Ginitial から D を削除する．Ginitial ← Ginitial −{D}．

ミュレーションに使用する G′1 を作成した．ここで作成した G′1 は(5.b)(p > q の場合)

G′1 = {{1, 2, 3, 5, 7, 8, d1 , ..., dn }, {4, 6, 9, d1 , ..., dn }, {d1 , ..., dn }}相手機関は D に含まれる識別子のデータと同じ値の組合せのである．
（ここで，{di ∈ T2 とする）．このとき，3.1 節の実際データのうちの q 個を持っている．D からランダムに q 個の識の機関 P1 とのやりとりを擬似データを使って模倣できること別子を選び，識別子の集合 Q を作成し，Gsimulate に Q を追加を示す．

する．Gsimulate ← Gsimulate ∪ {Q}．

[フレームワーク]′

その後，Ginitial に含まれる集合 D を D = D − Q に更新す・お互いが要素 i をもつ場合

る．Ginitial ←（Ginitial − {D}）∪ {D }．

G′1 , G2 から要素 i を含む D1 , D2 を入力として要素数判定を(6)Gf inal から集合 A を削除する．Gf inal ← Gf inal − {A}．

行う．

′

(7) もし，Gf inal が空集合でないならステップ (2) へ．
(8)Gsimulate の各要素 D に対応する相手機関のもつ属性の値組合せを結合後のデータセットより割り当てる．このとき，同じ値組合せに対応する複数の要素が存在するならそれらを Gsimulateから削除し，代わりに和集合を挿入する．

(9)Gsimulate の各要素 D に N ID に含まれる識別子をランダムに追加，または，新しい集合を挿入し，擬似データとしてGsimulate を出力する．

|{1, 2, 3, 5, 7, 8} ∩ {1, 2, 3, 5, 7, 8, d1 , ..., dn }| ≧ 3(7)|{4, 6, 9} ∩ {4, 6, 9, d1 , ...dn }| ≧ 3(8)・一方または両者が要素 i をもたない場合空集合が入力となるので |D1 ∩ D2 | = 0 の判定で結合可能と判定を得る．

[プロトコル]・要素数 0 判定が true の場合

4. 2 P1 のシミュレーション
結 合 後 の デ ー タ セット 表 3 と 自 身 の デ ー タ セット T1 から シ ミュレ ー ション に 使 用 す る G′2 を 4.1 節 で 示 し た 擬 似データ作成方法を用いて作成した．ここで作成した G′2 はG′2 = {{1, 2, 7, a1 , a2 , a3 , d1 , ..., dn }, {4, 6, 9, d1 , ...dn },{d1 , ..., dn }} である．
（ここで，ai ∈ {3, 5, 8, 10},di ∈ T1 とする）．このとき，3.1 節の実際の機関 P2 とのやりとりを擬似データを使って模倣できることを示す．

G2 の入力 D2t のどの要素も含まない D1′s を入力とする．
|{1, 2, 3, 5, 7, 8} ∩ {4, 6, 9, d1 , ...dn }| = 0|{1, 2, 3, 5, 7, 8} ∩ {d1 , ..., dn }| = 0|{1, 2, 3, 5, 7, 8} ∩ ∅| = 0...etc
・要素数 0 判定が false の場合

G2 の入力 D2t の要素を含む D1′s を入力とする．つまり，式(7),(8) のときである．このとき，それぞれの要素数を判定した
とき式 (7) から式 (1),(2) を，式 (8) から式 (3) をシミュレート[フレームワーク]

し表 3 を得ることが可能である．

・お互いが要素 i をもつ場合

G1 , G′2 から要素 i を含む D1 , D2 を入力として要素数判定を行う．

5. ま と め
本稿では，異なる ID 要素集合の共通集合のみを安全に匿名化するためのフレームワークを提案した．今後の課題として|{1, 2, 7} ∩ {1, 2, 7, a1 , a2 , a3 , d1 , ..., dn }| ≧ 3(4)|{3, 5, 8, 10} ∩ {1, 2, 7, a1 , a2 , a3 , d1 , ..., dn }| ≧ 3(5)

全性を検証することが挙げられる．また，提案結合データ作成|{4, 6, 9} ∩ {4, 6, 9, d1 , ...dn }| ≧ 3(6)プロトコルでは G1 , G2 内の集合数をかく乱するために空集合は，作成擬似データを用いたシミュレーションを一般化し，安・一方または両者が要素 i をもたない場合空集合が入力となるので |D1 ∩ D2 | = 0 の判定で結合可能と判定を得る．

[プロトコル]・要素数 0 判定が true の場合

G1 の入力 D1s のどの要素も含まない D2′t を入力とする．
|{1, 2, 7} ∩ {4, 6, 9, d1 , ...dn }| = 0|{1, 2, 7} ∩ {d1 , ..., dn }| = 0|{1, 2, 7} ∩ ∅| = 0...etc
・要素数 0 判定が false の場合

G1 の入力 D1s の要素を含む D2′t を入力とする．つまり，式を ⌊m/k⌋ 個追加している．このため，結合データを作成するまでの秘匿要素数０判定の回数が増大している．よって，追加する空集合の適切な設定方法の導出もさらなる課題である．
文

献[1] W. Jiang and C. Clifton: A secure distributed framework
for achieving k-anonymity, The VLDB Journal, Vol.15,
pp.316-333 (2006).
[2] 櫻田潤一, 上土井陽子, 若林真一: 分散データベースにおける安全で効率的なプロトコル, DEIM2012 論文集, C5-5 (2012).
[3] B. Schneier: Applied Cryptography, Second Edition, John
Wiley & Sons Inc.(1996).
[4] L. Sweeny; ”k-anonymity: a model for protecting privacy,” International Journal of Uncertainty, Fuzziness andKnowledge-based Systems, Vol.10, No.5, pp.571-588 (2002).