Robust De-anonymization of Large Datasets | Netflixのコンペで起きたプライバシー侵害の事例
論文
Robust De-anonymization of Large Datasets
著者
Arvind Narayanan
Vitaly Shmatikov
リンク
補助文献
TL;DR
Netflixが2006年に開催した映画推薦アルゴリズムの改善を目的としたコンペティションにおいて、提供されたデータセットから個人を特定できる可能性があるとNarayananらが指摘
Narayananらは利用者あたり8本の映画評価点を用いてレコードの一意絞り込み実験を行った
実験により映画評価点2本を使うと70%、4本を使うと90%、8本を使うと100%を一意絞り込みができた
Netflixはこの論文による報告を受けてコンペ用に提供していたデータセットの提供を取りやめた
この論文のあとにプライバシーが侵害されたとしてユーザがNetflixを訴えようとした(FTCが介入しのちに和解)
2006年と古い事例ではあるが、プライバシー保護関連の書籍や論文なんかではかなり有名な事例なので取りあげる
Netflixコンペの概要
賞金100万ドル
映画推薦アルゴリズムの改善を目的としたコンペティション
配布したデータセットは1999年12月から2005年12月までの間に480,189人のNetflix利用者が行った100,480,507個の映画評価の5ランクに分類された採点結果
評価データセットからは個人名が削除されるなど最低限の匿名化処理は施されていた
補足
2006年当時Netflixは世界最大のオンラインDVDレンタルサービス会社であった(現在とは若干業態がちがう)
モデル
データベースの定義
個人N人、映画がM種類のデータベース$ \mathcal{D}を定義する
この論文では特に記載がない限り、公開された匿名化サンプル$ \hat{D}が$ Dのサブセットであると想定する
table:dataset
映画評価1 映画評価2 映画評価i 映画評価M
個人1 5 1 null 3
個人2 1 2 4 null
個人j null null 3 5
個人N 2 4 2 1
Sparsity and similarity
Sparsityはデータが疎(まばら)かどうか
数千から数百万の属性値を持つデータベースは必然的にデータがまばらになる
属性値のうちnull以外の値を持つものをサポート(support)と呼び$ supp(r)と表記する
まばらなデータベースはロングテールな分布になる
人気のない有名ではない映画のデータが非常に多くなる
このようなデータベースをk-匿名化しようとしても大半が失敗する(k=1ばかりになる)
Similarityはデータの類似性
類似度$ Simはレコードのペアを0か1にマップする関数
2つのレコード$ r_1, r_2に対する$ Simを定義する(コサイン類似度を一般化)
$ Sim(r_1,r_2)=\frac{\sum_i Sim(r_{1i},r_{2i})}{|supp(r_1)\cup supp(r_2)|}
定義1、データのスパース性
データベース$ Dは以下を満たす時$ (\epsilon,\delta)-sparseである
$ Pr\lbrack Sim(r',r)>\epsilon\forall r'\ne r \rbrack\le\delta
攻撃者モデル
攻撃者の目標は、公開データベースから匿名レコード$ rの匿名化を解除すること(de-anonymize)
これを正式にモデル化するために、$ Dからランダムに$ rをサンプリングし、$ rに関連する少しの補助情報または背景知識を敵に提供する
任意の確率関数$ Auxとしてモデル化され、$ rの属性の不正確な値として生成される
攻撃者に与えられる属性は、$ supp(r)から、または他の確率分布に従って均一に選択できます
プライバシー侵害、正式な定義
プライバシー侵害(Privacy breach)
レコード$ rの匿名化を解除するとはどういう意味なのか
公開サンプル$ \hat{D}から「正しい」匿名化されたレコードを見つけること
攻撃者の目的はプライバシー侵害である。攻撃者がまだ知らない$ rの属性についてできるだけ多くのことを知りたいと思っている。
大規模なデータベースでのプライバシー侵害には2つの異なるシナリオがあるため2つの異なる正式な定義を示す
シナリオ1、自動化された大規模な匿名化
攻撃者は、情報を持っているすべてのレコード$ rについて、$ rのすべての属性に対して単一の「予測」を生成する
例
k-匿名性を刺激した攻撃
有権者データベースからの人口統計データを補助情報として取得し、敵対者はそれを匿名化された退院データベースと結合し、結果の組み合わせを使用して、両方のデータベースに表示される各人の医療属性の値を照合する
定義2、脱匿名化1
$ Dと$ Aux(r)を入力とし、以下の条件式を満たす$ r'を出力するアルゴリズム$ Aが存在する時$ Dは$ (\theta,\omega)-deanonymizedされる
$ Pr\lbrack Sim(r',r)\ge\theta\rbrack\ge\omega
定義2は、背景知識の増幅として解釈できる
攻撃者は「正しい」匿名化されたレコードを正確に識別する必要はない
攻撃者がターゲットレコードと非常に類似していることが保証されているレコード、つまり同じまたは類似の属性値を含むレコードを見つけている限り、プライバシー侵害が発生している
定義3、脱匿名化2
補助情報$ Auxが、$ r \in Dに対して入力$ \hat{D}および$ Aux(r)から以下の式を満たす$ r'を生成するアルゴリズム$ Aが存在する場合
データベース$ Dの任意のサブセット$ \hat{D}は$ (\theta,\omega)-deanonymizedすることができる
$ (1)\quad\text{If $r\in\hat{D}$ then}\quad Pr\lbrack Sim(r',r)\geq \theta\rbrack\geq\omega
$ (2)\quad\text{If $r\notin\hat{D}$ then}\quad Pr\lbrack Aがnullを生成\rbrack\geq\omega
シナリオ2
攻撃者は、ターゲットレコード$ rを含む候補レコードのセットまたは「ラインナップ」を作成する
ラインナップ内の$ rを識別するのに十分な補助情報がないため、または追加の、場合によっては手動で実行することを期待している
一部のレコードは他のレコードよりも候補の可能性が非常に高いため、候補レコードの数は適切なメトリックではない
代わりに、候補レコード全体の確率分布を考慮し、メトリックとして$ auxが与えられた$ rの条件付きエントロピーを使用する
匿名化解除アルゴリズムを実行した後、攻撃者がレコード$ r'_1...r'_kおよび対応する確率$ p_1...p_kを出力する
後者($ p_1...p_k)は、候補レコードのエントロピー符号化と見なすことができる
定義4、脱匿名化3(エントロピー脱匿名化)
補助情報$ Auxが、$ r \in Dに対して入力$ \hat{D}および$ Aux(r)から以下の式を満たす、候補レコード$ D'と確率分布$ \Piのセットを出力するアルゴリズム$ Aが存在する場合
データベース$ Dは$ (\theta,H)-deanonymizedすることができる
$ E\lbrack min_{r\in D',Sim(r,r')\ge 0}H_S(\Pi,r') \rbrack\le H
glassonion1.icon 期待値がHよりも小さいみたいな意味っぽいが詳細がよくわからない
エントロピーが大きいほど分布がよくわからないことを示しているので、$ H_Sの期待値がH以下になる
Hより攻撃者が分布について知ってしまっている(cipepser.iconさん補足)
この定義は、ターゲットレコードに類似したレコードの候補セットの最小シャノンエントロピーを測定する
攻撃者がもっともらしい候補のラインナップを計算できないときに、データベース全体からランダムなレコードを出力することをモデル化している
脱匿名化アルゴリズム
アルゴリズムの3つの主要なコンポーネント
スコアリング関数
一致基準
レコードの選択
スコアリング関数$ Scoreは、敵の補助情報$ Auxとの一致度に基づいて、$ \hat{D}の各レコードに数値スコアを割り当てる
一致基準は、一致があるかどうかを判断するために、スコアリング関数によって割り当てられたスコアのセットに攻撃者が適用するアルゴリズム
レコードの選択では、必要に応じて、1つの「最良の推測」レコードまたは確率分布を選択する
脱匿名化手順
攻撃者は各$ r' \in \hat{D}に対して$ Score(aux, r')を計算する
攻撃者は、結果のスコアのセットに一致基準を適用し、一致するセットを計算する。一致するセットが空の場合、攻撃者はnullを出力して終了する
データベース全体が解放された場合、つまり$ D'=Dの場合、または攻撃者がターゲットレコードが解放されたことを確実に知っている場合、つまり$ r\in\hat{D}の場合、このステップはスキップできる
攻撃者の「最良の推測」が必要な場合(定義2および3による匿名化解除)、敵対者は最高のスコアで$ r'\in\hat{D}を出力する
候補レコード全体の確率分布が必要な場合(定義4による匿名化解除)、攻撃者はスコアに基づいて減少しない確率分布を計算し、この分布を出力する
アルゴリズム1A
シンプルなパターン
スコアの計測
候補レコードのスコアは、攻撃者の知識との間の最も類似性の低い属性によって決定される
$ Score(aux,r')=min_{i\in supp(aux)}Sim(aux_i,r_i')
攻撃者はいくつかの固定値$ \alphaに対してマッチング$ D'=\{r'\in\hat{D} : Score(aux,r')>\alpha\}を計算する
一致基準は$ D'が空でないこと
確率分布は$ D'に対して均一
アルゴリズム1B
特徴
統計的にまれな属性により高い重みを与える
アルゴリズムの堅牢性を向上させるために、一致基準では、最高スコアが2番目に良いスコアを大幅に上回っている必要がある
元論文の数式がわかりづらかったので「プライバシー保護入門」の数式を引用する
スコアの計測
$ Score(aux,r')=\sum_{i\in supp(aux)}\frac{Sim(aux,r'_i)}{log|supp(i)|}
glassonion1.icon 分母に対数関数が使われている理由がよくわかってない
$ S=\{Score(aux,r')|r\in \hat{D}\}かつSの要素の標準偏差$ \sigma(S)としたとき攻撃者はあらかじめ決めたパラメタ$ \phiに対して以下とする(ただし$ max_2(S)は2番目に大きな$ Scoreの値である。論文の実験では$ \phi=1.5としている)
$ \text{if}\quad\frac{max(S)-max_2(S)}{\sigma(s)}\geq \phi\quad\text{then}$ Aux(r)に対するレコードはScore最大のレコード
$ \text{if}\quad\frac{max(S)-max_2(S)}{\sigma(s)}<\phi\quad\text{then}$ Aux(r)に対するレコードはなし
確率分布は各$ r'に対し$ \Pi(r') = c\cdot e\dfrac{Score(aux,r')}{σ}となる
$ cは、分布の合計を1にする定数
分析、一般的なケース
アルゴリズム1Aを使用して、任意の多次元データセットの匿名化を解除するために必要な補助情報の量を定量化する
必要な補助情報が小さいほど(つまり、敵がターゲットについて知る必要のある属性値が少ないほど)、攻撃が容易になる
最悪の場合の分析から始めて、データが抽出される分布についての仮定なしに、最も一般的な場合に必要な補助情報の量を計算する
$ auxは$ Aux(r)関数の実行結果
$ auxを、データセットのレコード$ rに関する補助情報とする
$ rと$ auxはどのレコードにおいても類似した属性値を持っている
定理1
データベース$ DはN個のレコード$ rからなり、$ 0<\epsilon,\delta<1とする
$ auxが$ rの属性のうち、m個以上について$ Sim(aux_i, r_i)\geq 1-\epsilon\forall i\in supp(aux)を満たす時
$ Dは$ (1-\epsilon-\delta,1-\epsilon)-deanonymized可能である
分析、スパースデータセット
スパース性、データが疎(まばら)かどうか
スパース性は、匿名化が成功する確率を高め、必要な補助情報の量を減らし、データの摂動と補助情報の誤りの両方に対してアルゴリズムをより堅牢にする
平均レコードにはデータセット内に極端に類似したピアがないと想定する
定理2
$ \epsilon,\delta,auxを定理1と同じとする
データベース$ Dが$ (1-\epsilon-\delta,1-\epsilon)-sparseな場合
データベース$ Dは$ (1,1−\epsilon)-deanonymized可能である
定理3
データベース$ Dが$ (1-\epsilon-\delta,1-\epsilon)-sparseかつ
$ m=\dfrac{log\frac{N}{k-1}}{log\frac{N}{1-\delta}}な場合
データベース$ Dは$ (1,\frac{1}{k})-deanonymized可能である
データベース$ Dは$ (1,\log k)-deanonymized可能である
分析、サンプルデータの脱匿名化
匿名化されたレコードの一部のみが攻撃者に利用可能であるというシナリオ
このシナリオでは、元のデータベース$ Dに敵のターゲットレコード$ rが含まれていても、このレコードは匿名化された形式でも$ \hat{D}に表示されない場合がある
定理4
$ \epsilon,\delta,D,auxを定理1と同じとする
$ \hat{D}\in Dとする
$ \hat{D}は$ (1-\epsilon-\delta,1-\epsilon)-deanonymized可能である
定理1の証明で与えられた誤った一致の確率の限界は依然として成り立ち、敵は、ターゲットレコード$ rが$ \hat{D}にある限り、少なくとも1つの一致が保証される
$ r\notin\hat{D}の場合、攻撃者は少なくとも$ 1−\epsilonの確率でnullが出力される
$ r\in\hat{D}の場合、攻撃者は少なくとも$ 1−\epsilonの確率で成功する
定理2と3はこのシナリオに直接変換されることはない
攻撃者が利用できるランダムサンプル$ \hat{D}がスパースである場合、データベース$ D全体もスパースでなければならないことを保証する
定理5
データベース$ Dが$ (\epsilon,\delta)-sparseでない場合
ランダムに抽出された$ \frac{1}{\lambda}-subsetの$ \hat{D}は少なくとも$ 1-\gammaの確率で$ (\epsilon,\frac{\delta\gamma}{\lambda})-sparseではない
ケーススタディ: Netflix Prize dataset
Netflix PrizeはNetfliの映画推薦アルゴリズムの改善を目的としたコンペティション
映画のレイティングは、医療記録なんかに比べて機密性は高くない
一見機密性は低そうだがNetflix会員に関する大量のデータが公開されるとプライバシーの問題が発生することがわかる
Netflix Prize Webページのよくある質問の中に次の質問があった
Netflix側はデータを公開することでプライバシー侵害が起きるとは考えていなかった
Q: データセット内に非公開にする必要のある顧客情報はありますか?
A:
いいえ、すべての顧客識別情報が削除されました。
残っているのは評価と日付だけです。
... 中略 ...
たとえば、自分の評価とその日付をすべて知っていたとしても、含まれているサンプルはごくわずかであり(完全なデータセットの10分の1未満)、そのデータは対象であるため、データでそれらを確実に特定することはできません。
レコードから識別情報を削除するだけでは匿名化は不十分
攻撃者は、一部の加入者の映画の好みに関する補助的な情報を持っている可能性がある
実際の攻撃
NarayananらはNetflix Prizeデータセットに対して脱匿名化アルゴリズムの1Bを適用した
攻撃者の背景知識の仮定
映画評価属性1-5について完全に一致と±1の誤差データ
日付については3日または14日ずれているデータを用意した
攻撃者が日付についてまったく知らない場合も想定した
攻撃の結果
8つの映画のレイティング(うち2つは完全に間違っている可能性がある)と14日間のエラーがある可能性のある日付により、99%のレコードがデータセット内で一意に識別された
2つの評価と日付(3日間のエラーあり)で68%を識別できた(グラフは論文から引用)
https://gyazo.com/aaf5864f2728e4570737069ea819920c
攻撃者が6本の映画を正しく知っていて、2本を間違って知っている場合、ほんの少しの追加情報で完全な脱匿名化が可能(グラフは論文から引用)
https://gyazo.com/95b12734a7005b54452d4bee1352acdf
攻撃者は日付を知らなくても、マイナー映画の評点に関する背景知識を持っている場合は、重大なプライバシー侵害が発生した(グラフは論文から引用)
https://gyazo.com/4f2f320f8bf1a24bbe2533dc6b95cc57
IMDbとの照合
IMDb(Internet Movie Database)は、映画、テレビ番組、ホームビデオ、ビデオゲーム、に関連する情報を集めたオンラインデータベースで、キャスト、制作スタッフ、個人の経歴、プロットの概要、トリビア、評価、ファンや批評家のレビューなどが含まれている
IMDbを使用するNetflix会員の場合、プライベートNetflixレーティングとパブリックIMDbレーティングの間には強い相関関係があると予想された
両サービスの加入者によって評価されたほんの一握りの映画であってもNetflix Prizeデータセットのレコードと照合することができた
IMDbの利用規約によって課せられたIMDbのクロールに関する制限のため、数十人のIMDbユーザーのごく少数のサンプルを使用して実験を行った
実験で使用した50人のIMDbユーザのうち2人のユーザが、Netflix Prizeの2人のユーザと同一人物であることが高い確信度で推定された
Narayananらの実験の補足
Netflix Prize datasetの実験はデータを一意絞り込みができることを示している
IMDbとのレコード照合実験は一意に絞り込まれたレコードが公開データセットとの照合により個人特定につながることを示している
おわりに
長めの論文で数式も多く読むのが大変でしたが補助文献の「プライバシー保護入門」のおかげでかなり理解を深めることができました。かなり良書なのでおすすめです。
Netflixの映画評価データベースのような履歴データの匿名化は単純な匿名加工やk-匿名化では守ることが難しいということがよくわかる事例でした。映画評価のような一見機密情報がなさそうなデータベースであってもプライバシー侵害の可能性があることが指摘されているのがとても興味深かったです。個人的に大事だなと思った点は、外部提供したデータが全データの一部(サブセット)であっても提供したデータにスパース性(データがまばらかどうか)があればプライバシー侵害のリスクが高いという部分です。データ量に関係なく個人情報が保存されているデータベースは常にプライバシー侵害のリスクがあることを意識することが大切だと思いました。
論文には分析で取り上げた定理の証明もきちんと掲載されているのですが記事の都合上省略しました。この記事で興味をもたれた方はぜひそのあたりも読んでみてください。(文責・藤田)