DEIM Forum 2014 E5-3

動的データテーブルの連続的匿名化の安全性について
柚木塁†

上土井陽子††

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

本研究では挿入や削除により時間の経過に従って変化する動的データテーブルの連続した匿名化における安全性について考察する．従来知られている静的データテーブルに対する匿名化手法を用いて動的データテーブルを匿名化した場合，複数の匿名化テーブルの情報を統合することで個人を特定できる可能性が指摘されている．本研究では動的データテーブルの連続した匿名化テーブルの列が匿名性および多様性を維持するために満たすべき性質を明らかにする．
キーワード

動的データテーブル，挿入，削除，m-不変性
くつかの基本的な概念を説明する．

1. は じ め に
プライバシー保護データ公開では主に一度だけ公開する静的［定義 1］（QI グループ/分割） 元のデータの表 T (j) で、QI

データテーブルを対象としてきた．近年，挿入や削除が行われグループはタプルの部分集合である．表 T (j) の分割は互いに素る動的データテーブルの連続的匿名化が考察され始めた．しかな交わりのない複数の QI グループタプルからなっていて，そし，動的データテーブルは挿入や削除を行うことが可能となっれらの集合和は表 T (j) となる．各 QI グループは特定の ID をたのだが，静的データテーブル向けのプライバシー保護手法でもつ．t ∈T (j) を満たす各タプル t で，t.QI(j) は t を含む QI

匿名化し再公開を行うとプライバシーが保護されないことがグループを示す．t.QI(j) のことを表 T (j) での t のホスティン

あった．そのため動的データテーブルの安全性は再公開では不ググループと呼ぶ．

確かなものとなっていた．従来研究 [1] では再公開を行っても時刻 j で公開される表 T ∗ (j) を以下に定義する．例として

プライバシーが保護できる性質が導出されている．本研究では

表 1 の元データ表と表 2 の一般化表を用いて，定義を詳細に説

従来研究より匿名化に伴う情報損失を低減することを目標とし明する．

て，動的データテーブルの連続的匿名化の新しい安全性を提案［定義 2］（偽造された一般化） 表 T (j) の匿名化された表であする．

る表 T ∗ (j) は表 T (j) の分割に基づいて計算される．そして表2. 準

T ∗ (j) は以下の性質を持っている．

備（ 1 ） 表 T ∗ (j) は”Group-ID”と名付けられた列 Ag を含み，Aid を除く表 T (j) のすべての属性を含む (表 2 の場合，年齢と本節では本研究で必要となる基本的な定義を示す．
公開者によって保管されている元のデータテーブルを T とする．

ジップコードと病名が含まれる)．

表 T の中の列を (i)T の主要なキーとなる識別子属性 A (今回（ 2 ） 同じグループ IDAg をもつ表 T (j) のすべてのタプル

qiの場合，名前)，(ii)d 個の準識別子属性 Aqi
1 ,...,Ad (今回の場合，sはすべて同じ QI 属性値を持つ．これらのタプルは表 T ∗ (j) のid

年齢，ジップコード)，(iii) 機密属性 A (今回の場合，病名) で

QI グループを形成し，ID はグループ内の Ag の値に等しい．

分類する．d 個の準識別子属性は数値属性か分類別属性のどち（ 3 ） T (j) の各タプル t∈T (j) は表 T ∗ (j) に一般化されたタs

らかであるが，機密属性 A は分類属性とする．表 T の行であプル t∗ を持つ．ここで t∗ は以下を満たす．

る各タプル t に対して、t[A] はタプル t の属性 A の値を示す．

•

t∗ [As ]=t[As ]表 T は任意の順序で実行される挿入や削除によって更新さ•

グループ t∗ [Ag ] は表 T ∗ (j) の t∗ のホスティンググルー

れる．公開者はプライバシーを侵害することなく，挿入や削除を行うことが出来き，いつでも T の匿名化された表を公開する

プの ID である．

•

qi
値 t∗ [Aqii ] は，値 t[Ai ] を含む範囲である．(t=(表 1

かもしれない．そこで，j 番目の公開のタイムスタンプを示すのボブのタプル),t∗ =(表 2 のボブのタプル),t∗ [As ]=”消化不ために整数 j を使う．

良”,t[As ]=”消化不良”,t[Ag ]=1,

時刻 j での T の表を T (j) とする．表 T (j) を匿名化した表qit∗c [Aqi
1 ]=age[21,22],t[A1 ]=age21)．

を T (j) とする．表 R(j) を表 T (j) についての統計のための（ 4 ） 表 T (j) の QI グループ QI に対して，表 T ∗ (j) は任意

補助の表とする．公開者は表 T ∗ (j) と補助表 R(j) をペアで公の数の偽造されたタプル t∗c を含む場合がある．ここで値 t∗c [As ]開する．特に，匿名化は後で述べる偽造された一般化を適用しは機密属性 As の領域の値になる．グループ IDt∗c [Ag ] は QI のて達成される可能性がある．この概念 [1] を定義する前に，いID に等しい．t∗c [Aqii ] は値の範囲である．

∗∗

t∈T(j) に対して，t.QI ∗ (j) を t の一般化されたホスティング∗

表 3 2 回目の元データ

∗

名前

年齢

コード

病気

ボブ

21

12k

消化不良

デイビット

23

25k

胃炎

エミリー

25

21k

風邪

ジェーン

37

33k

消化不良

グループとして示し，t.QI (j)=t .QI(j) とする．
明らかに偽造を含む一般化は偽造がない従来の一般化の方法を特別な場合として含んでいる．次の定義は補助の表 R(j)が表 T ∗ (j) と伴に公開されることを明らかにする．
表 1 1 回目の元データ
名前

年齢

コード

病気

ボブ

21

12k

消化不良

アリス

22

14k

気管支炎

アンディ

24

18k

風邪

デイビット

23

25k

胃炎

ガーリー

41

20k

風邪

ヘレン

36

27k

胃炎

ジェーン

37

33k

消化不良

ケン

40

35k

リンダ

43

26k

胃炎

ガーリー

41

20k

風邪

メアリー

46

30k

胃炎

レイ

54

31k

消化不良

スティーブ

56

34k

胃炎

トム

60

44k

胃炎

ベニス

65

36k

風邪

表 4 表 3 の一般化テーブル
年齢

コード

病気

風邪

G.ID

[21,23] [12k,25k] 消化不良

リンダ

43

26k

胃炎

1

ポール

52

33k

消化不良

1

[21,23] [12k,25k]

胃炎

スティーブ

56

34k

胃炎

2

[25,43] [21k,33k]

風邪2[25,43] [21k,33k] 消化不良

2[25,43] [21k,33k]

胃炎

表 2 表 1 の一般化テーブル

3[41,46] [20k,30k]

風邪1[21,22] [12k,14k] 消化不良

3

[41,46] [20k,30k]

胃炎

1[21,22] [12k,14k] 気管支炎

4[54,56] [31k,34k] 消化不良

2

[23,24] [18k,25k]

風邪

4[54,56] [31k,34k]

胃炎

2[23,24] [18k,25k]

胃炎

5[60,65] [36k,44k]

胃炎

3[36,41] [20k,27k]

風邪

5[60,65] [36k,44k]

風邪3[36,41] [20k,27k]

胃炎

4[37,43] [26k,35k] 消化不良

4[37,43] [26k,35k]

風邪

名前

G.ID

4

[37,43] [26k,35k]

胃炎

ボブ

1

[21,23] [12k,14k] 消化不良

5[52,56] [33k,34k] 消化不良

G.ID

5

年齢

コード

[52,56] [33k,34k]

病気

表5

胃炎

動的データに対する一般化テーブル
年齢

コード

病気

c1

1

[21,23] [12k,14k] 気管支炎

デイビット

2

[23,25] [21k,25k]

胃炎

エミリー

2

[23,25] [21k,25k]

風邪

ジェーン

3

[37,43] [26k,33k] 消化不良

［定義 3］（補助の表） 補助の表 R(j) は二つの列”Group-ID”と”Count”を持つ．表 T ∗ (j) の中で偽造タプルを少なくとも一c2

3[37,43] [26k,33k]

風邪

リンダ

3

[37,43] [26k,33k]

胃炎

つ含む QI グループ QI ∗ に対して，補助の表 R(j) には列 [g, c]

ガーリー

4

[41,46] [20k,30k]

風邪

∗

メアリー

4

[41,46] [20k,30k]

胃炎

∗

レイ

5

[54,56] [31k,34k] 消化不良

スティーブ

5

[54,56] [31k,34k]

胃炎

トム

6

[60,65] [36k,44k]

胃炎

ベニス

6

[60,65] [36k,44k]

風邪∗がある．g はグループ QI の ID であり，c はグループ QI の偽造されたタプルの個数である．偽造されたタプルが表 T (j)に存在しないなら，補助の表 R(j) は空である．
例 1. 表 T (j)(表 3)，表 T ∗ (j)(表 5)，表 R(j)(表 6) によって定義 2，3 を説明する．表 T (j) のタプル ⟨ ボブ,21,12k, 消化不良

⟩ を t として考える．ホスティンググループ t.QI(j) は表 T (j)表 6 偽造テーブル∗

G.ID 個数の最初の二つの行となる．表 T (j) でタプル t の一般化された
タプルは ⟨1,[21,22],[12k,14k], 消化不良 ⟩ である．t の一般化されたホスティンググループ t.QI ∗ (j) は表 T ∗ (j) で二つの行で

1

1

3

1

ある Group-ID=1 であるタプルから成る．特に，t.QI ∗ (j) でのタプル c1 は偽造され，T (j) には存在しない。ID=3 での QI［定義 4］（履歴の統合） 時刻 n>=1 で、統合表 U (n) はそれぞグループにももう一つ偽造された c2 がある．補助の表 R(j) はれの 1,2,...,n のタイムスタンプでの表 T のすべてのタプルを含

各 QI グループで偽造された個数を示す．

む表であり，以下のように形式的に記述される．：

U (n) =

n
∪
j=1

T (j)

(1)

t∈U (n) を満たす各タプル t はライフスパン [x, y] で関連づけU (2) のタプル ⟨ ボブ,21,12k, 消化不良 ⟩ に対して，対応する行

られる．ここで x は表 T に現れた始めの時刻 j を表し，y は表b∈B(n) は表 2 の最初のタプルである．b[Group-ID]=*は相手T に現れた最後の時刻 j を表す．

が t の一般化されたホスティンググループについて確信がない

統合表 U (n) は表 T と同じような表と見すことが出来る．もしことを意味する．

タプルが異なる j でいくつかの表 T (j) に現れるなら，統合表

表 5 の偽造された c1 を tc とする．行 b∈B(n) が表 2 の最後かU (n) では，重複させないようにする．例として表 7 に示す．以ら 2 番目のタプルに対応する．相手は bc [Group-ID]=1 を知っ

降，我々は統合表を用いて攻撃者の背景知識を定義する．

ている．なぜなら，この値は R(2) に明確に示されているからである．一般に偽造されたタプルは一般化以前に”特定の QI 値”

表7

統 合 表

を持たないので，QI 値は Ø である．すべての偽造タプルは一

名前

年齢

コード

病名

ボブ

21

12k

消化不良

アリス

22

14k

気管支炎

アンディ

24

18k

風邪

デイビット

23

25k

胃炎

表に対するプライバシー攻撃 (機密属性などを推測すること) を

ガーリー

41

20k

風邪

実行する間，一般に想定された相手のもつ最大の知識を表して

ヘレン

36

27k

胃炎

いる．現実に，相手の知識は知識テーブル B(n) に示されるよ

ジェーン

37

33k

消化不良

りもっと少ないだろう．例えば，知識テーブル B(n) は病院で

ケン

40

35k

風邪

リンダ

43

26k

胃炎

ポール

52

33k

消化不良

スティーブ

56

34k

胃炎

エミリー

25

21k

風邪

した攻撃から守ることによって，我々は実際に出くわすより不

メアリー

46

30k

胃炎

利な状況でのプライバシー保護を目的としている．

トム

60

44k

胃炎

補助の表 R(1),...,R(n) のすべての情報は知識テーブル B(n)

ベニス

65

36k

風邪

にあると考える．このとき，情報漏洩は以下のように定式化さつの表にしか使えない．例えば，bc [Lifespan] は tc が T ∗ (2) にあることを意味している．
もしグループ ID を取り除くなら，知識テーブル B(n) が公開の受診者の情報の連続的公開の場合，(1) すべての患者の名前と歳とジップコード，(2) 病院に滞在する正確な日付などをすべて含むことになる．言い換えると，定義 5 の背景知識を利用［定義 5］（背景知識） 時刻 n での相手の知識は以下とする．

•

利用される一般化の法則 (一般化の方法)•

知識テーブル B(n):列 Ag と名付けられた”グループ ID”

れる．
表 8 相手の背景知識テーブル B(2)と Al と名付けられた”ライフスパン”と機密情報を除く表 U (n)のすべての属性を持つ (今回の場合，名前と年齢とジップコード) 表であり，以下に内容を詳細に示す．

G.ID

名前

年齢

コード

スパン

∗

ボブ

21

12k

[1,2]

∗

アリス

22

14k

[1,1]

∗

アンディ

24

18k

[1,1]

– すべてのタプル t∈U(n) に対して，1<= i<=d の間のすべて

∗

デイビット

23

25k

[1,2]

qi
l
において b[Ag ]= ∗，b[Aid ]=t[Aid ]，b[Aqii ]=t[Ai ] であり，b[A ]

∗

ガーリー

41

20k

[1,2]

が t のライフスパンと等しいような行 b∈B(n) をもつ．

∗

ヘレン

36

27k

[1,1]

∗

ジェーン

37

33k

[1,2]

∗

ケン

40

35k

[1,1]

∗

リンダ

43

26k

[1,2]

∗

ポール

52

33k

[1,1]

∗

スティーブ

56

34k

[1,2]

∗

エミリー

25

21k

[2,2]

のすべてのタプル，(2) 統合表 U (n) で各タプルのライフスパ

∗

メアリー

46

30k

[2,2]

ン，(3) すべての偽造されたタプルの公開された細部を含んで

∗

トム

60

44k

[2,2]

いる．

∗

ベニス

65

36k

[2,2]

1

c1

∅

∅

[2,2]

3

c2

∅

∅

[2,2]

∗
– 1<
=j <
=n で 各 表 T (j) の 偽 造 さ れ た tc に 対 し て ，
qi
g
g
<<
bc [A ]=tc [A ]，bc [Ai ] が B(n)，bc [Aqii ]=0 すべての 1=i=dの間で bc [Al ]=[j, j] において偽造の識別子であるような行

bc ∈B(n) がある．
同じく，知識テーブル B(n) は (1) 列 As を除く統合表 U (n)∗例 2.n=2 で仮定することによって，表 T (1)(表 1)，表 T (1)(表2)，表 T (2)(表 3)，表 T ∗ 2(2)(表 5)，補助の表 R(2)(表 6) として定義 4 と 5 を説明する．

［定義 6］（プライバシー違反） もし表 T ∗ (1),...,T ∗ (n) と知識

重複を除いた後で，統合表 U (2)(表 7) は T (1) と T (2) のすべ

テーブル B(n) を利用して．相手が正確に任意のタプルの機密てのタプルを含む．表 T (1)，表 T (2) に存在するので，タプル

情報を見つけ出すことが出来るなら，プライバシー違反が起こ⟨ ボブ,21,12k, 消化不良 ⟩ のライフスパンは [1,2] である．一方る．

で，⟨ アリス,22,14k, 気管支炎 ⟩ のライフスパンは [1,1] である．

例えば，例 2 でもし相手がテーブル 1b,3a,4 からボブの病気がなぜなら，時刻 1 では挿入され，時刻 2 では削除されている

消化不良だと推測することができるならプライバシー違反であからである．表 8 は表 B(n) の一部を表している．例として，

る．

以下に再公開問題の再帰的な定義を示す．

（ 1 ） T ∗ (n) は m-ユニークである．

［定義 7］（再公開） 公開者が元のデータ表 T について n-1 回匿（ 2 ） T (n − 1)∩T (n) に含まれるタプル t に対して，一般化

名化した表を公開していると想定する．{T ∗ (1),R(1)}...,{T ∗ (n−されたホスティンググループである t.QI ∗ (n − 1) と t.QI ∗ (n)1),R(n − 1)} や {T ∗ (j),R(j)} は定義 2 と 3 で定義されているは同じシグネチャを持つ．

公開表とする．このとき，プライバシー保護再公開の目的はプ

補題 2 は再公開を行うため追加的なアプローチを取ることがライバシー違反を最小限にしながら，できるだけ多くの元デー

できることを示す．特に T ∗ (n) を準備するため，公開者は表タの情報を含む表のペア {T ∗ (n),R(n)} を作成することである．

T (n − 1) と T (n) と最後に公開された表 T ∗ (n − 1) を考えるだ

以降では，特別な場合を除き，公開表 T ∗ (1) と補助の表 R(1)けでよい．古い元データである表 T (1),...,T (n − 2) と同様に公を合わせて公開表 T ∗ (1) と呼ぶ．

開された表 T ∗ (1),...,T ∗ (n − 2) は保持する必要がない．

3. 従 来 手 法

3. 2 問 題 点

従来研究 [1] では，動的データテーブルの匿名化表の列が満

従来研究 [1] での m-不変性はプライバシーを保護することにたすことにより，連続的なプライバシー保護公開可能とする性関しては今のところ問題はない．しかし m-不変性を保つため質である m-不変性という概念が提案されている．以下で，m-に偽造タプルを挿入しなければならない等，情報損失が大きく不変性を考える上で必要な定義を示し，続いて m-不変性の概なるという問題がある．そこで情報損失を低減させるために本念を示す．

研究では新しい安全性の提案を行う．

3. 3 公開データ作成方法

3. 1 m-不変性［定義 8］（シグネチャ） 1 から n の間の任意の j に対する公従来研究 [1] では，m-不変性を満たす 1 回目の公開データ作

開表 T ∗ (j) における QI グループを QI ∗ とする．グループ QI ∗成時に考察する性質も定義されている．

のシグネチャは QI ∗ での機密情報の集合とする．

［定義 10］（m-エリジブル） 元のデータの表の中で最も多い

次に，従来研究 [1] で再公開でのプライバシー保護のため，公機密属性 As の要素数/元データのタプルの個数が 1/m 以下な開テーブルが満たすべき性質と提案された m-不変性について

ら，このデータ集合は m-エリジブルと呼ぶ．また元データが定義する．

m-エリジブルであるなら，m-不変性を満たす公開データを作［定義 9］（m-不変性） 一 般 化 さ れ た テ ー ブ ル T ∗ (j) が (1)成することが出来る．

∗

T (j) の各 QI グループが少なくとも m 個のタプルを含み，
かつ (2) QI グループ内のすべてのタプルが異なる機密情報をm-エリジブル性質に基づく公開データ作成アルゴリズムについ持つなら，T ∗ (j) は m-ユニークであると言う．このとき，公開

て述べる．

∗

∗

された表 T (1),...,T (n) の列が以下の条件を満たすなら m-不3. 4 1 回目の公開データ作成アルゴリズム (提案 1)変性であると言う：

元のデータを入力データとして，m-ユニークな公開データ∗（ 1 ） すべての表 T (j) は m-ユニークである．

を作成する．公開者によって保管されている元のデータの表を（ 2 ） ラ イ フ ス パ ン [x, y] で 任 意 の タ プ ル t に 対 し て ，T とする．また元データのタプルの総数を tupleN とする．表

t.QI ∗ (x),t.QI ∗ (x + 1),...,t.QI ∗ (y) は同じシグネチャを持つ．

T の中の列を識別子属性 Aid (今回の場合，名前)，d 個の準識

ここで t.QI ∗ (j) は時刻 j∈[x, y] での公開表 T ∗ (j) でのタプル tqi
別子属性 Aqi
1 ,...,Ad (今回の場合，年齢，ジップコード)，機密の一般化されたホスティンググループである．

属性 As (今回の場合，病名) で分類する．機密属性 As の中で，

m-ユニーク性は各機密情報がすべての QI グループの中で高々同じ機密属性 As は n 種類あると想定できるのでそれぞれの種

1 回だけ現れるべきであると要求する．明白に，m-ユニーク性

類の個数を数える．そして個数の多いものから順に並べる．こは m-多様性を意味する．しかし各 QI グループに m 種類の機のとき一番多いものから順に機密属性 As1 ,...,Asn (表 T の場合，

密属性が存在すればよい m-多様性の定義の場合，反対はそう

As1 =胃炎，As2 =消化不良，As3 =風邪，as4 =気管支炎) とする．

ではない．m-不変性の原理では，もしタプル t が数回にわたっ以下に公開データ作成アルゴリズムを示す．

て連続で公開されるなら，タプル t を含むすべてのホスティン［Step 1］ 最初に元のデータが m-エリジブルを満たすかどう

ググループは同じ機密情報を持たなければならない．

か確認する．その後に最も多い要素数個の QI グループが存在∗∗[ 補題 1] もし {T (1),...,T (n)} が m-不変性であるなら，そのとき risk(t)<=1/m となる．ここで risk とは，任意のタプル t のすると考えて |As1 | 個数分バケットを作成する (表 T(1) の場合，機密属性が特定される確率である．

したバケットに As1 のタプルを振り分ける．

As1 =胃炎の 4 つが最大なので 4 つバケットを作成する)．作成

それゆえ，公開者はプライバシー保護を達成するために十分な

次にまだ振り分けていないタプルの振り分けを行う．

値を単に m を定めることができる．

［Step 2］ 振り分ける前に m-エリジブルかどうか確認する．

[ 補題 2] もし {T ∗ (1),...,T ∗ (n-1)} が m-不変性を満たすなら，確認後，次に要素数の多いタプルの 1 つをバケットに振り分け

∗

∗

∗

そのとき {T (1),...,T (n − 1),T (n)} は以下の 2 つの条件を満る．次に残りの振り分けられていないタプルの要素数の多いもたすとき，かつその場合に限り，m-不変性を満たす：のを選択しておく．

すべての残りの要素数が 1 になるまで Step2 を繰り返す．

想定できるのでそれぞれの種類の個数を数える．そして個数の［Step 3］ 新しくバケットを作り残りのすべてのタプルを入多いものから順に並べる [2]．このとき一番多いものから順に機れる．

密属性 As1 ,...,Asn (表 T の場合，As1 =胃炎，As2 =消化不良，As3 =このアルゴリズムによって初期解ではあるが公開データを作成

風邪，as4 =気管支炎) とする．

できた．元データを表 9 として作成した公開データを表 10 とこのとき，以下の定理が成り立つことを新たに証明する．

する．しかし，このアルゴリズムでは情報損失について考慮し[定理] |As1 |<=⌊tupleN /m⌋ の時，⌊tupleN /m⌋ 個の m-ユニーていないので情報損失を改良するためにタプルの交換を行う必クなグループへの表 T の分割が存在する．

[証明] ⌊tupleN /m⌋ 個が最大バケット数であり，そのバケッ

要がある．
表 9 1 回目の元データ
名前

年齢

コード

病気

ボブ

22

15k

消化不良

アリス

22

14k

気管支炎

アンディ

24

18k

風邪

デイビット

23

25k

胃炎

ガーリー

40

20k

風邪

ヘレン

36

27k

胃炎

ジェーン

37

33k

消化不良

ケン

40

25k

風邪

リンダ

43

26k

胃炎

ポール

52

33k

消化不良

ト数を持ち，m-ユニークを満たす解が存在することを示す．バ

スティーブ

56

34k

胃炎

ケットとは，⌊tupleN /m⌋ 個のバケットを用意し，公開データ

図 2 (b)
図 1 (a)の QI グループの 1 つにあてはまる各タプルを振り分けたものである．

表 10 1 回目の公開データ (提案 1)
年齢

コード

病気

実際に，機密属性の要素数の多い順に 1 つずつバケットに振り

名前

G.ID

ボブ

1

[22,24] [15k,25k] 消化不良

デイビット

1

[22,24] [15k,25k]

胃炎の要素数が ⌊tupleN /m⌋ 以下であることがわかるから，同一バ

アンディ

2

[24,36] [18k,27k]

風邪

ケットに同じ機密属性を持つタプルが振り分けられることはな

胃炎

い (図 2(b) 参照)．したがって，バケット数 ⌊tupleN /m⌋ で m-

ヘレン

2

[24,36] [18k,27k]

ジェーン

3

[37,43] [26k,33k] 消化不良

リンダ3

[37,43] [26k,33k]

胃炎

ガーリー

4

[40,56] [20k,34k]

風邪

スティーブ

4

[40,56] [20k,34k]

胃炎

アリス

5

[22,52] [14k,33k] 気管支炎

ケン5[22,52] [14k,33k]

ポール

5[22,52] [14k,33k] 消化不良

風邪

分けると考える．このとき，命題の仮定よりすべての機密属性

ユニークな解が存在するといえる．
上記の定理に基づいて，以下の m-ユニークなグループを作成する手法を提案する．
［Step 1］ それぞれの QI グループに分割するためにバケット

BU C1 ,...,BU Cl を作成する．定理を用いてバケットの個数 l を⌊tupleN/m⌋ とする．次に l 個の空のバケットを作成する．以後はバケットにタプルを振り分けていく．

4. 新しい安全性の考察［Step 2］ 最初に l 個のタプルを振り分けていく．このとき，

本節では始めに m-ユニークな公開データを m-エリジブルと順に並べておいた機密属性 As1 から振り分ける．例えば BU C1

いう概念を使わずに作成する公開データ作成アルゴリズムを提には機密属性 As1 である胃炎のタプルの一つを振り分ける．こ案する．次に提案した公開データ作成アルゴリズムを用いて作れをバケット数 l 回分行う．

成した公開データの列は m-不変性の制約条件の緩和が可能か［Step 3］ 次に振り分けていない残りのタプルを振り分けてい否かを考察する．

く．振り分けるタプル t は，Step2 の振り分けが終わったタプル

4. 1 1 回目の公開アルゴリズム (提案 2)の次を選択する．振り分けを行うタプル t は各バケット BU C

元のデータを入力データとして，公開しても機密情報が特の中に入れたときに自信の値が情報損失の最も少ないバケット

定できないような公開データを作成する．公開者によって保管を選択する．この選択を行う際，以下の条件を満たす．

されている元のデータの表を T とする．また元データのタプル•

タプルの個数が最小のバケットの中で選択する．

•

バケット内はすべて異なる機密属性を持つので，同じ機の総数を tupleN とする．表 T の中の列を識別子属性 Aid (今qi回の場合，名前)，d 個の準識別子属性 Aqi
1 ,...,Ad (今回の場合，

密属性が存在する場合はそのバケットは選択しない．

年齢，ジップコード)，機密属性 A (今回の場合，病名) で分類

Step3 をバケットにタプルがすべて振り分けられるまで行う．

する．機密属性 As の中で，同じ機密属性 As は n 種類あると元データを表 9 として作成した公開データを表 11 とする． 表s表 13 2 回目の元データ

表 11 1 回目の公開データ (提案 2)
年齢

コード

名前

年齢

コード

病気

ボブ

22

15k

消化不良

風邪

デイビット

23

25k

胃炎

胃炎

エミリー

25

21k

風邪

ジェーン

37

33k

消化不良

胃炎

リンダ

43

26k

胃炎

風邪

ガーリー

40

20k

風邪

胃炎

メアリー

46

30k

胃炎

名前

G.ID

アリス

1

[22,24] [14k,25k] 気管支炎

アンディ

1

[22,24] [14k,25k]

デイビット

1

[22,24] [14k,25k]

ジェーン

2

[36,37] [27k,33k] 消化不良

ヘレン2

[36,37] [27k,33k]

ガーリー

3

[40,43] [20k,26k]

リンダ

3[40,43] [20k,26k]

病気

ポール

4

[52,56] [33k,34k] 消化不良

レイ

54

31k

消化不良

スティーブ

4

[52,56] [33k,34k]

胃炎

スティーブ

56

34k

胃炎

ケン

5

[22,40] [15k,25k]

風邪

トム

60

44k

胃炎

ボブ

5

[22,40] [15k,25k] 消化不良

ベニス

65

36k

風邪

1 の元データを以上の Step で公開データにする．このとき，節3.4 での手法との情報損失の比較を表 12 で示す．ここで，情報

表 14 2 回目の公開データ
番号

名前

G.ID

コード

病気

損失は一般化表での準識別子属性値の各区間の長さの総和とす

1

ベニス

1

[60,65] [36k,44k]

風邪

る．

2

トム

1

[60,65] [36k,44k]

胃炎

3

レイ

2

[54,56] [31k,34k] 消化不良

4

スティーブ

2

[54,56] [31k,34k]

5

ジェーン

3

[37,46] [30k,33k] 消化不良

6

メアリー

3

[37,46] [30k,33k]

胃炎

7

ガーリー

4

[40,43] [20k,26k]

風邪

8

リンダ

4

[40,43] [20k,26k]

胃炎

9

エミリー

5

[22,25] [15k,25k]

風邪

10

ボブ

5

[22,25] [15k,25k] 消化不良

11

デイビット

5

[22,25] [15k,25k]

4. 2 比較

1 回目の公開データ (提案 1) と 1 回目の公開データ (提案2) の情報損失の量を比較する．各準識別子 (今回の場合，列年
齢と列コード) を正規化した値を用いる．結果を以下の表 9 に示す．
表 12 情報損失の比較
年齢

年齢

胃炎

胃炎

ジップコード提案 1 3.231

4.005

提案 2 1.730

3.278

これより 1 回目の公開アルゴリズム (提案 2) の方が情報損失が低減されているので以後使用する．

4. 3 m-不変性を満たさない公開データの安全性

表 15 2 回目の公開データ
番号

名前

G.ID

1

偽造タプル c1

1

[22,25] [14k,25k] 気管支炎

年齢

コード

病気

2

エミリー

1

[22,25] [14k,25k]

風邪

3

デイビット

1

[22,25] [14k,25k]

胃炎

4

ジェーン

2

[37,46] [30k,33k] 消化不良

5

メアリー

2

[37,46] [30k,33k]

胃炎

次に 2 回目の公開データ作成を考える．その際，2 つの方法

6

ガーリー

3

[40,43] [20k,26k]

風邪を使用してデータの作成を試みた．1 つ目は 1 回目の公開アル

7

リンダ

3

[40,43] [20k,26k]

胃炎

ゴリズム (提案 2) を使用する方法，2 つ目は m-不変性の定義

8

偽造タプル c2

4

[52,56] [33k,34k] 消化不良に従って，m-不変性を満たす公開データを作成した．1 回目の

9

スティーブ

4

[52,56] [33k,34k]

胃炎

元データを表 9，公開データを表 11，2 回目の元データを表 13

10

ベニス

5

[22,65] [15k,36k]

風邪として 2 回目の公開データを作成した．1 つ目の 1 回目のアル

11

ボブ

5

[22,65] [15k,36k] 消化不良

12

レイ

6

[54,60] [31k,44k] 消化不良

13

トム

6

[54,60] [31k,44k]

ゴリズム (提案 2) を使用し公開データを作成した表を表 14 に示す．2 つ目の従来研究 [1] で定義されている m-不変性を満たすように作成した表を表 15 に示す．まず，表 14 が再公開可能
かどうか検討する．

胃炎

具体的には，始めに (場合 1)T(2)-T(1) の集合 { エミリー,
メアリー, レイ, トム, ベニス } に属する 2 回目の表で追加された各要素の機密情報が特定される可能性を調べる．次に，(場合2)T(1)-T(2) の集合 { アリス, アンディ, ヘレン, ケン, ポール }に属する 2 回目の表で削除された各要素の機密情報が特定される可能性を調べ，最後に，(場合 3)T(1)(表 9)∩T(2)(表 13) の集合 { ボブ, デイビット, ジェーン, リンダ, ガーリー, スティーブ } の各要素 t に関して推測される機密情報が特定される可能性 risk(t)<=1/m であることを確認する．例では m=2 であるとする．また表 11 と表 14 での任意のタプルが属する可能性のあ

記 4 名に関して推測のリスクは 1/m 以下となる．またボブのるシグネチャをまとめた表を表 16,17 に示す．

場合，T ∗ (1) のボブが属するグループの機密属性値は { 消化不表 16良, 風邪 } であり，T ∗ (2) でのボブが属するグループの機密属性

表 11 の視点 1

名前成り得る機密属性の候補

アリス{ 気, 風, 胃 }アンディ{ 気, 風, 胃, 消 }デイビット{ 気, 風, 胃, 消 }ジェーン{ 消, 胃 }表 T ∗ (1) でデイビットが属するグループの機密属性値の集合は

ヘレン{ 消, 胃 }{ 気管支炎, 風邪, 胃炎, 消化不良 } であり，表 T ∗ (2) では { 風ガーリー{ 風, 胃, 消 }{ 風, 胃 }邪, 消化不良, 胃炎 } なので，G.ID=5 の QI グループが公開可

リンダ
ポール

{ 消, 胃 }スティーブ{ 消, 胃 }ケン{ 風, 消, 胃 }ボブ{ 気, 風, 胃, 消 }値の集合は { 風邪, 消化不良, 胃炎 } となるので，T ∗ (1)∩T ∗ (2)によって機密属性値を推測されるリスク risk(ボブ) は 1/|{ 消化不良, 風邪 }| となり，1/m となる．またデイビットの場合は，能かどうかわかっていない．それを確かめるために表 18 を作成した．この表の作成方法としてはまずボブの属する機密属性
は { 風, 消 } であるので属する risk は 1/2 ずつになることがわ
かる．そしてボブの risk の和は 1 となっている．また表 16 よりタプル番号 11 の胃炎に属するのは { エミリー, デイビット }表 17

表 14 の視点 1

なので risk は 1/2 ずつになる．そして胃炎の risk の和は 1 と名前成り得る機密属性の候補なる．残りの risk については機密属性とタプルの両方の risk のベニス{ 風, 胃 }和が 1 となるように分ける．これによってすべての risk の和がトム{ 風, 胃 }レイ{ 消, 胃 }スティーブ{ 消, 胃 }ジェーン{ 消, 胃 }メアリー{ 消, 胃 }ガーリー{ 風, 胃 }リンダ{ 消, 胃 }エミリー{ 風, 消, 胃 }ボブ{ 風, 消, 胃 }デイビット{ 風, 消, 胃 }1 になることがわかる．そのなかでこの表のすべてが 1/m 以下になるので公開可能である．またすべてのタプルの成り得る機
密属性の確定した表を表 19 とする．
表 18

属性分布確率

風邪

消化不良

胃炎

エミリー

1/3

1/3

1/3

1

ボブ

1/3

1/3

1/3

1

デイビット

1/3

1/3

1/3

1

1

1

1

(場合 1) 始めに T ∗ (1)(表 11) では存在しなかったが T ∗ (2)(表14) で挿入されたタプルについて考える．例えば，エミリーの表 19 統合表のタプルの成り得る機密属性

タプルは属する QI グループのタプルが 3 つあるのでエミリー

名前成り得る機密属性の機密属性値を推測されるリスク risk(エミリー) は 1/|{ エミベニス{ 風, 胃 }リー, ボブ, デイビット }| より 1/3 となり，1/m 以下となる．

トム{ 風, 胃 }レイ{ 消, 胃 }スティーブずつある．上記 4 名に関しても推測のリスクは 1/m となる．

{ 消, 胃 }ジェーン{ 消, 胃 }この方法を使用した場合，偽造タプルが必要なく再公開が可能

メアリー{ 消, 胃 }

となる．

ガーリー

{ 風, 胃 }(場合 2) 次に T ∗ (1)(表 11) には存在したが T ∗ (2)(表 14) でリンダ{ 消, 胃 }は削除されたタプルについて考える．タプルを削除する際に，

エミリー{ 風, 消, 胃 }T ∗ (1) での QI グループの中の任意のタプル t が T ∗ (2) で m-

ボブ{ 風, 消 }メアリー, レイ, トム, ベニスの QI グループのタプルは各々2 つ不変性を満たされていないならば，同じ QI グループのタプル
が m 個以上削除されるなら再公開可能である．今回の場合，
アリスのタプルがあてはまる．T ∗ (1) でアリスの QI グループデイビット

{ 風, 消, 胃 }アリス{ 気, 風, 胃, 消 }アンディ{ 気, 風, 胃, 消 }ヘレン

で T ∗ (2) でも公開されるデイビットは m-不変性ではない．し{ 消, 胃 }ポール{ 消, 胃 }かし，同じ QI グループのタプルが m 個以上削除されるのでケン{ 風, 消, 胃 }∗∗T (1)∩T (2) によってアリスの機密属性値を推測されるリスク
risk(アリス) は 1/|{ アリス, アンディ}| より 1/m となる．

従来研究 [1] で定義されている m-不変性を保つように作成(場合 3) 最後に T ∗ (2)(表 14) においてスティーブの場合，m-

した公開データ (表 15 の場合) の場合すべてのデータについてユニークであり同じスティーブが属するグループは同じ機密のリスクが 1/m 以下になるので公開可能となる．しかし偽造属性値の集合を持つので m-不変性の性質を満たす．ジェーン，

タプルは 2 つ必要となる．

ガーリー，リンダも同様に m-不変性の性質を満たす．よって上

この 2 つの公開データを情報損失と偽造タプルの個数から比較する．比較した表をまとめたものをそれぞれ表 20,21 をして[条件 2] 各時刻 h において，各一般化表 Th∗ の各タプルは対応公開する．これによると情報損失は低減していることがわかる．

する元データ表 Th のいずれかのタプルに該当する．

偽造タプルの重さを大きいものと考えると本研究の提案を使用∀h∈[1,l],∀tg ∈Th∗ [して公開データを作成する方がよい．

∑

riskh (tg ,torg )=1]
torg ∈T ∗h∗[条件 3] 各一般化表 Th の各タプルにおいて，そのタプルが一

般化タプルである可能性のあるタプルは一般化タプルのもつ準表 20 情報損失の比較
年齢

ジップコード

表 14

1.017

3.803

表 15

1.218

4.625

識別子の値の範囲に含まれる値しか持ち得ない．

∀h∈[1,l],∀torg ∈Th ,∀th ∈Th∗ [∃Aqi ∈QI torg [Aqi ]∈t/ g [Aqi ]⇒riskh (tg ,torg )=0]
[条件 4] 各時刻 h において，各元データ表 Th のタプルの機密属性値が特定される確率は 1/m 以下である．

表 21

偽造タプルの個数の比較
個数∀h∈[1,l],∀torg ∈Th
[max{

∑

tg ∈T ∗ ∧t∗g [As ]=Shriskh (tg , torg )|S∈As }<
=1/m]

表 14

0

[条件 5] 統合表 U (l) に含まれる各タプルにおいて，各一般化

表 15

2

表で該当する可能性がある機密属性の候補集合はすべて同じでなければならない．ここで lif espan(tunion ) は，tunion が存在

4. 4 安全性の提案した期間を表す関数とする．

4.3 節の議論より従来の安全性の定義である m-不変性の制∀tunion ∈U (l),∀x∈lifespan(tunion )約が厳しすぎる場合があると考えられる．本研究では，偽造タ∗[x-1∈lifespan(tunion )⇒{t∗g [As ]|tg ∈Tx−1∧riskx−1 (tg ,tunion )=0}]|

プルの数を減らすことを目的として，背景知識テーブルを背景={t∗g [As ]|tg ∈Tx∗ ∧riskx (tg ,tunion )=0}|

知識としたときに元データ表のタプルと一般化表のタプルとを[条件 6] 各元データ表 Th のタプルに対応する一般化タプルに連結する攻撃 (record-linkage[3]) と元データ表のタプルと機密

対しては，特定される確率を 0 にすることはできない．

属性値とを連結する攻撃 (attribute-linkage[3]) の双方が成功す∀∈[1,l],∀torg ∈Th ,∀tg ∈Th∗ [(t∗org =tg )⇒(riskh (tg ,torg )=0)]|る確率を 1/m 以下に抑制するために，連続的匿名化結果であ

m-不変性を満たせば，m-連続安全性も満たされる．しかし，る一般化表の列が満たすべき安全性の性質を新たに提案する．

m-連続安全性を満たしても，m-不変性を満たさない場合が［定義 11］ (m-連続安全性)ある．例として，先に 4.3 で議論した表 11,14 の場合である．

1 から l までの各時刻における元データ表の系列 T1 ,T2 ,...,Tl

表 11,14 の場合，m-連続安全性を満たすリスク変数行列の列とそれぞれに対応する一般化表の系列 T1∗ ,T2∗ ,...,Tl∗ ，および，時Risk1 ，Risk2 の各要素への 0 以上 1 以下の実数値の割り当て

刻 l までの元データ表の統合表 U (l) が与えられたとき，以下のが存在する．よって，m-連続安全性はすべての一般化テーブル

条件を全て満たすリスク変数行列の列 Risk1 ,Risk2 ,...,Riskl (図に対する record-linkage 攻撃と attribute-linkage 攻撃の成功確

3 参照) の各要素への 0 以上 1 以下の実数値の割り当てが存在

率を 1/m 以下に抑えながら，m-不変性の制約を緩和した安全

するなら，一般化表の系列 T1∗ ,T2∗ ,...,Tl∗ は m-連続安全である．

性の定義である．

ここで，ある時刻 h(1<= h<=l) でのリスク変数行列 Riskh は

5. ま と め
本研究では情報損失の低減を目指して新しい安全性の考察を行った．実際に m-不変性を満たさなくても，m-連続安全性を用いて検証するとプライバシー保護データ作成することができ，
偽造タプルを必要とせず情報損失を低減できる例を発見するこ

図3

リスク変数行列

時刻 h での元データ表 Th のサイズ nh =|Th | と一般化表 Th∗とができた．今後の課題としては，一般化表系列が m-連続安
全性を満たすかどうかを判定する手法の提案，また，m-連続安
全性を満たす一般化系列の作成手法の提案が挙げられる．

のサイズ nh =|Th∗ | において，mh 行と nh 行の行列であり，i∗行 (i<=nh ) の要素を riskh (ti ,tj ) 変数とする．
=j <=mh )j 行 (i<=i<riskh (t∗i ,tj ) 変数での t∗i は一般化表 Th∗ での i 番目のタプルを表し，tj は元データ表での j 番目のタプルを表し，risk(t∗i ,tj )は一般化表 Th∗ のタプル t∗i が元データ表のタプル tj の一般化である可能性 (確率) を示す変数となる．

[条件 1] 各時刻 h において，各元データ表の各タプルは対応す
る一般化表のいずれかのタプルに該当する．

∀h∈[1,l],∀torg ∈Th [∑tg ∈T ∗hriskh (tg ,torg )=1]

文

献[1] X.Xiao,Y.Tao,”m-invariance: toward privacy preserving republication of dynamic datasets,” Proc. of SIGMOD’07,
pp.689-700 (2007).
[2] 村本俊祐, 上土井陽子, 若林真一,”プライバシー保護データ公開に向けた l-多様化適正の評価”, 情報処理学会論文誌 データベース, Vol.4, No.2, pp.126-141 (July 2011).
[3] B.G.M.Fung, K.Wang, R.Chen and P.S.Yu,”Privacypreserving data publishing:a survey on recent developments,” ACM Computing Surveys, Vol.42, No.1, pp.14:0114:53 (2010).