スライド 1

個人情報保護が叫ばれる
複数の企業、組織が協力し
ないと日本はどんどん遅れ
ていく
欧米では、性別や人種に
よる差別が起きないよう
なデータマイニングにも
焦点が当たり始めている
2002年くらいから伸びてきた分野です。最
近は機械学習、データ工学系の学会で相当
数の論文が発表されています。
こういうご時勢ですから、ひょっとすると
重要な技術要素になるかもしれません。
プライバシ保護データマイニング
(PPDM)
東京大学
中川裕志
PPDMの基礎概念
２種類のＰＰＤＭ
摂動法



データベースに雑音を加え、利用者がデータベースに質
問しても真のデータベースの内容が利用者には取得でき
ないようにする
プライベートな情報は漏れないようにしたいが、一方で
できるだけ正確なデータマイニング結果も得たい！
暗号法


3
データ保持者をパーティと呼ぶ。複数のパーティが自分
のデータは公開鍵暗号で暗号化する。当然、他のパー
ティには自分のデータは知られない。暗号化したまま何
らかの計算をしてデータマイニングの結果だけは全パー
ティが共有する。
摂動法
摂動法に関して
2002年から2006年ころまでに導入された概念




摂動法によるPPDMを始めた動機
k-匿名性（k-anonymity）
l-多様性（l-diversity）
t-closeness
動機

複数の組織がプラバイシーに係わるクリティカルなデータ
(sensitive data)を持ち、場合によっては公開している


microdata の保護のため sanitized（不要部分の削除など）



microdata (vs. aggregated macrodata) と呼ばれる詳細データが解析
やマイニングに利用される状況である。（ＵＳでは公開は法令で義
務化 )
例えば、explicit identifiers (Social Security Number, name, phone #)
の削除
しかし、それで十分か？
否! link attacksの脅威

公開データからプライバシー情報を推測できる可能性あり
link attack の例

Sweeney [S01a] によれば、Massachussetts州知事の医療記録
が公開情報から特定可能


MA では、収集した医療データを sanitize して公開している（下図）
(microdata) 左円内
一方、選挙の投票者名簿は公開右円内
• 両者をつきあわせると
•
6 人が知事と同じ生年月日
うち3 人が男
うち1 人が同じzipcode
• 1990年の the US 1990 census dataによれば
[S01a]より
– 87% の人が (zipcode, 性別, 生年月日)によって一意特定可能
microdataのプライバシー

microdataの属性



explicit identifiers は削除
quasi identifiers （QI＝擬ID)は個人特定に利用可能
sensitive attributes は sensitive 情報を持つ
identifier
quasi identifiers
sensitive
名前
誕生日
性別
Zipcode
病名
太朗
21/1/79
男
53715
風邪
花子
10/1/81
女
55410
肺炎
光子
Sanitize!
1/10/44
女
90210
気管支炎
次郎
21/2/84
男
02174
ねんざ
明菜
19/4/72
女
02237
エイズ
プライバシー保護の目標は、個人をsensitive
情報から特定できないようにすること
k-匿名性（k-anonymity）


k-匿名性によるプライバシー保護, Sweeney and Samarati
[S01, S02a, S02b]
k-匿名性: 個人を他のk-1 人に紛れさせる



実現方法



つまり、公開された microdata においては、Quasi Identifier:QI の値
が同一の個人は少なくともk 人存在することを保証
よって、link attackでも個人特定の確率は 1/k
一般化 and 抑圧
当面はデータの値の perturbation（摂動）は考えない。摂動は、後に
差分プライバシーのところで活用されることになる
プライバシーとデータマイニングにおける有用性のトレードオ
フ

必要以上に匿名化しない
k-匿名性の例
匿名化手法
 一般化


例えば、対象分野のデータは抽象度によって階層化されているなら、
上の階層のデータを公開
抑圧

特異性のあるデータ項目は削除
original microdata
誕生日
性別
Zipcode
21/1/79
男
53715
10/1/79
女
55410
1/10/44
女
90210
21/2/83
男
02274
19/4/82
男
02237
2-anonymous data
group 1
誕生日
性別
Zipcode
*/1/79
人
5****
*/1/79
人
5****
女
90210
*/*/8*
男
022**
*/*/8*
男
022**
suppressed 1/10/44
group 2
一般化を行う束： lattice
K-anonymity
Z2 ={537**}
Z1 ={5371*, 5370*}
B1 ={*}
S1 ={Person}
Z0 ={53715, 53710, 53706, 53703}
B0 ={26/3/1979, 11/3/1980, 16/5/1978}
S0 ={Male, Female}
全Qiに対して一般化を行う束を構成
<S1, Z1>
<S0, Z2>
<S1, Z0>
<S0, Z1>
一般化
more
<S1, Z2>
<S0, Z0>
性別
誕生日
zipcode
less
目的
k-anonymityを満たしつつ、最小限の
一般化を行う
[1, 2]
[1, 1]
[0, 2]
[1, 0]
[0, 1]
[0, 0]
一般化のために束構造を使う
incognito [LDR05]
単調性の利用
<S1, Z2>
<S1, Z1>
(I) 一般化の性質 (~rollup)
<S0, Z2>
if k-anonymity があるノードで成立
then そのノードの任意の上位ノードでも成立
e.g., <S1, Z0> k-anonymous  <S1, Z1> も <S1, Z2> k-anonymous
<S1, Z0>
<S0, Z1>
<S0, Z0>
<S,Z,B>を全部使って描くと複雑
すぎるので<S,Z>のみ
(II) 部分集合の性質 (~apriori)
if あるノードでQI の属性の集合が k-anonymity でない
then その集合を含む集合でもk-anonymity でない
e.g., <S0, Z0> k-anonymous でない
 <S0, Z0, B0> and <S0, Z0, B1> k-anonymous でない
分割によっては匿名化できない例
not 2-anonymous
incognito の例
2 QI 属性, 7 このデータ点
zipcode
sex
2-anonymous
group 1
w. 2 tuples
group 2
w. 3 tuples
group 3
w. 2 tuples
一般化の良い例、悪い例[LDR05, LDR06]
各次元を順次一様に
一般化
各次元を個別に一般化
多次元まとめて一般化
mondrian [LDR06]
topdown [XWP+06]
incognito [LDR05]
一般化の強さ
mondrian
[LDR06]
2-anonymous
グループの周囲長を利用してグループ化[XWP+06]:
まずい一般化
良い一般化
長い箱
正方形に近い
データマイニングの精度が
低い
データマイニングの精度が
高い
Topdown [XWP+06]
split algorithm
最も遠い２点を種にして開始
• これはヒューリスティックではある
• 種から２グループへ成長させる
各データ点を調べ、近くの種（あるいは種から
成長したグループ）に周囲長が最小になる
点を追加して新しいグループとする
右図では、全ての点は、元々は赤と緑に分離さ
れていなかったが、アニメーションに示すよ
うな流れで2グループに分離された。
外部DBを逆に利用

外部データは通常攻撃側が使うが、これを逆利用して役立てたい

join k-anonymity (JKA) [SMP]
3-匿名
マイクロデータ
k-匿名
合併
公開データ
合併 3-匿名
anonymous
合併されたマイクロデータ
JKA
x3
x3
x3
k-匿名性の問題点
id
1
2
3
4
5
6
7
8
9
10
11
12

k-匿名性の例

Homogeneityによる攻撃: 最終グループは全員 cancer

背景知識による攻撃: 第1グループで、日本人は心臓疾患にかかりにくいことが知
られていると。。。
microdata
国籍
Zipcode 年齢
ロシア
13053
28
13068
29
US
日本
13068
21
13053
23
US
インド
14853
50
ロシア
14853
55
14850
14850
13053
13053
13068
13068
47
49
31
37
36
35
US
US
US
インド
日本
US
病名
心臓病
心臓病
感染症
感染症
がん
心臓病
感染症
感染症
がん
がん
がん
がん
id
1
2
3
4
5
6
7
8
9
10
11
12
4-anonymous data
国籍
Zipcode 年齢
130**
<30
∗
130**
<30
∗
130**
<30
∗
130**
<30
∗
1485*
≥40
∗
1485*
≥40
∗
1485*
≥40
∗
1485*
≥40
∗
130**
3∗
∗
130**
3∗
∗
130**
3∗
∗
130**
3∗
∗
病名
心臓病
心臓病
感染症
感染症
がん
心臓病
感染症
感染症
がん
がん
がん
がん
l-多様性
[MGK+06]

各グループにおいて sensitiveなデータの値がうまく
管理されていることを目指す
 homogeneity 攻撃を防ぐ
 背景知識攻撃を防ぐ
l-多様性 (簡単な定義)
あるグループが l-多様性を持つとは、
そのグループ内では少なくともl種類の
sensitive なデータ値が存在する
• group内にl種類のsensitiveな値があり、できるだけ均等に出現することが
望ましい。
名前
年齢
性別病名
一郎
65
男
インフルエンザ
次郎
30
男
胃炎
三子
43
女
肺炎
四郎
50
男
インフルエンザ
五子
70
女
肺炎
六夫
32
男
七子
60
八郎
九美
病名の頻
度順に並
んだDB
インフル
六夫
インフル
七子
インフル
四郎
インフル
三子
肺炎
インフルエンザ
五子
肺炎
女
インフルエンザ
八郎
肺炎
55
男
肺炎
40
女
鼻炎
一郎
インフル
六夫
インフル
七子
インフル
四郎
インフル
三子
肺炎
五子
肺炎
八郎
肺炎
次郎
胃炎
九美
鼻炎
21
一郎
次郎
胃炎
九美
鼻炎
algorithm
•sensitive values を bucket
に割り当て
•大きい順にl個のbucketから
データを引き出してグループ
を形成
3つのグループはいずれも3種類の病名(sebnsitive data)を含む：l-diversity
Anatomy

グループ化したデータをQIの表とsensitiveデータの
表に分割 3-diversity
名前：
匿名化
する
QI:
年齢
QI：
性別
グルー
プID
一郎
65
男
１
七子
60
女
三子
43
八郎
グループ
ID
病名
頻度
１
インフル
２
１
１
肺炎
２
女
１
１
鼻炎
１
55
男
１
２
インフル
２
九美
40
女
１
２
肺炎
１
六夫
32
男
２
２
胃炎
１
四郎
50
男
２
五子
70
女
２
次郎
30
男
２
22
これらの2つの表から
データマイニングする
t-closeness



l-多様性があっても、ある属性がaの確率99%,bの確率
1%というように偏りが激しいと、プライバシーは危険
２つのグループ（上記a属性のグループとb属性のグルー
プ）は、sensitive データの分布における距離と、全属性
の分布における距離が t 以下であるとき、 t-closeness
である。
上記の分布間の距離としては、属性を各次元としてにお
いてEarth Mover’s distance(EMD)を用いる
P   p1 , p2 ,.., pm , Q  q1 , q2 ,..,qm , dij  distancebetween pi and q j : given
fij  flow bewteen pi and q：　j
  d f 最適化したのが EMD
EMDP, Q   min   d f
fijを変化させて
f ij
s.t.
fij  0
 
m
23
i 1
m
m
i 1
j 1
m
m
i 1
j 1
ij ij
ij ij
1  i  m,1  j  m
,
pi   j 1 fij   j 1 f ji  qi
f  i 1 pi  i 1 qi  1
j 1 ij
m
m
m
m
m
攻撃を断ち切るにはをどこか断ち切れば良い
micro data
公開された外部
データベース
k-anonimity
microdata と公開外部データとの
突き合わせを狙う攻撃
背景知識
l-diversity
t-closeness
背景知識を用いたQuasi ID とsensitive
dataの突き合わせを狙う攻撃
個人情報流出
24
k-anonymity, l-diversity, t-closenessの参考文献









[LDR 05]LeFevre, K., DeWitt, D.J., Ramakrishnan, R. Incognito: Efficient Full-domain kAnonymity. SIGMOD, 2005.
[LDR06]LeFevre, K., DeWitt, D.J., Ramakrishnan, R. Mondrian Multidimensional kAnonymity. ICDE, 2006.
[XWP+06] Xu, J., Wang, W., Pei, J., Wang, X., Shi, B., Fu, A., Utility-Based Anonymization
Using Local Recoding. SIGKDD, 2006.
[MGK2007]MACHANAVAJJHALA,A. KIFER,D. GEHRKE,J. and
VENKITASUBRAMANIAM, U. l-Diversity: Privacy Beyond k-Anonymity. ACM
Transactions on Knowledge Discovery from Data, Vol. 1, No. 1, Article 3,2007
[S01] Samarati, P. Protecting Respondents' Identities in Microdata Release. IEEE TKDE,
13(6):1010-1027, 2001.
[S02a] Sweeney, L. k-Anonymity: A Model for Protecting Privacy. International Journal on
Uncertainty, Fuzziness and Knowledge-based Systems, 2002.
[S02b] Sweeney, L. k-Anonymity: Achieving k-Anonymity Privacy Protection using
Generalization and Suppresion. International Journal on Uncertainty, Fuzziness and
Knowledge-based Systems, 2002.
Ninghui Li,Tiancheng Li,Venkatasubramanian, S. “t-Closeness: Privacy Beyond k-Anonymity
and –Diversity”. ICDE2007, pp.106-115, 2007.
[SMP] Sacharidis, D., Mouratidis, K., Papadias, D. k-Anonymity in the Presence of External
Databases（to be appeared)
25

ここまで述べてきたように、公開された複数のデー
タベースを串刺しする攻撃への対策は、t-closenessに
至って、一段落した感あり。

攻撃者は、データベースへの質問者の場合を想定
攻撃者の事前知識に左右されることなく、データ
ベースのプライバシー保護の強度を数学的に制御で
きる概念として、2006年以降、マイクロソフトの
Cynthia Dworkが中心になって提案した差分プライバ
シーがトレンドとなった。

26
差分プライバシーの必要性
病院ＡのＤＢ at
10:30am
インフル 10名
10+1=11名
太郎が来院 at
10:31
病院ＡのＤＢ at
10:40am
インフル 11名
11-2=10名
ＤＢにインフル患者数を質問し、10:30am で１０，10:40am で１１と分か
ると、太郎の来院を知っていた人は太郎がインフルだと分かってしまう。
 質問への結果に雑音加算すると回避できる。
27
DIFFERENTIAL PRIVACY
差分プライバシー

同じドメインのデータベース：D1,D2要素が1個だけ異なる
Ｄ２
Ｄ１
α
１要素だけ違う
任意のD1,D2において、両者を質問 f に対して区別できない
結果を返す  データベースの内容が利用者に同定しにく
いという相対的安全性：差分プライバシー
 X=D1 or D2 に対してYをうまく決めて
 t=f(X)+Y  p(t-f(D1)) ≦ eε p(t-f(D2))
pt  f D1
 あるいは
log
  としたい。（ε-privacy)



pt  f D 2
このようなYの分布はラプラス分布で実現
28
 t
1
pがラプラス分布 : Lapalace  
exp  
2
 
 t  f ( D1) |  | t  f ( D 2) 
p(t  f ( D1)) exp t  f ( D1) /  



 exp
p(t  f ( D 2)) exp t  f ( D 2) /  



 f ( D1)  f ( D 2) 
  exp f ( D1)  f ( D 2)   expp 
 exp



p  max f D1  f D1
D1, D 2
 p 
 p 
 p Y   p t  f ( X )   Laplace

Y

t

f
(
X
)
~
Laplace









パラメータ ε の調整
29
右側のほうがよ
り安全
どんな関数 f がこの枠組みに入れるのかが研究課題
差分プライバシーの弱点
ＤＢへ同じ質問（インフル患者数）を
繰り返すと
９
病院ＡのＤＢ at
10:30am
インフル 10名
１２
８
１１
平均すると (9+12+8+11)/4=10
同じ質問を繰り返してもε-privacyが保てるようにする
には、非常に大きな雑音を加算しないとならない
データマイニング精度の低下
30
Differential Privacy の文献



C. Dwork. Differential privacy. In ICALP, LNCS, pp.1–12,
2006.
C. Dwork. Dierential privacy: A survey of results. In
TAMC, pp. 1-19, 2008.
Cynthia Dwork, Frank McSherry, Kunal Talwar. “The
Price of Privacy and the Limits of LP Decoding”.
STOC’07, pp.85-94, 2007
31
暗号化
準同型性公開鍵暗号を用いたPPDMプロトコル
32
プライバシ保護データマイニングの目的
Alice
Bob
XA
XB
XA ∪ XB




Alice は彼女のデータベースを Bob に開示したくない．
Bob も彼のデータベースを Alice に開示したくない．
ただし，結合されたデータ XA∪XB についてデータマイニ
ングや統計処理を実行し，その結果のみを知りたい．
PPDMではAliceやBobを「パーティ」と呼ぶ。
33
プライバシー保護データマイニング(PPDM)では
 自分自身のデータを持つ多数のパーティが、各々の
データを他のパーティに知られることなく、全パー
ティのデータを統合的に利用したデータマイニング
結果を入手すること.
 暗号技術に基づく PPDM 実現が目標.
 このようなPPDMには多数の応用分野がある



多数の病院が協調して疫病の感染ルート追跡
多数の金融機関が協調して個人の信用情報を得る（与
信）
競合数社が共同して市場調査
暗号学的アプローチ


データマイニングを複数の分散計算に分割．
セキュリティプロトコルや暗号学的ツールを組み合わせて，
それぞれの計算をプライバシを保護して実行．
 準同型性公開鍵暗号により，暗号化されたデータ同士の加
算や乗算を組み合わせた計算が可能．

Epk(m)をメッセージmを公開鍵pkで暗号化したものとすると
Epk(m1)* Epk(m2)= Epk(m1+m2)
Alice
XA
Bob
XB
暗号化
暗号化
XA
XB
暗号プロトコルに
よる関数の評価
35
暗号法の参考文献
プライバシー保護データマイニング
J.ヴァイダヤ、C.W.クリフトン、Y.M.ズー著
シュプリンガージャパン 2010
(原著は 2006）
 計算機科学、機械学習の国際会議としては、
KDD,ICML,ICDM,などに論文が発表されている。

36
準同型性公開鍵暗号による平均値の計算プロトコル
A knows x and m, B knows y and n
 Both A and B knows public key : pk
 A only knows secret key: sk

A
B
 Epk(x) , Epk(m)


B generates random z

Epk(y)z =Epk(yz), Epk(n)z =Epk(nz),

Epk(m)z =Epk(mz), Epk(x)z =Epk(xz),


Epk(yz)xEpk(xz)=Epk(z(x+y))


Epk(mz)xEpk(nz)= Epk(z(m+n))
Dsk( Epk(z(x+y))) /Dsk( Epk(z(m+n)) )
=z(x+y)/z(m+n)
= (x+y)/(m+n)
 (x+y)/(m+n)
Both A and B knows (x+y)/(m+n)
Note: A couldn’t know z nor y because couldn’t factor out z or y from z(x+y)
大きな数の因数分解の不可能性
内積をプライバシー保護しつつ計算し、結果を
乱数としてシェアを計算するプロトコル．



Alice
Bob
入力
xA
yB
出力
(xA)T yB - rB
rB
ここで rB は，Bob しか知らない乱数である．
準同型性公開鍵暗号を用いれば，実現できる．
シェアしているのは乱数だが、足せば内積が得られる
Alice
Alice
公開鍵
公開鍵
pk を生成．
pk を生成．
ci = cEnc
Enc
(xi)pk(i(x=
1,…,d)
= 1,…,d)
i = pk
i) (i
Bob
Bob
A)T yB
wwi i==cciyiiy(ii (i==1,…,d)=Enc((x
1,…,d)
ww==ΠΠi=1i=1d dwwi i
Decsk(w’ ) = (xA)T yB – rB
乱数
乱数rBrBを生成．
を生成．
w’
w’==ww**Enc
Encpkpk(-r
(-rBB) )
38
付録：1-out of-2 Oblivious Transfer protocol：ＯＴ


n- out of –N も同様
Alice will send Bob one of two messages. Bob will receive one, and Alice will not
know which.
Alice
(m1, m2)
(pk1, sk1), (pk2, sk2)
Bob
pk1, pk2
Aliceはpk1,pk2のどちら
でencryptされたか分からない。
Dsk1( Epk1(K))=K, Dsk2(Epk1(K))=G
EK(m1), EG(m2)
m1を受け取ると決める
K:symmetric key,
Epk1(K)
D K(EK(m1))= m1, DK(EG(m2))
データマイニング



上記のプライバシー保護計算のプロトコルを基礎に、
より高度なデータマイニングアルゴリズムを実現す
る。
全データはデータ保持者であるパーティ毎への分割
は水平分割と垂直分割の2種類あり（次ページ）
水平、垂直分割データにおけるEMアルゴリズム、
K-meansなどを実現するプロトコルが知られている。
40
データ分割のモデル垂直分割と水平分割
エンティティ
属性１
属性２
属性３
１
a
A
α
２
b
B
β
３
c
C
γ
４
d
D
δ
５
e
E
ε
６
f
F
ζ
７
g
G
η
水平分割
パーティ１
エンティティ
属性１
属性２
属性３
１
a
A
α
２
b
B
β
パーティ２
垂直分割
パーティ１
パーティ２
パーティ３
エン
ティ
ティ
属性１
エン
ティ
ティ
属性２
エン
ティ
ティ
属性３
エンティティ
属性１
属性２
属性３
１
a
１
A
１
α
３
c
C
γ
２
b
２
B
２
β
４
d
D
δ
３
c
３
C
３
γ
４
d
４
D
４
δ
パーティ３
エンティティ
属性１
属性２
属性３
５
e
５
E
５
ε
５
e
E
ε
６
f
６
F
６
ζ
６
f
F
ζ
７
g
７
G
７
η
g
G
η
７
41
水平分割におけるK-means





パーティ数はｒ
パーティi のm番目のデータの属性j j=1,..,J(J次元）
のデータをdi×m-j
J次元のベクトル空間の距離はユークリッド距離など適
当なものを用いる
k番目のクラスタの属性j の値をγkj クラスタ数はK
γkjの初期値はγkj0
γkはクラスタkの重心
目的：K個のクラスタのγkjのK-meansの計算結果を全パー
ティが知る。ただし、個別のパーティのデータは他へは漏
れない。
42
パーティ１とパーティｒは特殊
 Step
1
パーティ１は乱数Rbを生成し、パーティrだけに送信
 Step
2
パーティrは公開鍵pkを作り全パーティに送る。秘密
鍵skは自分だけで保持。
43

Step 3
for all m (in パーティ1)
｛パーティ1は自分のデータにd1×m に対してクラスタ中心γk が一
番近いクラスタのJ次元ベクトルΓkJにd1×m を加算し、カウント
Ckにも1を加算｝

以上によって生成された ΓkJとCkはパーティ1がクラスkにもっとも
近いデータの属性の総和と、そのようなデータの個数
次は自分のデータを隠す乱数Rbの加算と暗号化をし、その結果を
パーティ２に送る

for j=1,J
Epk[Γkj+Rb]  パーティ２に送る
end for
Epk[Ck+ Rb」パーティ２に送る
44
パーティ１は1番目であるが、
それが保持している情報は
Rbによって保護される
 Step
4
 for i=2からr-1
 パーティi-1から受け取ったJ＋１種のデータを
Epk[Γ’kj+Rb]（j=1,..,J ）、 Epk[Ck’+Rb] とする


Γkj=0. Ck=0
パーティiは自分のデータにdi×m に対してクラス
タ中心γk が一番近いクラスタのJ次元ベクトルΓkJ
にd1×m を加算し、カウントCkにも1を加算
 Epk[Γ’kj+Rb]E[Γkj ]
=Epk[Γ’kj+ Γkj +Rb]（j=1,..,J ）、
Epk[Ck’+Rb]E[Ck]=Epk[Ck’+Ck+Rb]
を計算してパーティi+1に送る
45
 Step
5 パーティrにおいての操作
 まず、Step
4と同様に自分のデータを用いて
Epk[Γ’kj+ Γkj +Rb]（j=1,..,J ）、
Epk[Ck’+Rb]E[Ck]=Epk[Ck’+Ck+Rb]
を計算
 秘密鍵skでこれらを復号し、Rbを差し引いた上で比
をとる。すなわち
 Dsk
Epk[Γ’kj+ Γkj +Rb]－Rb=Σパーティ１からr Γkj=Akj
 Dsk
Epk[Ck’+Ck+Rb] －Rb=Σパーティ１からr Ck=Bk
 Akj／Bk＝ γkj すなわち次元jにおけるクラスタkの属性の
平均値がわかった。これを全パーティに送信
46
パーティrは平均値以外には、他の個々の
パーティの情報は得ることができない。
 Step
6
Step 5でパーティrから送られたγkjを新たなクラスタk
の中心の属性jの値として、Step 3, 4, 5をγkjが収束するま
で繰り返す。
γkjの収束判定はパーティ1かrが直
前のγkjと比較して行えばよい
47
垂直分割におけるK-means

J.Vaidya et.al. Privacy Preserving k-means clustering over
vartically partitioned data. KDD2003, 206-215, 2003

垂直分割の場合は、各パーティのデータを保護する
ために水平分割の場合とは異なる工夫が必要

パーティ数はr  各データはr個の属性値からなる
クラスタ数はK
総データ数はN
パーティiはN個のデータ y(i)n (n=1,..,N) を持つ
（データの属性は1個）


48
パーティ毎のデータ保持状況



N
枚
あ
る
クラスタk (k=1,..,K)は属性i (i=1,..,r)に対してそのクラス
タに属すると想定されるデータの平均値μkiを持つ
パーティiが保持しているN個のデータはyniという値を持つ
パーティiはデータ毎に属性iの値をクラスタkの平均値との
差 X(i)nk= y(i)niーμkiを成分とするベクトルを持つ（下図参
照）

データi
パーティ１
… パーティi
クラスタ１ X(i)11
…
パーティr
X(i)r1
…..
クラスタk
X(i)nk= y(i)niーμki
…..
クラスタK
49
X(i)1k
X(i)rk
分散データに対するK-means
各パーティi において以下を繰り返す


1.
2.
3.
4.
5.
6.
7.
50
ただし、パーティiが保持しているのは yni (n=1,..,N)とμki
for n=1,N
for k=1,K
X(i)nk= yniーμki (前頁の行列の成分の計算)
end for
SecureNearestCluster: n番目のデータの一番近いクラ
スタを求めるこの作業を各パーティのデータを保護しつつ行う
アルゴリズムを次のページ以降で述べる
end for
6.までで各データに一番近いクラスタが求まったら、
それを用いてクラスタkに対応する属性iの平均値μki を
再計算する
SecureNearestCluster アルゴリズム







Key Idea
順同型公開鍵暗号 E[]、D[]を使う
乱数Vを利用して各パーティのデータの流出を防ぐ
距離の比較計算は比較結果だけを得て公開
クラスタの順番を秘匿された置換πで隠す
特別な機能を果たす3パーティをP1,P2,Prとする
全パーティ 1,..rのデータを総合的にみて、データn （値
はyni (i=1,..,r))にもっとも近いクラスタknを求める


kn  arg min i1 Xi nk
k 1,..,K
r

次ページ以降ではnは省略する。
51
SecureNearestCluster
3
アルゴリズム-1
つの特別パーティを P1, P2 , Prとする
はK次元の乱数ベクトルVi をr個（i=1,..,r)生成。
r
T
 ただし
Vi  0  0  0
 P1

i 1
はK次元の乱数ベクトルの各要素を置換する置換πを
生成
 P1
SecureNearestCluster プロトコルのstage1
各パーティi(i≠1,r)とパーティ１の間で以下の計算を行う
V  V 1,VN  , X i   X i 1, , X i n,  , X i N  T
P1には暗号化に
よりX(i)の内容は
わからない
T
①　EX i   EX i 1,, EX i N 
T
X i 
V ,
P1
Pi
②を復号し  ( X i   V )
②　 (EX i   V )  EX i 1  V 1,, EX i N  VN 
T
準同型性暗号: E[x]*E[y] = E[x+y]
Piには置換πと
乱数Vの加算に
より、元のデー
タとの対応はわ
からない
SecureNearestCluster プロトコルのstage2
stage1でパーティiが得た結果をパーティrに送りX(i)の総和を得る
この結果とP2のデータをsecureに比
較して目的のクラスタを求める
P2
E2 X 2
 X i   Vi
 ( EX 2  V2 )
Vi , 
P3
i 2
P3
P1
Pr
EX r  1
 ( EX (r  1)  Vr 1 )
Stage 1
  X r  1  Vr 1 
Pr-1
Pr-1
EX r 
EX (r )  Vr 
 ( X 1  V1 )
Stage 2
SecureNearestCluster プロトコルのstage3
stage2の結果とP2のデータを総合して、PrとP2の間で最も近いク
ラスタを求めるプロトコル


n-1番目まで調べたところで、X(i)のベクトルのm番
目に対応するクラスタがデータiに一番近いと想定さ
れているとしよう。
この状況で、次のn番目のクラスタがそれより近いか
どうかを判定できればよい

r
i 1
X i   Vi  i 1 X i 　 i 1Vi  0
r
r
 i 1 X i m  Vi  i 1 X i n  Vi を調べる。
r
r
ただし、 P rが知っているのは
また P2はX 2n  V2 nとと
55

r
i 1

i2
X i n  Vin X i m  Vimを知っている
データnに一番近いクラスタのindexを求める

Prは乱数Raを生成


Epk i  2 X i n  Vin Epk X 2 n  V2 n 

 Epk i 1 X i n  Vin


r
Epk i 1 X i n  Vin
 Epk

r

r
i 1

 Epk

r
i 1
 
X i n  Vin Ra

P2は公開鍵pkと秘密鍵skを作
り
pkをPrに送る

EpkX 2n  V2 nと

Ra
Epk i 1 X i m  Vim
r


Ra
 
X i m  Vim Ra


r
r
i 1
X i n  Vin Ra
 X i n  Vin  1 or  1
 X i m  Vim
r

r

X i m  Vim Ra
i 1
56

Epk i 1 X i m  Vim
をPrに送る
skで復号
skで復号
これらを割り算しそれが１よ
り小さければ最小値を更新
i 1
r
i 1




上記までで求まったクラスタindexはまだ置換された
まま。
そこでこれをP1に送りπ－１を作用させ、真のindexを
求める
このようなstage 1,2,3,4の操作をN個すべてのデータ
に対して行うと、各データがどのクラスタに属する
かわかる。
この後、Piはi番目の属性のクラスタ毎の平均値を
ローカルに計算できる。
57
ややこしい！



以上が垂直分割データに対するプライバシー保護Kmeansアルゴリズムだが大変にややこしい。
しかも、暗号化、復号の回数も多く、速度は遅い。
このようなPPDMプロトコルが実用になるには、もう一歩
のbreak throughが必要のようだ
 ここまで述べた暗号技術を用いるPPDMプロトコルに
おいてはさらに結託攻撃が強敵
 結託攻撃とは t 個のパーティが結託して、別のパー
ティのデータを入手すること
 定義 t-private ：上記の結託攻撃を防げるなら、PPDM
は t-private という.
 総パーティ数= Mのとき, M-1-private なら full-private
と呼ぶ.
 full-private は PPDM の安心な利用の試金石.
59
 これまで提案された

PPDM は full-private ではない
Works Methods
Methods
Party
Anti-Collusion
S. Jha 2005
K-Means
2
NA
M. Ozarar 2007
-Means
Multi
×
J. Vaidya 2004
JNaive Bayes
Multi
×
J. Vaidya 2003
K-Means
Multi
×
PPDM の実現が我々の目標。具体的には
full-private な secure dot-products calculation, secure
ratio calculation, secure comparison を提案した.
 full-private

Bin Yang, Hiroshi Nakagawa, Issei Sato, Jun Sakuma.
“Collusion-Resistant Privacy-Preserving Data Mining”. 16th
ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining,(KDD2010) pp.483-492 ,
Washington, DC , USA, July 25-28 , 2010
60
PPDMに関する最近の研究の動向
KDD2010より
分類

必ずしも信用できないクラウドサーバ計算を任せる場合
の元データのプライバシー維持



Privacy-Preserving Outsourcing Support Vector Machines with
Random Transformation
k-Support Anonymity Based on Pseudo Taxonomy for Outsourcing of
Frequent Itemset Mining
差分プライバシー


Data Mining with Differential Privacy
 Discovering Frequent Patterns in Sensitive Data
Versatile Publishing for Privacy Preservation
 これらは摂動法
 これは暗号法

暗号技術による分散データからのマイニング

62
Collusion-Resistant Privacy-Preserving Data Mining
必ずしも信用できないクラウドサーバ計算を任
せる場合の元データのプライバシー維持
(1)Privacy-Preserving Outsourcing Support Vector
Machines with Random Transformation


信用できない外部のサーバにSVMをoutsourcingするときに、
元データを推定されないようにKernelをランダム変換するアル
ゴリズム
 従来は、教師データからランダムに選んだ小さな部分で
SVMの学習をする方法。そこそこの精度。ただし、テスト
においては外部サーバにデータを知られてしまう。
そこで新規提案
データの持ち主
外部サーバ
教師データ
摂動SVM
分類器
ランダム変換
テストデー
タ
ランダム変換
摂動教師
データでSVM
学習
摂動教師
データ
64
外部サーバ
予測ラベル
データの持ち主
学習
摂動データで
学習したSVM
で予測
摂動テスト
データ
予測
Privacy-Preserving Outsourcing Support Vector
Machines with Random Transformation


まず、準備としてm個の教師データのうちm’(<<m)個の
部分集合だけを用いるReduced SVMを説明。本来は少
ないメモリでSVMを行うアルゴリズム
Y.-J. Lee and O. L. Mangasarian. RSVM: Reduced support vector machines.
In Proceedings of the 1st SIAM International Conference on Data Mining
(SDM), 2001.







データはm個。１つのデータはn次元のベクトル。
y=分類の誤り許容度（ソフトマージン）の列ベクトル、
γ=原点からの距離
A=教師データ(n×m行列）
Dii=1 if 分類 iが正解 e=－1 if 不正解.
最適化の定式化
eは全要素が１の列ベクトル
65
if i≠j then Dij=0
概念図
w
分離平面
x’w=γ
Ａ+
Margin =2/||w||2
xTwーγ＝1
xTwーγ＝ー1
66
Ａ-
図のように線形分離できないときは、yiというソフ
トマージンのパラメータを使って制約を以下のよう
に緩和
x T w    yi  1　for　x T  Ai and Dii  1

x T w    yi  1　for　x T  Ai and

Dii  1
最適化問題は以下のようになる

1 T
T
minm  n 1 y y  w w   2 
 w , , y R
2
2
s.t.　D  Aw  e   y  e
m個の
xTwーγ＝1
xTwーγ＝ー1
に対応する制約式群
y  0
 制約なし最適化に書き直すと
minn 1
 w , R
67

2
e  D  Aw  e 
2
2
1 T
 w w   2 
2
x+ = max{0, x}
次のページに具体例
x T w    yi  1　for　x T  Ai and
Dii  1
x T w    yi  1　for　x T  Ai and
Dii  1
 w , , y R

1 T

w w  2
2
2
s.t.　D  Aw  e   y  e
minm  n 1
yT y 
y  0
1 0 0   a11 a12 
1 0 0  1
 y1 
 w1  




D( Aw  e )  y  0 1 0 a21 a22    0 1 0  1   y2 


  w2  
 
 
0 0  1 a31 a32 
0 0  1 1
 y3 
a12 
 a11
    y1   a11w1  a12 w2    y1  1
w
 
  a21
a22   1        y2    a21w1  a22 w2    y2   1

  w2      
 
 a31  a32 
    y3   a31w1  a32 w2    y1  1
Ａ+
x1w1+x2w2=γ+1
68
(a21,a22)
(w1,w2)
分離平面
x1w1+x2w2=γ
(a11,a12)
x1w1+x2w2=γ-1
(a31,a32)
Ａ-




y=分類の誤りの列ベクトル、γ=原点からの距離
A=教師データ
Dii=1 if 分類 iが正解 else =－1
w=重みベクトル=ATD u

分離平面

 xT AT D u = γ
xTw= γ
学習する
のはこのu
w

Ａ+

linear kernel K(xT AT)D u = γ
さらにDをかけると
xTw=γ+1
DK(xT AT)D u = Dγ

分離平面
x’w=γ
Margin
=2/||w||2
Ａ-
xTw=γ-1
69
次のページに具体例
xTw= γ  xT AT D u = γ
linear kernel K(xT AT)D u = γ
さらにDをかけると
D K(xT AT) D u = Dγ
x T w  　 x1w1  x2 w2  
a
 x T AT Du  　 x1 , x2  11
a12
a
 x1 , x2  11
a12
a21
a22
a21
a22
1 0 0   u1 
a31  
 u   　0 1 0 　
  2
a32  
0 0  1 u3 
 u1 
 a31   
u2   x1a11  x2a12 u1   x1a21  x2 a22 u2   x1a31  x2 a32 u3  　 a32   
u3 
1 0 0   x1a11  x2 a12 
Dk x T AT Du  D  0 1 0   x1a21  x2 a22 



0 0  1  x1a31  x2 a32 
70
T
1 0 0   u1  1 0 0 
0 1 0  u   0 1 0 

  2 

0 0  1 u3  0 0  1

するとSVMの最適化は (ただしA’=AT)

u , R


yT y 

 



これは条件なし最小化問題 (10)
minm 1


1 T
u u  2
u , , y R
2
2
s.t.　D K A, AT Du  e  y  e
y0
min2 m 1

2
e  DK A, A Du  e 
T
2
 2


1 T
u u  2
2

Newton 法などで解ける。
ここで、カーネル行列K(A,AT)は大きすぎてメモリに
乗らないので、Aの次元をmとすると、より小さな次
元 m’<<m の A (これはAのランダムな部分集合）を
T
用いたカーネル行列 K ( A, A ) を(10)に代入し最適化
問題を解くのがRSVM
この A をAとは関係ない乱数にしてしまうのが次
ページのアイデア
71
Privacy-Preserving Outsourcing Support Vector
Machines with Random Transformation




教師データxに行列Mで表されるランダム変換を施したMxとm’個
のランダムデータrに逆変換した(MT)-1rを外部サーバに送り、この
2種のデータ間でのペアからなるkernel k(xi,rj)でSVMを学習。
(m’<<m) K(A,A’)によるReduced SVM
ランダムベクトルで学習するので、kernel matrix k(xi,xj)も外部サー
バに知られない。ランダムベクトルは漏れなければ他の学習デー
タも漏れない。
正解ラベルが必要なのはyi k(xi,rj)のうちの(yi xi）だけなので、ラン
ダムデータrjには正解ラベルは不要なのがミソ。
線形カーネルの場合は、置換したMxを計算サーバに与えて計算す
る識別関数は、以下の通り


f ( x)   j 1 v j k Mx  M T  rj  b   j 1 v j k x, rj   b
m'

72
T
1
m'
(Mx)T(MT)-1r=xTMT(MT)-1r=xTr なので、多項式カーネルも計算でき
る
m'をランダム教師入力の個数とする

f ( x )   j 1 v j k Mx  M
m'


T

T 1

rj  b   j 1 v j k x, rj   b
m'
よって、実際のテストデータzはMzと変換して計算
をoutsourceすれば、計算はO(m’)で少なく、データ内
容を（かなり）保護できる。
精度の実験結果は以下(m’=m/10)
73
上の図は以下より抜粋： Keng-Pei Lin,Ming-Syan Chen. Privacy-Preserving
Outsourcing Support Vector Machines with Random Transformation ，KDD2010
(2)k-Support Anonymity Based on Pseudo Taxonomy
for Outsourcing of Frequent Itemset Mining


頻出アイテムセットのマイニングをアウトソーシングす
るときに k-support anonymity という概念を提案
k-support anonymity = 同一のsupport値のアイテムがk個
以上存在
真のDB : TIの暗号化(名前を fakeなものに置き換えるこ
x  S(sensit ive item)
少なくとも



と )された DB : TNにおいて

k個の匿名化item : y  TN   support TN (y)  support TI (x)
k-support anonymityを実現し、かつ匿名化した擬似分類木
を導入して頻出アイテムセットマイニングをアウトソー
ス
匿名化された結果を得たら復号化して欲する結果を得る
74
データベースのexample
原DB: T1
匿名化DB:TN
実アイテム
Transaction
ID
匿名化アイテム
Transaction ID
１
ワイン
１
c,d,g
２
たばこ、ワイン
２
b,d,g
３
たばこ、茶
３
b,h
４
ビール、たばこ、ワイン
４
a,b,c
５
ビール、茶、ワイン
５
a,c,d,h
全商品
嗜好品
4
4
安い嗜好品
2
3
a:ビール
｛4,5}
75
b:たばこ
｛2,3,4}
(a)

support 2
のitem
にはa,g,h
の3種類
あり
5
5
5
3-support
anonymity
k
2
5
4
h:茶
｛3,5}
i
j
4
4
e
f:ワイン
｛1,2,4,5}
2
2
f
3
3
3
2
g
h
{1,2} {3,5}
a
b
c
d
{4,5} {2,3,4} {1,4,5} {1,2,5}
(b)
○の中
の数は、
その部
分木に
含まれ
る
transacti
onの数
の合計
(b)
5
(a)
2
4
4
2
3
a:ビール
｛4,5}
4
(c)
f:ワイン
｛1,2,4,5}
2
(d)
4
i
2
a:ビール
｛4,5}
f:ワイン
3
1
2
g
h:茶
{1,2} {3,5}
b:たばこ c
d
｛2,3,4} {1,4,5} {2}
sup(p6)=3<sup(ワイン)
sup(p7)=1<sup(ワイン)
sup(ワイン)に影響なし
76
2
k
4
i
j
4
3
5
2
1,2はp3には含まれ
ているのでsup(茶)
に影響なし
b:たばこ
｛2,3,4}
5
k
e
2
f:ワイン g
h:茶
{1,2,4,5} {1,2} {3,5}
3
a:ビール
｛4,5}
b:たばこ
｛2,3,4}
4
4
P1
5
5
4
j
i
茶
{3,5}
i
e
k
5
k
5
insert
5
j
4
4
e
f:ワイン g
h:茶
{1,2,4,5} {1,2} {3,5}
2
a:ビール
｛4,5}
3
3
2
3
b:たばこ c
d
｛2,3,4} {1,4,5} {1,2,5}
split
insert、split、increaseという木構造の変更によって
supTN(child node)<supTI(sensitive node)<supTN(parent node)
という関係を崩さなければ、supportの計算は保存される
2
increase
1,5を追加
しても
sup(ワイン)
は不変。
差分プライバシー
(3)Discovering Frequent Patterns in Sensitive Data


Sensitiveなデータのデータセットからトップk個の再
頻出パタン( most frequent patterns： top k FPM)を抽出
するにあたって、ε 差分プライバシーを満たすよう
な細工をする。
近似 top k FPM




78
f k をk番目に多いパタンの真の頻度とする。
信頼度＝ρ:確率(1- ρ)以上で以下の条件を満たす
Soundness: 真の頻度が(f k− γ)より少ない頻度のパタン
は出力しない。
Completeness:真の頻度が(f k+ γ) より大きいパタンは
全て出力する。
Precision: 出力された全パタンの頻度は真の頻度から
±η の範囲に入る。
提案アルゴリズム


ここでε/2差分private
ここでε/2差分private
79


入力：パタン集合=U,データセットサイズ=n
前処理：γ＝(8k/εn)ln(|U|/ρ) とし、通常の
Frequent Pattern Mining アルゴリズムで、頻
度> (f k− γ) のパタン集合Uを抽出。残りの
パタンの頻度は (f k− γ) と見なす
雑音加算とサンプリング：Uの各パタンの頻度
にLaplace(4k/εn)で生成した値を加算。この加算
の結果からトップkパタンを通常のFPMで抽出
する。これをSと呼ぶ。
摂動(Perturbation)：S中のパタンの頻度に
Laplace(2k/εn)で生成した値を加算し、雑音加算
された頻度を得、これを最終結果として出力す
る。
併せてε-差分
private

提案されたアルゴリズムは ε差分プライバシー

少なくとも1-ρの確率で、真の頻度が(f k− γ)より大き
なパタン全てを抽出でき、 U中で(f k+γ)より大きなパ
タン全てが出力される。ただし、 γ＝(8k/εn)ln(|U|/ρ)


少なくとも1-ρの確率で、雑音加算された頻度と真の
頻度の差はη以下。ただし、 η ＝(2k/εn)ln(k/ρ)
Top kパタンの抽出の計算量はO(k’+klogk)
ただし、k’は頻度> (f k− γ) のパタンの個数
80
(4)Data Mining with Differential Privacy

データを属性の値によって分類するID3における分
類木(decision tree) 構築時には、分類木のあるnode に
ぶら下がるデータをsplitし、information gainが最大の
splitの仕方を選ぶ。

information gain
＝(データ全体のエントロピー)
ー(ある属性でデータを分割した場合のエントロピー)
 この論文では、info. gain 以外にもGINI係数、最大値など
を利用して実験比較している。

そこで、splitしたデータの個数にLaplace分布に応じ
たノイズを加え、これにより差分プライバシーを実
現
81
Nτ＝|T|+Laplace(1/ε)
情報量利得などが最大となる属性 A を求める
82
83
その他
(6)Versatile Publishing for Privacy Preservation



Micro data を公開しても quasi ID  sensitive data と
いう推論ができないようにデータベースを変形する
手法
禁止する推論 QIDS の集合を{QS}とする。
全データを以下のようにして分割し変形し{QS}が禁
止されるようにする。


84
全データから部分Tを切り出す。このTは上記の推論がで
きないように匿名化する。
別の部分T’を追加して既存の{T}が{QS}のルールを満た
す場合は、TからSを除去する。

Download Report