Differential Privacy

前回の記事でk-匿名性などを満たすように加工しようみたいな話をしましたが，現在はDifferential Privacy(DP)という考えが主流なのでそれについて説明していこうと思います．今回も『データ解析におけるプライバシー保護』[1]を参考にしています． www.kspub.co.jp

簡単な背景

そもそもどういう状況が想定されているのかが少し実感しづらいのでそのあたりをまず説明していきたいと思います．

ビッグデータと言われるように色々なデータが収集されるようになってきています．ただ，集めるだけじゃなくて，その分析結果なども公開されるようになっています．例えば，Amazonでは人気商品などが推薦されたり，Google Mapでは店の混雑状況などが可視化されたりしています．データの公開だけではなく，このような分析結果の公開もプライバシーに関するリスクを抱えています．

極端な例ですが，山田さんが毎週水曜日にあるラーメン屋に通っていることは知っているとします．そのラーメン屋は人気がなく，通っている人は山田さんだけだとします．この状況を知った上で，Google Mapの混雑状況を見るとある1時点だけ人が来ていることがわかり，山田さんが何時にラーメン屋に通っているかという情報がバレてしまいます．また，統計量などはその情報を分析したいサードパーティなどに提供されることもあります．

従って，このような統計量の公開でもプライバシーを保護する必要があり，それを考えているのがDifferential Privacy(DP)です．このDPは統計量にノイズを加えて本当の統計量ではないものを公開することでプライバシーを保護します．イメージとしては以下のような感じで，サービスの提供者はリアルなデータを集めることができ，その公開時にノイズをかけます．

f:id:kiri1701:20191221220543p:plain — DPのイメージ図

ここでは，数学的なDifferential Privacyの定義を書いたのちに，どういうことを意味しているのかを書いていこうと思います．上で述べたように，あくまでデータの統計量（カウント，合計，平均など）を公開する時に個人のデータがばれないようにするためのものだという認識は忘れないでください．プライバシーを完全に守るとデータの有用性が無になるので，プライバシーをある程度守って有用性を高めることを目指しています．

Differential Privacyの定義[2]
要素が一つだけ異なる（隣接する）データベースDとD'に対して
あるメカニズムAが以下の不等式を満たせば，そのメカニズムAはε-Differntial Privacyを満たすという

$\displaystyle{ \forall t \in \operatorname{Range}(\mathbf{A}): \operatorname{Pr}[\mathbf{A}(D)=t] \leq e^{\varepsilon} \operatorname{Pr}[\mathbf{A}(D^{\prime})=t] }$

この時，tはメカニズムの出力を全て考えているので，データベースの内容がどうなっていようとプライバシーは守られることになります．そのまま解釈するとAにDを入力した時にtを出力する確率とAにD'を入力した時にtを出力する確率が $e^\epsilon$ 倍違うとなるが，どちらかというと出力がtだった時に入力がDだったかD'だったかの確率の違いが $e^\epsilon$ でこの $e^\epsilon$ が小さいと見分けがつかないということになります．

この辺りの解釈については次でまとめて説明しようと思います．とりあえずは，DPはデータベースを入力としたメカニズムの出力に満たすべき制約を定義していると考えてください．

隣接性やεの解釈

まず入力のDとD'，εとはなんぞやとなると思うので，それについて説明します．

DPはDとD'という隣接したデータベースに対する定義なので，どのような要素の隣接を考えるかによって守られるプライバシーが異なってきます． FacebookのようなSNSの運営会社が参加しているユーザー間のグラフの統計量を公開する場面を考えます．データベースとしては(user_id, other_id, friend_or_not)のようなものを考える．friend_or_notは1なら友達，0なら友達ではない．

1つ目の考え方は「ある枝がグラフに存在するか否か」によって隣接性を定義することです．この場合，あるuser_idとother_idに対して，Dはfriend_or_notが1でD'はfriend_or_notが0になる．このようなDとD'に対してDPを満たすメカニズムを用いると，あるユーザが1人の別のユーザと友達であろうがなかろうが，クエリの結果がtという情報を受け取る確率は $e^{\epsilon}\simeq 1 + \epsilon$ 倍程度しか変わらない．従って，個々の交友関係を公にしたくない場合に有効な定義だと言えます．

2つ目の考え方は「ある頂点がグラフに存在するか否か」によって隣接性を定義することです．この場合，Dに含まれているユーザーのうち，ある1人のデータのみがD'には含まれておらず，それ以外は全て同じデータだということを意味します．このようなDとD'に対してDPを満たすメカニズムを用いると，あるユーザがSNSに参加していようがいまいが，クエリの結果がtという情報を受け取る確率は $e^{\epsilon}\simeq 1 + \epsilon$ 倍程度しか変わらない．従って，ユーザがそのSNSに参加しているかどうかを公にしたくない場合に有効な定義だと言えます．

隣接性は公にしたくないと考えている情報の粒度を定義していると言えます．一般的には1つ目のような考え方で，データベースのうちのある値が異なる場合を考えることが多いと思います．

εは隣接性で定義された粒度の情報に対してプライバシーをどの程度保護するかを定義しています． εを小さくすると，DとD'に対してtと出力する確率がほぼ同じになり，出力結果がtだった時に入力がDだったかD'だったか見分けがつかなくなるので，プライバシー保護の度合いが高いと言えます．一方，εを大きくすると，同じような値を出力する確率が低いので，出力から入力の見分けがつきやすくなり，プライバシー保護の度合いが低いと言えます．このイプシロンはよくプライバシーバジェットと呼ばれますが，なぜそう呼ばれるかは次の記事で紹介しようと思います．

εを事前に決定しておき，ε-DPを守るメカニズムに基づいて統計量の公開をすると，事前に設定した厳しさでプライバシーを保護できます． DPではどんな背景知識を持っている相手に対してでも同等のプライバシーを保護できることから，プライバシー保護の一般的な概念になってきています．ただ，εの実際の値(0.1や1, 2など)と実際に守られているプライバシーの関係がわかりづらいという批判もあります．

Laplace Mechanism

今まではDPの定義のような話でしたが，ε-DPを実際に達成する方法であるLaplace machanismについて説明していこうと思います． Laplace Mechanismでは，イメージ図で書いたようにノイズを加えることでDPを達成します．

敏感度

では，ノイズをどれくらい加えたら良いのでしょうか．それを考えるのにクエリの敏感度というものを用います．これは隣接したデータベースDとD'に対してクエリを実行した結果がどれくらい変わるかを表したものです．

l1-敏感度の定義[1]

$\displaystyle{ \Delta_{1,q}=\max_{D\sim D^\prime}\| q(D)-q(D^\prime)\| }$

例えば，合計や平均の敏感度は以下のようになります．

の敏感度
- あるユーザーiの値が0か1かなので，敏感度は1
の敏感度
- sumをnで割るので，敏感度は $\frac{1}{n}$

この敏感度に応じた大きさのノイズをかけることでDPを満たすことが出来ます．また，合計を出力する時にDPを満たす方がよりノイズを大きくかけないといけないことがわかります．

ラプラス分布

実際にかけるノイズでよく使われるのがラプラス分布です．

ラプラス分布の確率密度関数は以下の式で与えられます．

$\displaystyle{ f(x|\mu, \sigma) = \dfrac{1}{2\sigma}e^{-|x-\mu|/\sigma} }$

期待値は $\mu$ ，分散は $2{\sigma}^2$ です．ノイズとして加えるときは期待値を0にして，偏りがないようにします． $\mu=0$ として， $\sigma$ を色々と変えた時の分布は以下のようになります．

f:id:kiri1701:20191222174022p:plain — ラプラス分布

クエリqのl1-敏感度を ${\Delta}_{1, q}$ ，プライバシーバジェットをεとした時，
Laplace(0, ${\Delta}_{1, q}$ /ε)からサンプリングしたrを用いて
q(D)というクエリの結果の代わりにt=q(D) + rを結果として出力することでε-DPを満たすことができます．この流れ全体をラプラスメカニズムといいます．

次に，このラプラスメカニズムが本当にε-DPを満たしているかを確かめていきます．ラプラス分布の確率密度関数の定義からxに関わるのは指数関数の部分だけなので，そこだけに着目し対数をとった比を考えると以下になります．

$\displaystyle{ \big|\ln \dfrac{Pr[f(q(D)) = t]}{Pr[f(q(D') = t]} \big| = \big|\ln \dfrac{exp\big(-\frac{|t-q(D)|}{\Delta_{1,q}/\epsilon}\big)}{exp\big(-\frac{|t-q(D')|}{\Delta_{1,q}/\epsilon}\big)} \big| \\ = \big| \epsilon \cdot \dfrac{|t-q(D)| - |t - q(D')|}{\Delta_{1,q}} \big| \\ \leq \dfrac{\epsilon |q(D)-q(D')|}{\Delta_{1,q}}\leq \dfrac{\epsilon \Delta_{1,q}}{\Delta_{1,q}}\leq \epsilon }$

上記では敏感度の定義として，maxを取っていることを使っています．従って，ラプラスメカニズムはε-DPを満たします．平均値などを求めた後に，ラプラスメカニズムを使ってノイズをかけた出力を公開するとプライバシーを保護することが出来ます．

Local Differential Privacy(LDP)

DPでは統計量を公開するときにノイズをかけていましたが，実際のサービスなどでは，データを集めている人を信頼出来ない時が多々あると思います．スマホのアプリとかでは開発者がよくわからないというのはよくあるシチュエーションで，こういう時には個人的な情報をできれば渡したくないですが，渡すことでサービスがよくなるのであれば渡してあげたいはずです．そこで，考えられたのがLocal Differential Privacyという概念で，これはユーザーがデータ収集者にデータを渡す時にすでにノイズを加えて個々の値をわからなくしてから渡すというものです．従って，各ユーザーは安心してデータを渡せ，収集者は個々のデータはわからないが，統計的な性質は分析することが出来，サービスの向上に活かすことが出来ます．イメージとしては以下のようになります．

f:id:kiri1701:20191222180845p:plain — LDPのイメージ図

こうすることで個人の情報は渡さずに，全体の傾向を分析することができます．さらに，LDPを守って集められたデータはそこからどんな使い方をしようとこれ以上プライバシーを侵害するリスクがないという利点もあります．

Local Differential Privacyの定義[3]
任意の異なる入力v1,v2に対してメカニズムAが以下の不等式を満たす時，Aはε-LDPを満たすという

$\displaystyle{ \forall y \in \operatorname{Range}(\mathbf{A}): \operatorname{Pr}\left[\mathbf{A}\left(v_{1}\right)=y\right] \leq e^{\varepsilon} \operatorname{Pr}\left[\mathbf{A}\left(v_{2}\right)=y\right] }$

考え方はDPと共通で，出力がyだった時に，ユーザーの入力がどの値だったか見分けがつきにくいということを意味しています．しかし，DPでは隣接したDとD'に対してそれが成り立っていたのに対して，LDPでは，入力のどんな2つの値の組に対しても上記の不等式が成り立っていないといけないので， LDPはDPよりも厳しくプライバシーを保護していると言えます．

Random Response

LDPを達成するメカニズムの説明としてよく使われるのがRandom Responseと呼ばれるものです．例えば，100人の学生に対して，理系の人数を調べたいとします．各学生は自分の分野を知られたくないので，コインを投げて表が出れば正直に答え，裏が出ればさらにコインを投げ，表が出たら理系，裏が出たら文系と回答します．こうすると，各個人の回答が本当かどうかわからないので，個人の分野は分かりませんが，人数はなんとなく分かります．これを一般的にして，0,1で返す質問に対し，ある一定の確率pで本当の回答をし，残りの確率1-pで適当に回答するとします．数式的に表すと以下になります．

$\displaystyle{ \operatorname{Pr}\left[\text x=i\right]=\left\{\begin{array}{ll}{p=\frac{e^{\varepsilon}}{e^{\varepsilon}+1},} & {\text { if } i=x} \\ {q=1-p=\frac{1}{e^{\varepsilon}+1},} & {\text { if } i \neq x}\end{array}\right. }$

これがε-LDPを満たすことは簡単にわかると思います．このRandom Responseで回答されたものを集計すると，個々の回答がどっちだったかの判別はつきませんが，回数の推定値が求められます． [tex:\sum{j} 1{\text {Support }\left(y^{j}\right)}(i)]をiと回答した人の人数とすると，以下の値が回数の不偏推定量になります．

$\displaystyle{ \tilde{c}(i)=\frac{\sum_{j} 1_{\text {Support }\left(y^{j}\right)}(i)-n q}{p-q} }$

証明は簡単にできますが，詳しいことは論文[3]を参照してください．

メカニズムの評価

ε-LDPを満たすメカニズムはいくつか考案されているので，どれが良いか評価をする必要があります．実際の運用としては推定値が本当の値からあんまり離れていて欲しくありません．そこで，分散で評価をするということがよく行われています．

$Var(\tilde{c}(i))$ の大きさを各メカニズムごとに求めて，それを比べます．これが小さいということは本当の値から外れた値が生成される確率が小さくなるため，実運用でもうまくいきそうということが分かります．この分散をどうやって小さくするか，実際のデータでの誤差を小さくするというのがLDPの研究ではよく行われています．

まとめ

Differential Privacyについて，ちょっと冗長になってしまった気もしますが．なるべく詳しく説明してみました．ラプラスメカニズムは色々な手法で使われる基本的なものなので，わかっておくと良いと思います．また，それぞれのパラメータが何を意味しているのかなどもできるだけ説明したつもりなので，イメージもつきやすいかと思います．

最後少しだけLDPの説明をしましたが，LDPは実際にGoogleがブラウザでの情報を集めるのに使っているなど実応用とも関わりが強い分野です．同様に複数のクエリに対するDPやストリーミングデータなどの実応用との関わりが深いDPについても説明したかったのですが，少し長くなりすぎたので，次の記事で説明したいと思います．できれば毎週更新していきます．

参考文献

佐久間淳，データ解析におけるプライバシー保護，講談社サイエンティフィク，2016．
Cynthia Dwork. Differential privacy. Encyclopedia of Cryptography and Security, pp. 338-340, 2011.
Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium, pp. 729-745, 2017

kiri1701’s diary

勉強したことや調べたことのまとめ用

Differential Privacy

目次

簡単な背景