DEIM Forum 2016 A5-1

相関データにおけるベイジアン差分プライバシー
楊

斌†

佐藤

一誠††

中川

裕志†††

† 楽天株式会社 〒 158–0094 東京都世田谷区玉川一丁目 14 番 1 号†† 東京大学 大学院新領域創成科学研究科 〒 277–8561 千葉県柏市柏の葉 5–1–5††† 東京大学 情報基盤センター 〒 113–8658 東京都文京区弥生 2–11–16
E-mail: †yangbin64@gmail.com, ††sato@k.u-tokyo.ac.jp, †††nakagawa@dl.itc.u-tokyo.ac.jp
あらまし

差分プライバシーはデータプライバシーを保護するための強力なプライバシー基準である。データの相関性がある場合、差分プライバシーではデータのプライバシーを漏れるリスクがあることが知られている。この問題を解決するために、我々は、以下の三点について考察する：(1) データ相関性のプライバシーに及ぼす影響；(2) 攻撃者の事前知識のプライバシーに及ぼす影響；(3) 相関性のあるデータにおける任意の事前知識を持つ攻撃者に保護できる
汎用なプライバシー摂動アルゴリズム。上記三点の考察から、本稿では、Puﬀerfish プライバシーに基づき、「ベイジアン差分プライバシー」という新しいプライバシー定義を提案する。この定義を用いることで、相関性の有無にかかわらず、任意のデータのプライバシーを保護でき、任意の事前知識を持つ攻撃者の攻撃からプライバシーを守ることができる。更に、データの任意の構造に対してデータ相関性を表現できる「ガウシアン相関モデル」を提案する。このモデルに基づき、ベイジアン差分プライベートな摂動アルゴリズムを生成手法を提案することで、効率的に摂動ア
ルゴリズムを設計することができる。
キーワード

差分プライバシー，出力摂動，ガウスマルコフ確率場，最適化

1. は じ め に

インフルエンザのある人は何人がいるか？ というクエリを聞
くと、特定の人はインフルエンザがあるかどうかの情報を推定

ビッグデータと呼ばれる大量かつ多様なデータの活用をさまできるかもしれない。個人の健康情報を保護するため、ラプラ

ざまな業界で盛り込むとともに、個人情報漏洩やプライバシー

シアンノイズ Lap(1/ϵ) をクエリ結果に加えてから公開する必侵害は多数起こっている。個人情報の保護に関する法律と制度要がある。ラプラシアンノイズが ϵ− 差分プライバシーに満たを整備する一方、技術的な対策も必要不可欠である。プライバ

すことは知られているが、(1) この 10 人全員は無相関な場合、

シー保護技術として摂動法と匿名化法と暗号法 (秘密計算法)

特定の人がネットワークに含まれるかどうかにかかわらず、公の二種類がある。本稿で、摂動法によるプライバシー保護方法

開されたクエリ結果の確率分布ほとんど同様だから、その人のを考える。具体的に、ある組織が個人のデータを収集し、その情報は推定しにくい；(2) この 10 人全員は極めて強い相関性をデータに対するクエリ結果を計算し、データの利用者 (例えば、持つ場合 (例えば、10 人の家族)、全員はほとんど同じ状態であ研究機関) へ共有することで、ビッグデータは最大限に活用さるので、正しいクエリの値は 0 または 10 しかではない。ゆえれる。その一方、公開されたクエリ結果により、個人情報やプに、一人の状態の変化はクエリ結果に 10 倍の変化を引き起こ

ライバシーを漏れるリスクがある。個人情報やプライバシーをす。同じ水準のプライバシーを保証するために、ラプラシアン

推定できないために、公開する前、ノイズを加える必要がある。

ノイズ Lap(1/10ϵ) を加えるのが必要である；(3) 中間的な例とこのような方法は摂動法と呼ばれる。

して、この 10 人は弱い相関性を持つ場合 (例えば、10 人の友

近年、摂動法の手法として、差分プライバシーという概念が達)、特定の人の情報が他人に影響があるが、クエリの結果は固プライバシー業界で注目を集めている。差分プライバシーは、定な値ではない。この場合、どんなノイズを加えればよいか？

攻撃者の背景知識にかかわらず、強いプライバシー基準を提供

一方、実世界からデータの相関性を取得するのが比較的に容する。直観的に、個体の変化による公開データに及ぼす影響が易である。例えば、ウェブクラウリーを用いることで、ソーシャ

顕著ではないことを保証する。

ルネットワークの構造を確かめることができる。“政治的傾向

1. 1 相関データ

がリベラル派と保守派である人はそれぞれ何人いるか” という差分プライバシーが完璧なプライバシー基準であることはクエリの結果が与えられたら、特定な人の政治的傾向が推定さ

広く認められているが、データは相関性がある場合、プライバ

れやすいかもしれない。結局、データ相関性のプライバシーにシーを漏れる可能性があることは知られている [6]。10 人を含及ぼす影響を慎重に考察するのが非常に重要である。

むソーシャルネットワークを考えてみよう。このネットワーク

1. 2 攻撃者の事前知識にいる人々の間、家族や友達や同僚など様々な関係がある。例

差分プライバシーを提案することで、最も強い攻撃者の攻撃

えば、ある “攻撃者” はこのネットワークの構造 (人々の関係)からプライバシーを保護することができる。潜在的な仮定としを知っているが、人々の個人情報を知らない。“この 10 人に、ては、攻撃目標以外全ての情報を持つ、最も強い攻撃者は公開

表 1 差分プライバシーの妥当性.

PP
PP 攻撃者 強い
PP
データ
PP

任意

Independent

妥当

妥当

Correlated

妥当 妥当でないされたクエリ結果により、攻撃目標に関する最も多い情報を推定できることである。実は、データは相関性がない、又は攻撃者は最も強い場合 (攻撃目標以外全ての情報が知られる)、差分
プライバシーでプライバシーを保護することができる。しかし、

表2

Symbol記

号

Descriptionx

データベースの事例 {x1 , x2 , · · · , xn }.

n

データベースのタプルの数 x.

[n]タプル集合 {1, 2, · · · , n}.

i

攻撃目標となるタプル.

K, U

既知／未知タプル集合.

C

攻撃目的と既知タプル {i} ∪ K.

xi , x′i

タプル i ∈ [n] の二つの事例.

x−i

データベース x から xi を除いた集合.

x′

データベース x に xi を x′i へ変換した集合.

データは相関性があるかつ攻撃者一部の事前知識しか持たない

xK , xU

既知／未知タプルの事例.

場合、プライバシーが侵害される恐れがある (表 1)。

A(i, K)ある K を持つ xi を攻撃したい攻撃者.

2. 関 連 研 究
敵対的プライバシーというのは攻撃されることに関する事
前確率と事後確率が明示的に表現されるプライバシー定義で

f

データベース x 上のクエリ関数.

q

正しいクエリ結果 q = f (x).

Mx 上のランダムメカニズム.

r

M に生成されたランダムリクエスト.

ある。センシティブな変数 x とクエリ結果 r が確率変数とする。Miklau と Suciu [9] に提案された Perfect プライバシーとで表す、すなわち、[n] = {1, 2, · · · , n}。このデータベースをは、与えられた r に対し、Pr(x|r) ≡ Pr(x) が成り立つことで入力とするクエリ関数 f の結果 q = f (x) を公開するとき、各ある。直観的に、この定義で、r が与えられた時の x の事後確

タプルのプライバシーを保護するため、摂動されたクエリ結果

率分布はその事前確率分布は全く同じである。残念ながら、一r = M(x) だけを公開する。ただし、M はあるランダム関数で般的に、Perfect プライバシーに満たす出力はユーティリティ

あり、確率分布 Pr(M(x) ∈ S) あるいは Pr(r ∈ S|x) で表せるがない。この定義を基づき、より緩和的な定義も考慮されてい(S ⊂=Range(M))。M はクエリ q のランダム関数として扱えるる。Dwork ら [1] に提案された差分プライバシーが最も厳密な場合、Pr(r ∈ S|q) とも表せる。本稿でよく使われる記号は表

プライバシー基準であることは広く認識されている。差分プラ

2 に載る。

イバシーに基づくプライバシー定義も多数が存在している。

3. 1 仮Kifer と Machanavajjhala [6] は一連の事例を考えたうえ、差定

以下に、三つの仮定を記述する。

分プライバシーにおける重要な問題を提起した。要するに、デー

3. 1. 1 データの相関性

タが強い相関性を持つ場合、クエリ出力からセンシティブな情

全てのタプルはランダム変数と認められるので、その相関性報を推定しやすいので、差分プライバシー基準はプライバシー

はタプルの同時分布 Pr(x1 , x2 , · · · , xn ) で表せる。マルコフ確を保証しないことがある。Kifer と Machanavajjhala [6] は隣率場を用い、この同時分布をグラフで表現できる。

接の概念を再定義することで、確定な制約を持つデータベースにも適用できるように、差分プライバシーの定義を修正した。

仮定一：タプル間は独立あるいは相関であり、その相関性がだれにも知られる。

Gehrke ら [2], [3] も相関データにおけるプライバシーに注目し、

3. 1. 2 攻 撃 者

zero-knowledge プライバシーという概念を提案した。提案さ攻撃目標とするタプルと既知タプルセットと未知タプルセッ

れた摂動法メカニズムで、相関データのプライバシーを保護でトを明示的に指定することで、任意の攻撃者を A(i, K) で定義

きるが、集計関数集の選択はやや難しい。ベイジアンプライバする。ただし、タプル i ∈ [n] を攻撃目標タプルであり、タプル

シーの定義とする Puﬀerfish [7] は本研究で提案された新しい

セット K⊂=[n] \{i} を既知タプルセットであり、U = [n] \{i} \ K

プライバシー定義のフレームワークと見なされる。Puﬀerfish

を未知タプルセットである。特には、攻撃者 A(i, [n] \ {i}) をに啓発された Blowfish [5] は特殊なプライバシー定義である。

強い攻撃者といい、攻撃者 A(i, ϕ) を弱い攻撃者という。

この定義を用いることで、必要な制限だけを特定し、出力結果のユーティリティを改善した。もうひとつのベイジアンプライ
バシー定義 [12] には、タプルにある各属性はベイジアンネット
ワークと見なされる。Rastogi ら [10] は相関データを考慮し、差分プライバシーより弱い敵対的プライバシー定義を提案し、出力結果のユーティリティを改善した。[4] には、ソーシャルネッ
トワーク向けの差分プライベートなメカニズムは提案された。

仮定二：任意の背景知識 K⊂=[n] \ {i} を持つ攻撃者はタプル

i を攻撃する。
3. 1. 3 メカニズム
多くの暗号アルゴリズムと同じよう、摂動メカニズム自体も公開されるとする。
仮定三：条件確率分布 Pr(r ∈ S|x) と同値であるランダム関
数 M(x) は、誰にも知られる。
情報の利用者は攻撃者となることもあるので、本稿で考えら

3. プライバシーと相関データ

れた攻撃モデルは、データ相関性、メカニズム M、出力 r と

n 個タプルを含むデータベースをそのタプルのインデックス

攻撃者の背景知識 K を用い、攻撃目標であるタプル i の情報を

表3推定する問題になる。

同時分布 (Pr(x1 , x2 ))x1 = 0 x1 = 1

3. 2 差分プライバシーとラプラシアンメカニズム
x2 = 0

上記の記号を用いで、差分プライバシーの定義を再掲する。

x2 = 1

0.15

0.3

0.45

(a) 独立定義 3.1 (差分プライバシー) あるランダムメカニズム M が

x1 = 0 x1 = 1

下記の条件に満たせば、差分プライバシーという。

Pr(r ∈ S|xi , x−i ) <DP (M) :=
sup
log
ϵ.
Pr(r ∈ S|x′i , x−i ) =i,x−i ,xi ,x′ ,S

0.1

(1)

x1 = 0 x1 = 1

x2 = 00.49

0.01

x2 = 00.01

0.49

x2 = 10.01

0.49

x2 = 10.49

0.01(b) 正の相関i(c) 負の相関

ラプラシアンメカニズム [1] では、クエリ結果にラプラス分
布 p(z) ∼ Lap(λ) に従うノイズを加え、その結果を公開する。

λ = S(f )/ϵ の場合、公開された結果は ϵ–差分プライバシーに満たす。ただし、S(f ) = sup ||f (x) − f (x′ )||1 は関数 f についてのセンシティブと呼ばれる。直観的に、r = f (x) + z
1 |r−f (x)|
−λ

1
e
と
λ
1 |r−f (x′ )|
1 −λ
e
である。
ϵ
が小さいから、
ϵ–差分プ
λ′だ か ら 、出 力 の 密 度 は そ れ ぞ れ p(r|x) =′p(r|x ) =ライバシーでは p(r|x) ≈ p(r|x ) であることを保証できる。

3. 3 差分プライバシーの妥当性
p(r|x ,x)

差分プライバシーは R = p(r|xi′ ,x−i ) を狭い区域に抑える、i−iϵ
すなわち、e−ϵ <=R<= e 。ここで、強い攻撃者であることが仮定されている (K = [n] \ {i})。任意の攻撃者の場合、事前知識
i ,xK )
x−i が xK になり、R が p(r|xになる (K⊂p(r|x′ ,x )=[n] \ {i})。
iK

表 1 に記載されるケースにおいて差分プライバシーの妥当性を考えてみよう。具体的に、相関データの場合に R が [e−ϵ , eϵ ]に抑えられるかどうかを考察する。
p(r|x1 = 0, x2 = 0)

立であるから、Pr(x2 |x1 ) ≡ Pr(x2 )。M は差分プライバシーp(r|x1 =0)ϵに満たすので、e−ϵ <=e 。
= p(r|x1 =1) <3. 3. 2 相関データ
タプルが確率的に相関であれば、強い攻撃者の場合でも、Rが [e−ϵ , eϵ ] に抑えられるが、弱い攻撃者の場合に、R がその区域に抑えられないかもしれない。
例えば、データベース x = {x1 , x2 }(x1 , x2 ∈ {0, 1}) が確率
分布表 3(b) に従い、x1 と x2 は相関がある。

x2 が分かる強い攻撃者の場合、図 1(a) と (b) のように、Rが抑えられる。
一方、何も分からない弱い攻撃者 A(1, ϕ) に対し、p(r|x1 ) =∑x2

p(r|x) Pr(x2 |x1 ) である。極めて高い確率で x1 と x2 が等しいから、図 1(d) のように、曲線 p(r|x1 = 0) と p(r|x1 = 1)
がお互いに離れた。結局、メカニズム M が差分プライバシーに満たすのに、R が抑えられない。

p(r|x1 = 1, x2 = 0)以上の例で、攻撃者の事前知識が少なければなるほどプライ

(a)
-2
0
p(r|x1 = 0, x2 = 1)

ゆえに、p(r|x1 ) が図 1(a) と (b) のようになる。x1 と x2 が独

2

4
p(r|x1 = 1, x2 = 1)r

バシー情報を攻撃しやすいことと示唆する。実は、この結論も正しくない。以下に、その反例を挙げる。
例えば、データベース x = {x1 , x2 }(x1 , x2 ∈ {0, 1}) が確

(b)
-2

0
p(r|x1 = 0)

2

4

r

p(r|x1 = 1)率分布表 3(c) に従う。ここで、弱い攻撃者 A(1, ϕ) に対し、

p(r|x1 ) =

(c)
-2

0

2

p(r|x1 = 0)4p(r|x1 = 1)0p(r|x1 = 0)2p(r|x1 = 1)

4

0

2

p(r|x) Pr(x2 |x1 ) であるが、極めて高い確率で

x1 と x2 が異なる。図 1(e) のように、二つの曲線がほとんど

r

合、Lap(1/ϵ) は極めて高いプライバシー水準を持つ。

r

定義が必要となる。

要するに、全攻撃者に対応できる、より厳密なプライバシー

(e)
-2

x2

重ねるので、x1 = 0 と x1 = 1 が非常に識別しにくい。この場

(d)
-2

r

∑

4

図 1 相関データにおけるラプラシアンノイズ.

4. ベイジアン差分プライバシー
以上の例でデータの相関性がある時に差分プライバシーが脆

3. 3. 1 独立データ

弱性を示した。情報漏洩のプライバシー水準を正しく評価する

全てのタプルがお互いに独立であれば、強い攻撃者の場合でも、弱い攻撃者の場合でも、R は [e−ϵ , eϵ ] に抑えられる。
例えば、データベース x = {x1 , x2 }(x1 , x2 ∈ {0, 1}) が確率
分布表 3(a) に従う。クエリ関数 f (x1 , x2 ) = x1 + x2 に、ラプ
ラシアンノイズ Lap(1/ϵ) を加える。

x2 が分かる強い攻撃者 A(1, {2}) はタプル 1 の値を攻撃する。
M は差分プライバシーに満たすので、図 1(a) と (b) に示された
p(r|x1 =0,x2 ) < ϵ
よう、R 値は抑えられる。すなわち、e−ϵ <==e 。
p(r|x1 =1,x2 )一方、何も分からない弱い攻撃者 A(1, ϕ) もタプル 1 の値を攻撃する。ベイズの定理により、p(r|x1 ) =∑x2

p(r|x) Pr(x2 |x1 )。

ため、本節で、差分プライバシーの定義を拡張し、ベイズ的な新しいプライバシー定義を提案する。

4. 1 定義差分プライバシーの本質的な目標は攻撃目標であるタプルの追加、削除及び修正によらず、公開されたクエリの確率分布がほぼ変換されないようなメカニズムを設計することである。提案された定義では、一部のタプルしか分からない弱い攻撃者にも適用される。主なアイデアとして、未知のタプルを周辺化することで、既知のタプルとクエリ結果に関係を作ることである。

定義 4.1 (ベイジアン差分プライバシー)

A = A(i, K) を攻

4. 2. 3 相関データと任意の攻撃者

撃者とし、M(x) = Pr(r ∈ S|x) をデータベース x 上のランダ

以上の分析は、全てのタプルが独立であるあるいは全ての攻ム摂動メカニズムとすると、A における M のベイジアン差分

撃者が強い場合に、BDP は DP と全く同じであることを示唆

プライバシー漏洩はする。ただし、一般的に、タプルの相関性があるケース及び攻Pr(r/inS|xi , xK )BDP LA (M) :=sup logPr(r ∈ S|x′i , xK )′xi ,x ,xK ,S(2)

撃者は一部のタプルしか知らないケースにおいて、プライバ
シーを考える必要がある (表 1 の右下)。

i

例えば、データベース x = {x1 , x2 } において、x1 と x2 の同時である。ただし、x が連続関数であれば、∫Pr(r ∈ S|xi , xK ) =Pr(r ∈ S|x)p(xU |xi , xK )dxU

(3)

Pr(r ∈ S|xi , xK ) =考えよう。A(1, {2}) が x2 を知り、x1 の値を攻撃したい強い攻撃者であり、A(1, ϕ) が何も知らず、x1 の値を攻撃したい弱い攻撃であり；x が離散関数であれば、∑分布は表 3(b) のように示され、クエリ関数を f (x) = x1 +x2 をPr(r ∈ S|x) Pr(xU |xi , xK )(4)を生成し、クエリ結果 r に加える。定理 4.2 により、攻撃者

xU

A(1, {2}) のプライバシー漏洩は BDP LA(1,{2}) (M) = ϵ であである。もし、以下の条件に満たせば、sup BDP LA (M) <=ϵ者である。ラプラシアンメカニズムでノイズ Lap(1/ϵ)(ϵ = 0.1)

(5)る。一方で、A(1, ϕ) のプライバシー漏洩は

A

BDP LA(1,ϕ) (M)∑Pr(r|x1 = 0, x2 ) Pr(x2 |x1 = 0)x
= sup log ∑ 2

M は ϵ–ベイジアン差分プライバシー (ϵ–BDP) に満たすという。
ここで、r が連続である場合、(2) は下記の式と同値であり；

BDP LA (M) =supxi ,x′i ,xK ,tlogp(r = t|xi , xK )p(r = t|x′i , xK )(6)r が離散である場合、(2) は下記の式と同値である。
Pr(r = t|xi , xK )BDP LA (M) = sup log
Pr(r = t|x′i , xK )′xi ,x ,xK ,t

r

= log

x2

Pr(r|x1 = 1, x2 ) Pr(x2 |x1 = 1)

0.98 + 0.02e−ϵ≈ 0.196 ≈ 2ϵ.
0.02e−ϵ + 0.98e−2ϵである。BDP LA(1,ϕ) (M) > ϵ ので、ϵ-BDP に満たさない。

x1 = 0 であれば、高い確率で x2 = 0 である。従って、高い(7)i

確率で f = 0 である。同様に、x1 = 1 であれば、高い確率で差分プライバシーとの区別としては、事前知識は x−i では

f = 2 である。つまり、x1 の変化により f に大きい変化を引きなく、xK である。ベイズの定理を用いることで、未知のタ起こす。故に、M の出力 r により元の x1 の値を推定するのがプルを評価できる。(3) と (4) により、Pr(r ∈ S|xi , xK ) は容易となり、そのプライバシー漏洩が大きいといえる。

二つの部分に分けられる。Pr(r ∈ S|x) は摂動メカニズムで以上の例で、ラプラシアンメカニズム M で弱い攻撃者におけあり、p(xU |xi , xK ) はデータの相関性である。この定義で、る R を制限できないので、R を [e−ϵ , eϵ ] に制限できる ϵ′ (>= ϵ)Pr(r ∈ S|xi , xK ) と Pr(r ∈ S|x′i , xK ) の差の最大値 BDP L をを探す必要がある。Lap(1/ϵ′ ) は全ての攻撃者にプライバシー

評価する。BDP L は ϵ で抑えられれば、この摂動メカニズムを保証できる。結果として、最も弱い攻撃者は最も大きいプラは ϵ のプライバシーレベルを持つという。すなわち、ϵ–BDP。

イバシー漏洩を持ち、メカニズムのプライバシー水準を決める。

4. 2 BDP と DP の比較

しかし、この結論はいつも正しいか？次の例を考えよう。
例えば、データベース x の同時分布は表 3(c) のように示さ

BDP は差分プライバシーの拡張とし、より厳しいプライバ
シー基準である。(3) により、BDP はメカニズム M とデータ相関性で表せる。すなわち、

BDP LA (M) =supxi ,x′i ,xK ,S

∫
log ∫

Pr(r ∈ S|x)p(xU |xi , xK )dxU
Pr(r ∈ S|x′ )p(xU |x′i , xK )dxUれる。この時、弱い攻撃者 A(1, ϕ) のプライバシー漏洩は

BDP LA(1,ϕ) (M)
(8)

∑

r

DP との区別は未知タプル xU が周辺化されたことである。
= log

4. 2. 1 独立データ
全タプルは独立の場合、p(xU |xi , xK ) ≡ p(xU ) である (表 1の上の行)。

d

Pr(r|d1 = 0, d2 ) Pr(d2 |d1 = 0)d2

Pr(r|d1 = 1, d2 ) Pr(d2 |d1 = 1)

= max log ∑ 2

0.02 + 0.98e−ϵ≈ 0.004 ≪ ϵ.
0.98e−ϵ + 0.02e−2ϵとなる。BDP LA (M) <= ϵ(∀A) ので、ϵ-BDP に満たす。

x1 の値にかかわらず、f の値が 1 になりやすい。つまり、
定理 4.1 (独立データ)

全てのタプルがお互いに独立である

場合、ϵ–BDP は ϵ–DP と同値である。

4. 2. 2 相関データと強い攻撃者
タプルは相関があるかつ強い攻撃者が限定されるケースを考えよう (表 1 の左下)。

x1 の変化は f に大きい変換を引き起こさない。結果として、
BDP LA(1,ϕ) は ϵ より小さい。それにもかかわらず、強い攻撃者のプライバシー漏洩は ϵ であるので、任意の攻撃者におけるプライバシー漏洩は ϵ である。
要約すると、弱い攻撃者が大きいプライバシー漏洩を持つ場
合もあり、強い攻撃者が大きいプライバシー漏洩を持つ場合も定理 4.2 (相関データと強い攻撃者) 攻撃者は攻撃目標以外ある。BDP を計算する際に、全ての攻撃者を考える必要があるの全てのタプルが分かる場合、ϵ–BDP は ϵ–DP と同値である。

ことを示唆する。さらに、ϵ–DP は BDP LA(i,[n]\{i}) (M) <=ϵと同値であり、ϵ–BDP は BDP LA(i,K) (M) <= ϵ と同値であり、す。ただし、各頂点 xi ∈ x が一つのタプル i に対応し、各重み

BDP は DP より強いことが知られている。

wij ∈ W (wij >= 0) がタプル i と j の相関を表す。ここで、ネッ

4. 3 BDP と Puﬀerfish プライバシーの比較

トワークが連結であることを仮定する。つまり、任意のタプル

Puﬀerfish プライバシー [7] はベイズ的なプライバシーフレー

i と j に対し、i から j までの通路が少なくとも一通りがある。

ムワークである。提案されたベイジアン差分プライバシーには、データの相関性、攻撃者の知識とメカニズムが明示的に定義さ定義 5.1 (ガウシアン相関モデル)れたので、Puﬀerfish プライバシーの特殊なケースであること

向グラフとする。ただし、各頂点 xi ∈ x はデータベースには認められる。

あるタプルに対応し、各辺 wij ∈ W (wij >= 0) はタプル i

4. 4 議G(x, W ) を重みつけた無と j の相関を表す。W = (wij ) を重みつけた隣接行列とし、論

直観的に、強い攻撃者はより多い背景知識を持つから、プラ
イバシーのリスクが高いのは当然であるが、なぜ、前の例で弱D = diag(w1 , w2 , · · · , wn ) を G(x, W ) の次数 (degree) 行列とし (wi =

∑

j =i
|



い攻撃者がプライバシーのリスクが高いのであるか？

[7] の議論と同様に、ベイジアン差分プライバシー漏洩は事
前オッズ比と事後オッズ比の差で表される。

(

wij )、L をラプラシアン行列 G(x, W ) とする。

)

Pr(xi |r, xK )Pr(xi |xK )BDP LA (M) = sup log− log.
Pr(x′i |r, xK )Pr(x′i |xK )強 い 攻 撃 者 A(1, {2}) に 対 し 、事 前 分 布 Pr(x1 |x2 = 1) は{0.02, 0.98} であり、出力 r = 2 を公開すると、その事後分布
Pr(x1 |r = 2, x2 = 1) は {0.018, 0.982} であるが、弱い攻撃者w1

 −w12
L=D−W =
..


.
−w1,n



−w12

···

−w1,n

w2
..
.

···
..
.

−w2,n 
 . (9)
..


.

−w2,n

···



wn

∀i ∈ [n] に対し、x−i = x[n]\{i} の条件確率は下記であれば、(
p(x−i |xi ) ∝ exp −A(1, ϕ) の事前と事後分布はそれぞれ {0.5, 0.5} と {0.45, 0.55}

xT Lx
2

)
.

(10)

である。事前分布と事後分布の差の変化は、弱い攻撃者のほう(x, L) をガウシアン相関モデルといい、G(x, L) と表記する。

が強い攻撃者より大きいから、BDPL はより大きい。

行列 L を G(x, L) のガウシアン相関行列という。

データ相関性と未知タプルはクエリ結果に大きい変化を引き起こし、大きい情報漏洩も引き起こす。ベイジアン差分プライ
バシーは未知タプルと明示的なデータ相関性を用いることで、この情報漏洩を捉えることができる。

任意の攻撃者 A(i, K) に対し、i、K と U の値にかかわらず、

p(xU |xi , xK ) が以下の形式で表せる。

(

p(xU |xC ) ∝ p(xU , xK |xi ) ∝ exp −5. ガウシアン相関モデル

xT Lx
2

)
.

(11)

特には、U はただ一つのタプルの場合 (U = {u})、(11) は合計クエリはデータ開示の領域で広く使われているから、以xu の条件分布になる (C = [n] \ {u})。すなわち、(下に、合計クエリのみを考える。さらに、カウンティングクエ

p(xu |x−u ) ∝ exp −リやヒストグラムなども合計クエリから導出される。

T
wu x2u + 2xT−u L̃ xu2)
(12)

5. 1 モ デ ル
任意のマルコフ確率場はある多変量の同時分布である。ベイジアン差分プライバシーを計算するため、全ての n2̇

n−1

個の

攻撃者を考えるのが必要であるから、この計算は一般的に困難である。我々の目的は、複雑なデータ相関性を表現できる及び

ただし、

x−u = (x1 , · · · , xu−1 , xu+1 , · · · , xn )T ,(13)

L̃ = (−w1u , · · · , −wu−1,u , −wu,u+1 , · · · , −wun ).

(14)

そのベイジアン差分プライバシー漏洩を計算できるような相関モデルを作るのである。マルコフ確率場の一種類として、ガウ結果として、(12) 下記のガウス分布になる。

(

シアンマルコフ確率場は下記の特徴を持つ。
第一、タプルは相関あるいは独立であり、相関の強さも任意

p(xu |x−u ) ∝ exp∑ wuj 2
wu
−
(xu −
xj )
2
wu

)
.

(15)

j =u
|

である。このような相関は重み付けるネットワークで表され、∑

wuj
x は xu の隣接タプルの重みつけた
wu j
j =u
|

相関の強さは辺の重みで表現される。ガウシアンマルコフ確率

この分布の平均場でこのネットワークから直接に定義できる (定義 5.1)。

平均値である。大きい相関性 wuj は xj が xu へ大きい影響が第二、BDPL を評価するため、一部のタプルが与えられ、ほあることを意味する。

かのタプルの条件確率分布を計算する必要がある。ガウシアン

5. 2 相関性の分析

マルコフ確率場では、全ての条件分布がガウシアンであり、本稿の主な結論を容易に引き出せる (定理 5.2)。
第三、ガウシアン分布は非常に計算しやすくて、効率的なアルゴリズムの設計が可能になる (Algorithm1)。
データベース x と相関を重み付けたグラフ G(x, W ) と見な

ガウシアン相関モデル上のタプルの集計クエリ s = sum(x)に、ラプラシアンメカニズムでノイズを加え、r = s + Lap(1/ϵ)
を出力する。ベイジアン差分プライバシー漏洩を計算するために、任意の A(i, K) に対し、p(r|xi , xK ) を評価する必要がある。周辺化することで、

∫p(r|xi , xK ) ∝p(r|s)p(s|xi , xK )ds.

(16)

命題 5.1 (組合せ) G(x, L) をあるガウシアン相関モデルとする。任意の攻撃者 A = A(i, K) に対し、C = {i}∪K,
U = [n]\C∑

ここで、p(s|xi , xK ) はタプルとクエリ結果の相関であり、p(r|s)とし、m = |U| を U のサイズとする。x0 =

u∈U

xu

m

であり、

はラプラシアンメカニズムである。データ相関性 p(s|xi , xK ) を

xA = {x0 , xi } ∪ xK = {x0 } ∪ xC と仮定すると、G(xA , LA )本節で、ラプラシアンメカニズム p(r|s) を次節で議論しよう。

もガウシアン相関モデル。更に、攻撃者 A′ = A(i, K′ ) を A

個の異なる攻撃者 A(i, K) をそれぞれ評価するのは困の先祖とする。すなわち、K′ = K \ {j} (∃j ∈ K) である。

難である。本稿で、高いプライバシー漏洩を持つ攻撃者の部分

U ′ = U ∪ {j} とし、C ′ = K′ ∪ {i} とする。もし、A のガウシ集合を求め、この部分集合にプライバシー漏洩が最も高い攻撃

アン相関行列が下記であれば、

2n−1

者を探す方法を提案する。まずは、攻撃者のプライバシー漏洩の関係を反映できる階層的な構造を作る。
′

任意の攻撃者 A = A(i, K) に対し、K ⊂ K であれば、

(
LA =

w0

T
−w0C

−w0C

WC



)

w0

−w0j

=  −w0j

wj−w0C ′

A′ = A(i, K′ ) が A より弱いといい、A が A′ より強いという。
一方、|K| − |K′ | = 1 であれば、A′ が A の先祖といい、A が

(

LA′ =






I
 6@
  @

I
 6@
  @

  
I @
I 6
6@

@ @

  
I @
I 6
6@

@ @

  
@
I 6 
@
2

  
@
I 6 
@

34


i = 1, K⊂={2, 3, 4}34


i = 2, K⊂={1, 3, 4}

∅

∅

∅

2

23

3

4

24

34

13

1


 6@
I
 @
2

4

14

24

14

4

1

2

3

13

23

  
I @
I 6
6@

@ @

  
@
I 6 
@
1
24


  
@
I 6 
@
1
23


i = 3, K⊂={1, 2, 4}

′
−w0C
′

WC′ ′

WC ′

)

,

(21)

2
(m + 1)2 (w0 wj − w0j)2
m wj + 2mw0j + w0

WC′ ′ = WC′ −(w0j + mwj )w0C′ + (w0 + mw0j )wjC ′m2 wj + 2mw0j + w0

T
T
(w0C ′ − mwjC ′ )(w0C′ − mwjC ′ ).
m2 wj + 2mw0j + w0

5. 3 出 力 摂 動
本節で、(16) にある摂動メカニズム p(r|s) をパラメータ λと 0 を持つラプラシアンメカニズムに限定し、ベイジアン差分


 6@
I
 @

12

′T
−w0C
′

′
w0C
′ = (m + 1)





w0′

34

  
I @
I 6
6@

@ @
12

w0′ =

1





3

プライバシーに満たすように、λ を適当に選択する。すなわち、z ∼ Lap(λ) =1 − |z|
e λ .
2λ

(22)

このノイズをクエリ結果 s に加えて、その結果 r = s + z を公開する。大きい λ は低いユーティリティに引き起こすから、以下で、ベイジアン差分プライバシーに満たすような最も小さい

λ を見つける。

i = 4, K⊂={1, 2, 3}

定理 5.1 で、摂動メカニズム p(r|s) をデータ相関 p(s|xi , xK )図 2 K における階層的構造.

に結びつけることで、ベイジアン差分プライバシー漏洩 BDPL

一般的に、∀A(i, K) に対し、の計算方法は与えられる。

p(s|xi , xK ) = p(sU = s − sK − xi |xi , xK )定理 5.1 G(x, L) を ガ ウ シ ア ン 相 関 モ デ ル と し 、s =∝ p(sU , xK |xi )ただし、sU =

∑
i∈U

∑

(17)

xi 。xU が未知だから、sU が乱数と見′′なされる。∀A(i, K) の先祖 A(i, K ) (K = K \ {j}) に対し、

U ′ = U ∪ {j} であり、sU ′ = sU + xj となる。そして、
p(sU ′ , xK′ |xi ) = p(sU + xj , xK′ |xi ).

(18)

xi を x 上の集計クエリとする。ラプラシアンメカニズム

攻撃者 A = A(i, K) に対し、x0 =

(19)

)

(
x0
xC



x0

u∈U

|U |



xu

を未知タプルの平=  xi  とし、対応するガウシ

xK
アン相関行列は下記の式とする。



つまり、周辺化することで、sU と xj を一つの変数 sU ′ に纏めると、(18) を (19) から導出できる。

i∈[n]

M で、摂動出力 r = M(x) = s + z∑を生成する (z ∼ Lap(λ))。

均値とし、xA =一方で、p(sU , xK |xi ) = p(sU , xj , xK′ |xi ).



T
−wjC
′  ,(20)

ただし、

∅

1



A′ のガウシアン相関行列が下記のようになる。

A′ の子孫という。図 2 で、四つのタプルを含むデータベースの階層的構造が示される。

−wjC′

T
−w0C
′

w0

−w0i

LA =  −w0i

wi



−w0K

−wiK′

T
−w0K




T
−wiK
.

(23)

WK

M > 0 と m = |U| を仮定すると、A についての M のベイジ

5. 5 事前分布を持つガウシアン相関モデル

アン差分プライバシー漏洩は下記となる。

BDP LA (M; M ) =

M
λ

(

1+

mw01
w0

)

.

(24)

0i
本稿で、ℓA = mw
を A に関する相関モデルの漏洩係数とw0いう。結局、BDP LA (M; M ) = (1 + ℓA ) Mとなる。
λ弱い攻撃者 A(i, ϕ) は大きいプライバシー漏洩を持つから、対(応するガウシアン相関行列は 2×2 行列

w0

−w0i

−w0i

w0

)

とな

る。ガウシアン相関行列の定義及び定理 5.1 により (m = n−1)、

5. 4 メカニズム
本節で、全ての攻撃者から、ベイジアン差分プライバシー漏

BDP LA(i,ϕ) (M; M ) ≡

nM
.
λ

(27)

洩が最も大きい攻撃者を見つける。ゆえに、全ての攻撃者に対ゆえに、ベイジアン差分プライバシーに満たすために、n 倍のし、ϵ-BDP を満たすようなラプラシアンメカニズムを作れる。

分散のラプラシアンノイズを加える必要がある。この結果は平凡であり、非常に低いユーティリティを持つ。ガウシアン相関定理 5.2 G(x, L) は ガ ウ シ ア ン 相 関 モ デ ル で あ り、s =∑x は x 上の集計クエリである。ラプラシアンメカニi∈[n] i

ズム M で、r = M(x) = s + z (z ∼ Lap(λ)) を生成する。任意の攻撃者 A = A(i, K) とその先祖 A′ = A(i, K′ ) に対し、次の不等式は成り立つ。

モデルに事前分布を追加し、全てのタプルの同時分布を定義することにより、攻撃者の仮定が弱くなる一方、ユーティリティを高めることができる。詳しくは、[11] を参考ください。

5. 6 正と負の相関
定義 5.1 にて、タプル間は正の相関を持つから、あるタプルℓA <= ℓA′ .

(25)があるので、クエリ結果はより大きく増加する。さらに、大量ゆえに、∀M > 0、次の式は自明である。

BDP LA (M; M ) <= BDP LA′ (M; M ).









1

2

3

4

の値が大きくなると、ほかの未知タプルの値も大きくなる傾向
な未知タプルはクエリ結果の大きい増加を引き起こすので、 弱

(26)


*H

*
Y
Y

*H

H

H
I

@
I @
I

H6@
6
H
6
 
 @
 @


HH

HH
@



12
13
14
23
24
34
H
*
YHH
YH
*
*
I 
@
I H6 H
@
I @
6
6 

 

H 
H@

@
H 124 H 134 @234
123 
H
  

Y
*
HH A
K 
 
A

H

12
34

C⊂
={1, 2, 3, 4}
図 3 C における階層的構造.

い攻撃者が大きいセンシティブを持つ。ゆえに、大きいプライ
バシー漏洩を持つ。ただし、実際のデータがいつも正の相関性を持つとは限らない。例えば、「二つのタプルの足し算は 100である」という相関性は「一つのタプルが大きくなると、別のタプルは小さくなる」と意味する。こんな場合、弱い攻撃者が大きいプライバシー漏洩を持つとは言えない。

Algorithm 1 プライバシー漏洩係数を計算する
input: L - ガウシアン相関行列
input: m - |U | (xU にあるタプルの数)
output: ℓ - 漏洩係数
1: function CalcLeakageCoefficient(L, m = 1)

定理 5.2 は、与えられた Lap(λ) に対し、ある攻撃者の BDPL

2:はその先祖の BDPL より小さいことを示唆する。ゆえに、最3:n ← SizeOf(L)< 2 then
if n =

4:

return ww0

も弱い攻撃者は最も大きいプライバシー漏洩を持つ。逆に、全ての攻撃者にたいして ϵ-BDP に満たすために、ラプラシアン

01

5:

end if6:

M
メカニズムの分散が λ >= (1 + ℓA ) ϵ (∀A) に満たさなければk ← ⌈ n+1⌉
2

7:

L1 ← L

ならないので、λ は少なくても λ0 = M(1 + maxA ℓA ) であϵ8:for i = k → 2 step −1 do

る。結局、最も大きい BDPL を持つ攻撃者を探せば良い。最9:L1 ← Combine(L1 , i, m)も大きい BDPL を持つ攻撃者は必ず n 個の弱い攻撃者 A(i, ϕ)

10:

m←m+1

のうちにあるから、命題 5.1 を用い、図 2 にあるパスを経て、

11:

end for12:ℓ1 ← CalcLeakageCoefficient(L1 , m)

13:

L2 ← L14:

for i = n → k + 1 step −1 do

15:と A(i′ , K ∪ {i} \ {i′ }) は異なる攻撃者であるが、それぞれのL2 ← Combine(L2 , i, m)

16:

m←m+1

相関行列は完全に同じである。C の包含関係に基づき、図 3 の17:

end forような階層的構造を作れる。結局、一番高い階層にある n 個

18:ℓ2 ← CalcLeakageCoefficient(L2 , m)の弱い攻撃者に対するプライバシー漏洩を評価し、そのうちか

19:

return max(ℓ1 , ℓ2 )各弱い攻撃者に対するガウシアン相関モデルを獲得できる。
一方、命題 5.1 は A(i, K) に関するガウシアン相関モデルはC = {i} ∪ K にしか関係ないことを示唆する。例えば、A(i, K)

ら最も大きいのを選べば良い。Algorithm 1 で、各弱い攻撃者

20: end function

A(i, ϕ) (∀i ∈ [n]) に対する漏洩係数を計算できる。
定理 5.3 Algorithm 1 の時間及び空間計算量はそれぞれ O(n3 )と O(n2 ) である。

6. 実

験

本節では、実験結果を示す。

▷ (命題 5.1)

▷ (命題 5.1)

6. 1 人工データ

理由は、このタプルはほかのタプルと最大の相関性を持つこと

以下に、与えられたタプル数 n に対し、ランダムにネットである。図 5(b) により、事前分布の増加とともに、漏洩係数がワーク (n × n の隣接行列 W) を生成する。まずは、W の各項

減少することは知られている。

を選ぶ。さらに、W は必ず対称行列 (wij ≡ wji ) であるので、選ばれた wij とその対称項目 wji を 1 に設定する。ゆえに、こ

ϭϬϬϬ
ϭϬϬ

>ĞĂŬĂŐĞŽĞĨĨŝĐŝĞŶƚ

d に対し、W の上三角の部分の n(n−1)
項目から一意に nd個22&ƌĞƋƵĞŶĐǇ;EŽĚĞŶƵŵďĞƌͿϭϬϬϬϬ

目 wij を 0 に初期化する。次に、与えられたネットワーク度数

ϭϬ

ʏсϬ͘ϭ
ϭ

ʏсϭ
ʏсϭϬ

Ϭ͘Ϭϭ

ϭ
ϭϬ

のネットワークの平均度数が d となる。異なるタプル数 n と度
プラシアン行列 L = D − W を計算し、最後に、事前分布を加ʏсϬ͘ϬϭϭϬϬ͘ϭ

ϭ

数 d に対し、このようなネットワークを生成し、それぞれのラ

ϭϬϬ

ϭϬϬ

ϭ

ϭϬϬϬ

ϭϬϬ

ϭϬϬϬ

ĞŐƌĞĞ

ĞŐƌĞĞ

(a). 度数分布.
図5ϭϬ(b). 漏洩係数 vs. 度数.

実験結果（ソーシャルネットワーク）.

える。具体的に、与えられた τ に対し、行列 T = τ · I を L に加える。すなわち、L̂ = L + τ · I。

7. お わ り に
本稿では、データが相関性を持つ場合、任意の攻撃者に対すʏсϬ͘Ϭϭ

ʏсϬ͘ϭ

ϴϬϬ
ŶсϮϬϬ
ϲϬϬ
ŶсϰϬϬ
ϰϬϬ
ŶсϲϬϬ
ϮϬϬ

ŶсϴϬϬ

Ϭ

ŶсϭϬϬϬ
Ϭ

ϮϬ

ϰϬ

ϲϬ

ϴϬ

ϭϬϬ

WƌŝǀĂĐǇůĞĂŬĂŐĞŽĞĨĨŝĐŝĞŶƚ

WƌŝǀĂĐǇůĞĂŬĂŐĞŽĞĨĨŝĐŝĞŶƚ

る差分プライバシーを考えた。まず、データに相関があり、か

ϲϬϬ

ϭϬϬϬ

ϱϬϬ
ϰϬϬ

ŶсϮϬϬ

ϯϬϬ

ŶсϰϬϬ

ϮϬϬ

ŶсϲϬϬ

ϭϬϬ

ŶсϴϬϬ

Ϭ

ŶсϭϬϬϬϬϭϮϬϮϬǀĞƌĂŐĞĚĞŐƌĞĞ

ϰϬ

ϲϬ

ϴϬ

ϭϬϬ

つ攻撃者が一部の知識しか知らない場合、差分プライバシーが満たすメカニズムはプライベートではない可能性がある問題にϭϮϬ

対し、ベイジアン差分プライバシーという新しい Puﬀerfish プǀĞƌĂŐĞĚĞŐƌĞĞ

ライバシー定義を提案した。さらに、ガウシアン相関モデルを
ϭϰ

ϭϮϬ
ϭϬϬ

ŶсϮϬϬ

ϴϬ
ŶсϰϬϬ
ϲϬ
ŶсϲϬϬ

ϰϬ
ϮϬ

ŶсϴϬϬ

Ϭ

ŶсϭϬϬϬ
Ϭ

ϮϬ

ϰϬ

ϲϬ

ϴϬ

ϭϬϬ

ϭϮϬ

WƌŝǀĂĐǇůĞĂŬĂŐĞŽĞĨĨŝĐŝĞŶƚ

WƌŝǀĂĐǇůĞĂŬĂŐĞŽĞĨĨŝĐŝĞŶƚ

提案することで、複雑な相関関係を持つデータを表現できる。

ʏсϭϬ

ʏсϭ
ϭϰϬ

最後に、ベイジアン差分プライバシーの計算は一般的に困難で

ϭϮ
ϭϬ

ŶсϮϬϬ

ϴ
ŶсϰϬϬ
ϲ
ŶсϲϬϬ

ϰ
Ϯ

ŶсϴϬϬ

Ϭ

ŶсϭϬϬϬ
ϬϮϬǀĞƌĂŐĞĚĞŐƌĞĞ

ϰϬ

ϲϬ

ϴϬ

ϭϬϬ

ϭϮϬ

あるという問題に対し、ベイジアン差分プライベートなメカニ
ズムを設計できる効率的なアルゴリズムを提案した。

ǀĞƌĂŐĞĚĞŐƌĞĞ

図 4 実験結果（人口データ）.

ベイジアン差分プライバシー漏洩は漏洩係数に一意に決められるので、Algorithm 1 を用い、異なる係数 (n、d と τ ) に対応するネットワークの漏洩係数のみを計算すればよい。漏洩係
数は図 4 で示された。水平軸はネットワークの平均度数であり、垂直軸はネットワークの漏洩係数の最大値 maxA ℓA である。nと τ はそれぞれタプル数と事前分布を表す。ネットワークの度数は大きければ大きいほど、そのプライバシー漏洩は大きい。
理由としては、大きい度数はタプル間の強い相関を意味する。
図 4 により、τ が極めて小さければ、漏洩係数は n に近づき、ラプラシアンノイズの分散はほぼ差分プライバシーの n 倍になり、出力のユーティリティは非常に低い。一方で、τ が大きくなれば、漏洩係数が小さくなり、ユーティリティは大きくなる。

6. 2 ソーシャルネットワークデータ
Stanford Large Network Dataset Collection [8] は 、Facebook の参加者を見回し、4039 個の頂点と 88234 個の辺を集計し、作成したネットワークデータである。図 5(a) で、度数の分布は表される。それの度数の最大値は 1045 である。
タプル i と j が隣接であれば、隣接行列 W の項目 wij 及びwji を 1 に設定し、隣接ではなければ、0 に設定する。さらに、事前分布をこの行列にに加える。すなわち、L̂ = D − W + τ · I。
図 5(b) では、異なるタプルの度数と事前分布に対し、評価された漏洩係数が示された。具体的に、各 τ に対し、タプルの度数と漏洩係数 ℓ を図 5(b) で比較する。この計算結果をみると、最大の度数 (1045) に対応するタプルは最大の漏洩係数を持つ。

文

献[1] C. Dwork, F. Mcsherry, K. Nissim, and A. Smith. “Calibrating noise to sensitivity in private data analysis.” In TCC,
pages 265-284. Springer, 2006.
[2] J. Gehrke, M. Hay, E. Lui, and R. Pass. “Crowd-blending
privacy.” In ECRYPTO, pages 479-496. 2012.
[3] J. Gehrke, E. Lui, and R. Pass. “Towards privacy for social
networks: A zero-knowledge based denition of privacy.” In
TCC, pages 432-449, 2011.
[4] M. Hay, C. Li, G. Miklau, and D. Jensen. “Accurate estimation of the degree distribution of private networks.” In
ICDM, pages 169-178, 2009.
[5] X. He, A. Machanavajjhala, and B. Ding. “Blowsh privacy:
Tuning privacy-utility trade-os using policies.” In SIGMOD,
pages 1447-1458, 2014.
[6] D. Kifer and A. Machanavajjhala. “No free lunch in data
privacy.” In SIGMOD, pages 193–204, 2011.
[7] D. Kifer and A. Machanavajjhala. “Puﬀerfish: A framework
for mathematical privacy denitions.” ACM Trans. Database
Syst., 39(1):3:1–3:36, Jan. 2014.
[8] J. Leskovec and A. Krevl. “SNAP Datasets: Stanford large
network dataset collection.” http://snap.stanford.edu/data,
June 2014.
[9] G. Miklau and D. Suciu. “A formal analysis of information
disclosure in data exchange.” In SIGMOD, pages 575-586,
2004.
[10] V. Rastogi, M. Hay, G. Miklau, and D. Suciu. “Relationship privacy: output perturbation for queries with joins.”
In PODS, pages 107-116, 2009.
[11] B. Yang, I, Sato, and H. Nakagawa. “Bayesian Diﬀerential
Privacy on Correlated Data” In SIGMOD, pages 747-762,
2015.
[12] J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, andX. Xiao. “Privbayes: Private data release via bayesian networks.” In SIGMOD, pages 1423-1434, 2014.