全部門第一位チーム「ψ沈黙のジャスティスψ」が解説する
最強の匿名加工技術
NTTセキュアプラットフォーム研究所
濱田 浩気
Copyright©2016 NTT corp. All Rights Reserved.

概要
昨年の PWS Cup で，ψ沈黙のジャスティスψは幸運にもたくさんの賞をいただけました．
その中で何をしていたのかをご紹介いたします．

Copyright©2016 NTT corp. All Rights Reserved.

1

目次• ψ沈黙のジャスティスψ (概要，方針)• 匿名加工フェーズ (予備戦，本戦)• 再識別フェーズ(予備戦，本戦)

Copyright©2016 NTT corp. All Rights Reserved.

2

ψ沈黙のジャスティスψとは• NTT という会社の真面目な3人の社員

正木 彰伍

長谷川 聡

濱田 浩気

匿名化

匿名化

秘密計算+匿名化• 表の顔: プライバシー保護技術の研究者• 昨年7月～: ψ沈黙のジャスティスψで大会参加
Copyright©2016 NTT corp. All Rights Reserved.

3

チームの方針• (かなり)勝負に徹する‒ 会社からのプレッシャー応援• やりすぎと思われた方，すみません．．．

• でも大会は盛り上げたいし楽しみたい‒ 匿名加工は各自一つずつ好きなものを提出• 再識別フェーズを考えると，本命以外の2枠は当てられにくいものを提出するのが有利だが‒ ヒントは与える(後述)が，早めにいくつか提出
Copyright©2016 NTT corp. All Rights Reserved.

4

ルール分析と対策(1/2)• 相対評価どれを提出していいかわからない匿名加工では多様なデータを用意・提出し，良いものを残そう• 評価値は公開
早めの提出は他チームへの手法のヒントにできるだけ遅めに提出しよう，他チームの評価値をよく見よう
Copyright©2016 NTT corp. All Rights Reserved.

5

ルール分析と対策(2/2)• サンプルの再識別率，U5も公開
匿名加工データからは分かり得ない情報実世界では得られないが，再識別に有用評価値を積極的に利用• あくまで指標値で決着
既存の手法に囚われず，指標値の最適化に集中

Copyright©2016 NTT corp. All Rights Reserved.

6匿名加工フェーズ(予備戦)おおまかな戦術の選定• いくつの指標で勝てそうかで見積もり‒ 対象: 元のまま，k匿名，YA，etc.
有用性

安
全性
評価

重み

指標元のままk匿名

YA

2

U1(meanMAE)◎○◎

2U2(crossMean)◎△◎

2U3(crossCount)

◎

△

◎

2U4(corMAE)

◎

×

◎

2U5(IL)◎×△2

U6(nrow)◎◎◎3

S1(min-k)

△◎

△

3

S2(avg-k)△◎△6S3(max-reid)×○◎1414.7

18.7

凡例
◎: 1位
○: 上から1/3△: 上から2/3
×: 最下位近く

Copyright©2016 NTT corp. All Rights Reserved.

8

具体例1: フリーダム(予備戦1位)

Copyright©2016 NTT corp. All Rights Reserved.

9フリーダム(予備戦1位)でしたこと• QI統一• YA (+IL最適化(+ランダム化))
有用性

安
全性

評価

重み指標

YA

フリーダム

2

U1(meanMAE)

◎

◎

2

U2(crossMean)

◎

◎

2

U3(crossCount)

◎

◎

2

U4(corMAE)

◎

◎

2

U5(IL)△2U6(nrow)

◎

◎

3

S1(min-k)△△

3

S2(avg-k)△6

S3(max-reid)

◎18.7





凡例
◎: 1位
○: 上から1/3△: 上から2/3
×: 最下位近く○○◎20.3Copyright©2016 NTT corp. All Rights Reserved.

10

QI 統一• 手法: U2, U3 で対象外のカテゴリ属性の値を単一にする• 効果: ほぼノーリスクで S2 を高められる
世帯

性別

産業

職業

⋯

1

12529496.0792⋯25806.1846⋯

112525806.1846⋯

638278.1598

⋯

1

1

3538278.1598⋯

3

VV74122.0521

⋯

2

1

3574122.0521⋯

11533256.8355

⋯

2

1

1533256.8355⋯

21646992.7870

⋯

2

1

1546992.7870

⋯

世帯

性別

産業

職業

1

12529496.0792

12251232222⋮

⋮

⋮

⋮

食料支出

⋮

⋮⋮⋮⋮

食料支出

⋮

Copyright©2016 NTT corp. All Rights Reserved.

11

YA (山岡匿名化)• 手法: 行ごとに属性値を入れ替え• 効果: U5 は失うが，U1-U4,U6,S1,S2 を維持しながら S3 を高められる
行番号

性別

産業

職業

1

12529496.0792

222532

34256
⋮

⋮

行番号

性別

産業

職業

⋯

1

1

1533256.8355⋯

25806.1846⋯

222525806.1846⋯

638278.1598⋯

32

3638278.1598⋯

3VV

74122.0521⋯

421646992.7870⋯

11533256.8355⋯

523VV74122.0521⋯21646992.7870⋯

612529496.0792

⋯

⋮

⋮

食料支出

⋮⋮⋮

⋮

⋮

食料支出

⋮Copyright©2016 NTT corp. All Rights Reserved.

12

YA + IL最適化• 手法: YA の高度化．U5 が大きくならない
ように行ごとに属性値を入れ替え• 効果: YA で U5 も小さめ．
• 実装方針: 匿名化対象データは8333レコードしかないないので，𝑂(𝑛2 )でもなんとかなるはず 各行間の距離(IL)をすべて計算し，小さいペアから採用する𝑂 𝑛2 log 𝑛 の貪欲法
‒ 簡単な枝刈りをしつつで1分程度
Copyright©2016 NTT corp. All Rights Reserved.

13

YA + IL最適化 + ランダム化• 手法: 「YA + IL最適化」の高度化‒ 貪欲法をランダム化し，乱数の範囲を調整してU5 と S3 のバランスを取れるようにする• 効果: U5 は少し大きくなるが，当てられにくくなる• 実装: 行間の距離にノイズ(乱数)を加算‒ ノイズ大当てられにくく，U5大きく‒ ノイズ小当てられやすく，U5小さく
Copyright©2016 NTT corp. All Rights Reserved.

14匿名加工フェーズ(本戦)具体例2: アイロン(本戦1位)

Copyright©2016 NTT corp. All Rights Reserved.

16

アイロン(本戦1位)でしたこと• フリーダム(QI統一， YA+IL最適化+ランダム化)• QIグループ内スワップ
有用性

安
全性
評価

重み指標

フリーダム

アイロン

2

U1(meanMAE)◎◎

2

U2(crossMean)

◎

◎

2

U3(crossCount)

◎

◎

2

U4(corMAE)◎2

U5(IL)○○2U6(nrow)◎◎

3S1(min-k)

△

△

3

S2(avg-k)○○

6

S3(max-reid)(◎)×◎(20.3)14.3



18.3



×Copyright©2016 NTT corp. All Rights Reserved.

17

QIグループ内スワップ(1/2)• 手法: 各QIグループ内で数値属性値を属性ごとに独立にスワップ

世帯

人員

消費支出

食料

住居

1

12398.98

193.23

1

12389.11

112

⋮

世帯

人員

消費支出

345.45

112092.98

78.22

412.2378.22

567.88112398.98

987.64345.452092.98987.64412.23

1

12389.11

193.23567.8812888.10234.23452.90212074.42

234.23576.12

212074.42

105.32576.12

212615.21

688.98452.90212615.21

688.98662.21212888.10

105.32662.21

⋮

⋮⋮⋮⋮⋮

⋮

食料

住居

Copyright©2016 NTT corp. All Rights Reserved.

18

QIグループ内スワップ(2/2)• 効果:‒ AYA に強くなった(S3 向上)‒ 同一QIグループ内でのスワップなので．．．
• U2, U3 には影響なし• U4 は悪化するが諦める• なぜうまくいくのか:‒ AYA は総和に基づくソートで推定
 総和が乱れると隙ができる(AYAの推定が甘くなる) その後IL最適化を行えば，この隙に入り込める
Copyright©2016 NTT corp. All Rights Reserved.

19

その他
• 数値属性で分けたクラスタ中で行入れ替え(五十万郎丸(予備戦9位))‒ その際に数値を平均化 = 総和を乱して AYA 対策(Anony Name(本戦2位?), ponnyo(本戦4位?))• 平均と相関を保存する擬似データを生成(ジャスティスなビーバーの大工事(予備戦11位))• QIグループ間のレコード移動で S2(min-k) 向上‒ U2 をあまり変えないレコードを選んで移動
 U3 を壊すので思ったほど効果が上がらず
Copyright©2016 NTT corp. All Rights Reserved.

20

再識別フェーズ

再識別の方針
データを眺めて3つに分類
1. 微小なノイズとかなどで簡単に解けそう 簡単に解く

2. サンプルで十分によさそう サンプルを適用

3. YA みたいだから無理そう IL 近傍推定
 教科書 YA 解読

Copyright©2016 NTT corp. All Rights Reserved.

22

IL近傍推定• 発想: YA を使う場合は IL (U5)を小さくするはずIL が小さいレコードを選んで推定結果とすれば，そこそこ当たるのでは• 手法: 各レコードに対し，ILが最小の行番号を推定値として出力• 実装: 8333行なので𝑂 𝑛2 の実装．6秒くらい

Copyright©2016 NTT corp. All Rights Reserved.

23

教科書YA解読(1/2)
経緯:• YA 採用チームはきっとU5を小さくしているはずなのに U5 が 0.037 と大きいデータがある？
• ランダムでも U5=0.035 程度のはずなのに？？
• もしかして，教科書(ルール説明論文)
そのままの実装があったりするのでは？
 あ，あった！(U5=0.028だけど)• さらに，ずれ幅を変えていたりとか？
 あ，あった！(U5=0.037)
Copyright©2016 NTT corp. All Rights Reserved.

24

教科書YA解読(2/2)• 手法:
ずれ幅1～8332の教科書YAすべての IL を計算一致する評価値を持つ匿名加工データを探す
頑張って計算した IL
ずれIL (U5)10.02796416

20.02996592

30.03217687

40.03292660

50.03330663

60.03331962
⋮

⋮

8332

0.02796416

各匿名加工データの指標値
見～つけた！

⋯ U5

⋯

名前U1

データ1

0.00

0.01305021

⋯

データ2

1.01

0.00000000

⋯

データ3

0.00

0.02796416

⋯⋮

⋮

⋮

Copyright©2016 NTT corp. All Rights Reserved.

25

まとめ

ψ沈黙のジャスティスψのしたことを解説
指標値の最適化に集中した結果:• 匿名加工:‒ YA をベースに IL最適化‒ QIグループ内スワップ• 再識別:‒ IL近傍推定‒ 教科書YA解読
Copyright©2016 NTT corp. All Rights Reserved.

26

おわりに
• とても勉強になりましたし，何より，非常に楽しいコンテストでした• 一緒に競い合ってくださったみなさま，運営のみなさま，誠にありがとうございました

Copyright©2016 NTT corp. All Rights Reserved.

27