Local Differential Privacy: a Tutorial

• https://arxiv.org/abs/1907.11908

内容

Introduction

pass

Local Differential Privacy

乱択アルゴリズム$\mathcal{K}$が $\epsilon$-Differential Privacyを満たすとは、最大で１つ要素が異なる２つのデータセット$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}$$

筆者注：差分プライバシーの設定は以下のようになっている。

登場人物

• 情報提供者は情報を提供するが、プライバシーを守りたい
• 信頼できるデータベース管理者は情報を受け取り、情報提供者のプライバシーを守りながら分析者に情報を提供する
• 分析者はデータを分析したい

差分プライバシーの手順

1. 情報提供者はデータをデータベース管理者に生の個人情報を提供する
2. データベース管理者は情報提供者たちから集めたデータを使って統計値を計算する
3. データベース管理者は統計値に差分プライバシーを満たすようなメカニズムを使ってノイズを加える
4. 分析者はノイズを加えた統計値を使って分析を行う

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}$$

筆者注：差分プライバシーの設定は以下のようになっている。

登場人物

• 情報提供者は情報を提供するが、プライバシーを守りたい
• 分析者はデータを分析したい

差分プライバシーの手順

1. 情報提供者はデータに局所差分プライバシーを満たすようなメカニズムを使ってノイズを加えて分析者に提供する
2. 分析者は情報提供者から提供されたノイズを加えられたデータを使って分析を行う

End of 筆者注

Randomized response

Local Differential Privacyで使われるRandomized responseの例を以下に示す。Random responseはGoogleのRAPPORにも使われている。

回答者はコインを一度投げる

1. 表だったら真の回答を提供する
2. 裏だったらコインをもう一度投げる
   1. 表だったら「Yes」を提供する
   2. 裏だったら「No」を提供する

真のYesの割合は$2(X-0.25)$で推定できる。ただし、$X$は「Yes」を提供した割合である。

Challenges in the local model

Local Differential PrivacyはGlobal Differential Privacyよりも強いプライバシー保護を提供するが、その代わりにデータの品質が低下する。Global Differential Privacyではラプラスノイズの大きさの下界は$O(1/\epsilon)$のオーダに従うが、Local Differential Privacyのラプラスノイズの大きさの下界は$O(\sqrt{n}/\epsilon)$に従う。ただし、$n$は情報提供者数である。

RAPPOR

RAPPORはChromeで使われている。RAPPORはLocal Differential Privacyを満たすようなメカニズムである。RAPPORは以下のような手順で動作する。

サーバへの応答はk個のビットベクトルである。ベクトルの中身はkこのカテゴリであってもよく、ランダム化された応答と組み合わせてブルーム・フィルターを使用することで、カテゴリー以外の特性に関する統計を収集することも可能である。

$h$個のhash関数を使ったサイズが$k$のブルームフィルター$B$を考える。 RAPPORの手順は以下の通りである。

1. 永続的Randomized Responseを適用する
2. 一時的Randomized Responseを適用する

永続的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を行った後のベクトルが１である確率は、生のブルームフィルターの値ごとに $$\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}$$

Apple’s implementation of LDP

アップルは絵文字の利用頻度推定をするためにデータストリームを線型以下のメモリで処理する確率的データ構造のcount-mean sketch (CMS)を使っている。 CMSはcount min sketchの亜種である。

サーバサイドでの処理は以下のように行う。

1. $k$個のHash関数を用いた$m\times k$の行列$M$を用意する。$M$の初期値は全て0である。
2. クライアントはデータ$d\in D$に対してサイズ$m$のベクトルを作成し、サーバサイドに送る。
3. クエリ：要素$d$の出現回数を推定するためには、各ハッシュ関数に$d$を入力し、各行で得られた列の値を調べる。CMSでは最小値ではなく平均値を使う。

クライアントサイドの処理は以下のようにおこう。

プライバシーパラメータ$\epsilon$に対して、$\epsilon$-LDPを維持しながら$d\in D$を送ることを考える。

1. $k$個のハッシュ関数から一様ランダムに一つを選ぶ。
2. encoding vector $v \in {-1,1}^m$を用意し、$h(d)$の要素に1を代入、他の要素は-1を代入する。
3. 各要素を$\frac{1}{1+\exp^{\epsilon/2}}$の確率で反転する。
4. サーバサイドに送る。

Appleの実装は透明性がなく、Tangらの研究によると、1回の通信の$\epsilon$は1~2であるが、一日に16回まで許されているため、一日の$\epsilon$は16にもなることがある。

Frequency Oracles

LDPの核となる問題はユーザ側でプライバシーを守る頻度推定である。 定義域$\mathcal{D}$が与えられた時、Frequency Oracle (FO)は要素$d\in\mathcal{D}$の出現回数を推定するプロトコルである。

WangらはFOを３つのステップに分割した。

1. Encode: ユーザがそれぞれの回答をエンコードする
2. Perturb: 回答に摂動を加える
3. Aggregate: サーバがエンコードされた回答を集計する

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を満たすために、

• $q^*>0$
• $\frac{ p^* }{ q^* } \le \exp^\epsilon$

が必要である。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プロトコルのフレームワークを提案した。 かわえて、４つのEncodeテクニックを提案した。

1. Direct Encoding(DE)
2. Histogram Encoding (HE)
3. Unary Encoding (UE)
4. Binary Local Hashing (BLH)

Direct Encoding

$\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$に対して線形という欠点がある。

Histogram Encoding

Encodeとしてv番目の要素だけ１で他は０のベクトルを返す。 Perturbはラプラスノイズ$Pr[Lap(\beta)=x]=\frac{1}{2\beta}\exp^{-|x|/\beta}$を用いて$B’[i]=B[i]+Lap(\beta)$とする。

Aggregateは全てのユーザの値を足すSummation with Histogram Encoding (SHE) と閾値を超えたら１を返すThreshold with Histogram Encoding (THE) がある。 THEの方が分散が優れている。

Unary Encoding

Encodeとしてv番目の要素だけ１で他は０のベクトルを返す。 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

Binary Local Hashingは通信コストを下げるために用いられる。

$d\in D$を１ビットに射影するハッシュ関数のすべての集合$\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 (OLH)

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}$$

• OLHとOUEは同じ分散を持つ。
• OLHのコミュニケーションコストは$O(\log|D|)$の一方で、OUEのコミュニケーションコストは$O(|D|)$である。

まとめ

• $|D|<3\exp^\epsilon+2$のとき、DEは最適である。
• $|D|>3\exp^\epsilon+2$のとき、OEUとOLHは最適である。
• OLHのコミュニケーションコストは$O(\log|D|)$の一方で、OUEのコミュニケーションコストは$O(|D|)$である。

Heavy Hitter Identification

ローカルモデルのヘビーヒッター同定問題では、ユーザーの集合の中で共通のドメイン要素（ヘビーヒッター）の頻度を推定したい。

問題設定

• n人のユーザが$x_i\in D$の入力を持っている
• 全てのユーザの入力からなる分散データベース $S=(x_1,\dots,x_n)$がある
• Sの要素の少なくとも$\delta$倍である要素$x\in D$を$\delta$-heavyと呼ぶ
• できるだけ小さな$\delta$に対して、$\delta$-heavyな要素（ヘビーヒッター）を特定したい
• $\delta$より小さい頻度を持つ要素も除外されるわけではないので、$\delta$をプロトコルの誤差とも呼ぶ

関連研究

• Bassily and Smithはsuccinct histogramという簡潔データ構造を使って局所差分プライバシーを保障しながらヘビーヒッターを特定するアルゴリズムを提案した
• Bassilyらは二分プレフィックス木を使ったTreeHistと公開されている行列$Z\in \{-1, 1\}^{|D|\times n}$を利用してPerturbするBitstogramを提案した
• 上記のアルゴリズムは$\epsilon$-LDPを保障したヘビーヒッター同定問題の最悪ケースの下界を達成しない
• Bunらはfrequency oracle HashtogramをベースにしたPrivateExpanderSketchを提案し、下界を達成することを示した。

Itemset mining

問題設定

• アイテムセットマイニング問題は、局所差分プライバシー設定において、単一値入力ではなく、集合値入力に関する統計量の収集を扱うThakurta。
• 頻度オラクルおよびヘビーヒッタープロトコルは、十分に大きな母集団サイズによって付加されたノイズをフィルタリ ングすることで機能するため、アイテムセットの設定にこれらを適用することは不可能である。

関連研究

• Qinらは２段階のフェーズでアイテムセットマイニングを行うLDPMinerを提案した。
  1. heavy hitterを特定する
  2. 頻度を推定する
• BassilyらはQinらの研究をベースにsuccinct histogramの亜種のsampling succinct histogramを用いて、RAPPORの亜種のsampling RAPPORを提案した。
• Wangらは新しいSet-Value Item Mining (SVIM) protocolを提案し、LDPMinerより大幅に性能を改善した上、未解決だった頻出アイテム集合の同定問題を解決した。
  • padding-and-sample-based frequency oracles (PSFO)というQinらのsampling randomizer algorithmによってサンプリングすることでプライバシーパラメータが改善する（＝プライバシーが守りやすくなる）というprivacy amplicationというアイデアをベースにしている。
  • privacy amplicationの効果はGeneralized Random Responseにはあるが、Optimized Local Hash２はないので、アイテム集合のサイズに基づいて適応的に利用する頻度オラクルプロトコルを選択する($|J|>(4\ell^2-\ell)\cdot\exp^\epsilon+1$ならば、Generalized Random Responseを利用)ことを提案している
  • SVIMプロトコルは以下の４つのステップからなる。ユーザを４つのグループに分け、それぞれのグループに１つのタスクだけ行わせる。
    1. ユーザは小さな$\ell$を使って入力を報告し、分析者はヘビーヒッターを特定して、それをユーザに送る
    2. 標準的頻度オラクルプロトコルを使って、幾つアイテムの候補を持っているかを報告する
    3. $\ell$は分析者が適切に選び、PSFOを用いてユーザは候補のアイテムを報告する。これにより分析者はアイテムの頻度を推定できる。
    4. 分析者は頻度の多い$k$個のアイテムを特定する
• アイテムセットのマイニングは、考慮すべき候補が指数関数的に増えるため、より困難である。これに対処するため、Wangらは頻出アイテムセットを効率的に見つけるSVSMを導入した。
• SVIMはLDPMinerを性能で大幅に上回り、SVSMはオープンプロブレムであった頻出アイテムセットの同定問題を解決した。

Private Spatial Data Collection

• Google MapsやWazeのような多くのサービスは、人気のある場所を特定したり、渋滞マップを作成したりするために、ユーザーデータの収集から利益を得ている。
• 多数のユーザーとその位置データが与えられた場合、ユーザーのプライバシーを維持しながら、空間領域上の分布を学習したい。
• Chenらは、個別化局所差分プライバシー(Personalized Local Differential Privacy: PLDP)の概念を導入し、各ユーザのPDPを保証しながら、空間領域(location universe)上のユーザ分布を学習できるフレームワークを提案している。

Personalized Local Differential Privacy

ユーザ$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になる。

PSDA Framework

• Chenらは、プライベート空間データ集約（PSDA）フレームワークを提案した
• 与えられた地域内のユーザ数をカウントするには以下のようなpersonalized count estimation protocol (PCEP)を使う
  • nユーザの地域とプライバシー仕様とaccuracyを制御する$\beta$が与えられた元で$(\tau, \epsilon)$-PLDPを満たすように報告された地域に摂動を加える
  • 同じ安全領域を持つユーザを真のユーザカウント$s_l$と推定したユーザカウント$\hat{s}_l$の絶対誤差の最大値 $\max_{l \in L}| \hat{s}_l - s_l |$ を小さくするようにクラスタリングする。
  • 信頼できないサーバはそれぞれのクラスタ$C\in\mathbb{C}$に対して信頼パラメータ$\frac{\beta}{|\mathbb{C}|}$に設定するので、信頼水準を$\beta$に設定することができる。
  • サーバは全てのクラスタに対して推定値を組み合わせてカウントを計算する。

Open Problems

• LDPとDPを組み合わせて精度向上
• DNNとLDPを組み合わせる（DPとDNNの組み合わせはうまくいっている）
• クライアントとサーバのやり取りの回数を増やすことで性能を向上させる

Conclusion

pass