pass
乱択アルゴリズム$ \mathcal{K} $が $\epsilon$-Differential Privacyを満たすとは、最大で1つ要素が異なる2つのデータセット$ D_1, D_2 $に対して、任意の部分集合$ S \subseteq Range(\mathcal{K}) $に対して以下が成り立つことを言う。 \begin{equation} \frac{Pr[\mathcal{K}(D_1) \in S]}{Pr[\mathcal{K}(D_2) \in S]} \leq e^\epsilon \end{equation}
筆者注:差分プライバシーの設定は以下のようになっている。
登場人物
差分プライバシーの手順
End of 筆者注
Differential Privacyの問題点はユーザがデータベース管理者を信用する必要があることである。ユーザはデータベース管理者が正しくアルゴリズムを実行しているかを確認することができない。この問題を解決するために、Local Differential Privacyが提案された。
アルゴリズム$\pi$が$\epsilon$-Local Differential Privacyを満たすとは、入力$v$, $v’$に対して以下が成り立つことを言う。 \begin{equation} \forall y \in Range(\pi): \frac{Pr[\pi(v) = y]}{Pr[\pi(v’) = y]} \leq e^\epsilon \end{equation}
筆者注:差分プライバシーの設定は以下のようになっている。
登場人物
差分プライバシーの手順
End of 筆者注
Local Differential Privacyで使われるRandomized responseの例を以下に示す。Random responseはGoogleのRAPPORにも使われている。
回答者はコインを一度投げる
真のYesの割合は$2(X-0.25)$で推定できる。ただし、$X$は「Yes」を提供した割合である。
Local Differential PrivacyはGlobal Differential Privacyよりも強いプライバシー保護を提供するが、その代わりにデータの品質が低下する。Global Differential Privacyではラプラスノイズの大きさの下界は$O(1/\epsilon)$のオーダに従うが、Local Differential Privacyのラプラスノイズの大きさの下界は$O(\sqrt{n}/\epsilon)$に従う。ただし、$n$は情報提供者数である。
RAPPORはChromeで使われている。RAPPORはLocal Differential Privacyを満たすようなメカニズムである。RAPPORは以下のような手順で動作する。
サーバへの応答はk個のビットベクトルである。ベクトルの中身はkこのカテゴリであってもよく、ランダム化された応答と組み合わせてブルーム・フィルターを使用することで、カテゴリー以外の特性に関する統計を収集することも可能である。
$h$個のhash関数を使ったサイズが$k$のブルームフィルター$B$を考える。 RAPPORの手順は以下の通りである。
永続的Randomized Responseは以下のようにする。 プライバシーを保証するパラメータ$f$を使って、 \begin{equation} B_i’ = \begin{cases} 1,& \text{with probability } \frac{1}{2}f \\ 0,& \text{with probability } \frac{1}{2}f \\ B_i,& \text{with probability } 1-f \end{cases} \end{equation} ただし、$B_i’$は元のブルームフィルターの$i$番目のビットである。永続的Randomized Responseは覚えておく。
一時的Randomized Responseは以下のようにする。長さが$k$のベクトル$S$は初期値が全て0である。 randomized responseパラメータ$p,q$を用いて、$S$の$i$番目の要素$S_i$は以下のようにする。 \begin{equation} P(S_i=1) = \begin{cases} q,& \text{if} B_i’ = 1 \\ p,& \text{if} B_i’ = 0 \end{cases} \end{equation}
ErlingssonらのPARRORアルゴリズムの修正では、あたいを一度だけ遅らせる場合は一時的ランダム化ステップを飛ばして、永続的Randomized Response $B_i’$を送ることができる。 この場合、$\epsilon_1$-LDPを満たす。 \begin{equation} \epsilon_1 = 2h\ln\frac{1-\frac{1}{2}f}{\frac{1}{2}f} \end{equation}
一時的Randomized Responseを行った後のベクトルが1である確率は、生のブルームフィルターの値ごとに \begin{equation} q’=P(S_i=1|B_i=1) = \frac{1}{2}f(p+q)+(1-f)q p’=P(S_i=1|B_i=0) = \frac{1}{2}f(p+1)+(1-f)p \end{equation} であるから、$\epsilon_2$-LDPを満たす。 \begin{equation} \epsilon_2 = h\ln\frac{q’(1-p’)}{p’(1-q’)} \end{equation}
アップルは絵文字の利用頻度推定をするためにデータストリームを線型以下のメモリで処理する確率的データ構造のcount-mean sketch (CMS)を使っている。 CMSはcount min sketchの亜種である。
サーバサイドでの処理は以下のように行う。
クライアントサイドの処理は以下のようにおこう。
プライバシーパラメータ$\epsilon$に対して、$\epsilon$-LDPを維持しながら$d\in D$を送ることを考える。
Appleの実装は透明性がなく、Tangらの研究によると、1回の通信の$\epsilon$は1~2であるが、一日に16回まで許されているため、一日の$\epsilon$は16にもなることがある。
LDPの核となる問題はユーザ側でプライバシーを守る頻度推定である。 定義域$\mathcal{D}$が与えられた時、Frequency Oracle (FO)は要素$d\in\mathcal{D}$の出現回数を推定するプロトコルである。
WangらはFOを3つのステップに分割した。
WangらはPurturbとEncodeからなるPEを純粋なLDPとして定義した
Pure LDPの定義は以下の通りである。
PEと台によって与えられるプロトコルが純粋であるとは全ての$v_1$に対して、以下を満たすような$p^* > q^*$となる二つの確率が存在することである。
\begin{equation} Pr[PE(v_1) \in \{y | v_1\in Support(y)\}] = p^* \\ \forall_{v_1\not= v_2} Pr[PE(v_2) \in \{y | v_1\in Support(y)\}] = q^* \end{equation}
式の理解
$ \{y | v_1\in Support(y)\} $ を $v_1$ の台の集合と呼ぶ。 $ p^* $ はどんな$v_1$は自身の台の集合へ射影される確率である。 $ q^* $ は任意の他の値が$v_1$の台の集合へ射影される確率である。
$\epsilon$-LDPを満たすために、
が必要である。Pure LDPを満たすためにはすべたの値に対して$ p^* $が同じ値を取り、全てのペアに対して$ q^* $が同じ値を取る必要がある。 iの真の頻度の推定はユーザ$j$の回答を$y_j$とすると、
\begin{equation} \hat{c}(i) = \frac{\sum_{j}\mathbb{1}_{support(y_j)}(i)-nq^* }{ p^* - q^* } \end{equation}
Wangらは多くの既存手法を一般化したPure LDP FOプロトコルのフレームワークを提案した。 かわえて、4つのEncodeテクニックを提案した。
$\text{Encode}(v)=v$とし、Perturbは
\begin{equation} Pr[Perturb(x) = i] = \begin{cases} p = \frac{\exp^\epsilon}{\exp^\epsilon+|D|-1} \\ q = \frac{1-p}{|D|-1} = \frac{1}{\exp^\epsilon+|D|-1} \end{cases} \end{equation}
Aggregateは$\hat{c}$を用いてカウントする。 分散が$D$に対して線形という欠点がある。
Encodeとしてv番目の要素だけ1で他は0のベクトルを返す。 Perturbはラプラスノイズ$Pr[Lap(\beta)=x]=\frac{1}{2\beta}\exp^{-|x|/\beta}$を用いて$B’[i]=B[i]+Lap(\beta)$とする。
Aggregateは全てのユーザの値を足すSummation with Histogram Encoding (SHE) と閾値を超えたら1を返すThreshold with Histogram Encoding (THE) がある。 THEの方が分散が優れている。
Encodeとしてv番目の要素だけ1で他は0のベクトルを返す。 Perturbは \begin{equation} Pr[Perturb(x) = i] = \begin{cases} p, \text{if} B[i]=1 \\ q, \text{if} B[i]=0 \end{cases} \end{equation}
RAPPORと同じSymmetric Unary Encoding (SUE)は$p+q=1$を用いる。 WangらのOptimized Unary Encoding (OUE) では$p=\frac{1}{2}$、$q=\frac{1}{\exp^\epsilon+1}$を用いる。 OEUは最適なパラメータで、より誤差が小さい。
Binary Local Hashingは通信コストを下げるために用いられる。
$d\in D$を1ビットに射影するハッシュ関数のすべての集合$\mathbb{H}$が以下を満たしているとする。 \begin{equation} \forall x, y\in D, x \not= y: Pr_{H\in\mathbb{H}}[H(x)=H(y)] \le \frac{1}{2} \end{equation}
Encodeは一様ランダムに選んだハッシュ関数$H\in\mathbb{H}$を使って$b=H(v)$としたとき、$\text{Encode}(v)=\langle H, b\rangle$とする。 Perturbの出力は \begin{equation} Pr[b’ = 1] = \begin{cases} p=\frac{\exp^\epsilon}{\exp^\epsilon+1}, \text{if} b=1 \\ q=\frac{1}{\exp^\epsilon+1}, \text{if} b=0 \end{cases} \end{equation}
Optimal Local HashingはBinary Local Hashingの一般化で、出力が$[g], g\ge2$である。 $g=\exp^\epsilon+1$が最適である。
Encodeは一様ランダムに選んだハッシュ関数$H\in\mathbb{H}$を使って$b=H(v)$としたとき、$\text{Encode}(v)=\langle H, b\rangle$とする。 Perturbの出力は \begin{equation} Pr[b’ = 1] = \begin{cases} p=\frac{\exp^\epsilon}{\exp^\epsilon+g-1}, \text{if} b=i \\ q=\frac{1}{\exp^\epsilon+g-1}, \text{if} b\not=i \end{cases} \end{equation}
ローカルモデルのヘビーヒッター同定問題では、ユーザーの集合の中で共通のドメイン要素(ヘビーヒッター)の頻度を推定したい。
ユーザ$u$が設定できるプライバシー仕様$(\tau, \epsilon)$、ランダムかアルゴリズム$\pi$が与えられているとする。 ユーザ$u$の$(\tau, \epsilon)$-personalized local differential privacy (PLDP)を満たすとは、二つの地域$l$, $l’$と任意の部分集合$O\subseteq Range(A)$に対して以下が成り立つことを言う。 \begin{equation} \frac{Pr[\pi(l)\in O]}{\pi(l’)\in O} \le e^\epsilon \end{equation}
$\tau$はユーザごとに安全領域と呼ばれる位置情報の解像度を制御するためのパラメータである。$\tau=L$として、位置情報の解像度を最低にすると$\epsilon$-LDPになる。
pass