满足Local Differential Privacy(LDP)的五种编码的介绍

如果一个算法$A$满足$\epsilon$-local differential privacy($\epsilon$-LDP)，其中$\epsilon \ge 0$，当且仅当对于任意的输入$v_1,v_2$，有
$$\forall y\in Range(A):Pr[A(v_1)=y]\le e^{\epsilon }Pr[A(v_2)=y],$$
其中$Range(A)$表示算法$A$的所有可能输出的值。

LDP的基本应用是频度估计（即，从n个数据里，统计每个值的出现次数），它可以归结为下面的3个步骤：

1. Encode即编码，由每个用户执行：
   – 输入一个值$v$；输出一个编码后的值$x$，即$x=Encode(v)$；
2. Perturb即扰动，由每个用户执行：
   – 输入一个编码后的值$x$，输出扰动后的值$y$，即$y=Perturb(x)=Perturb(Encode(v))$，后面简记为$y=PE(v)$；
3. Aggregate即收集，由收集者(Aggregator)执行：
   – 将所有用户扰动后的值$y$收集，输出处理后的信息，如频度估计。
   
   本文将介绍17-USENIX-Locally Differentially private Protocols for Frequency Estimation¹中所描述的满足LDP的五种编码方法，对它们的比较主要是两个指标：
4. 隐私保护程度$\epsilon$，
5. 频度估计（frequency estimation）的方差$Var(\tilde{c}(i))$。

1. Basic RAPPOR 简化版

规定输入$v$的值是有限的，为$d$个。不失一般性，我们$v$取$1$到$d$的整数，即$v\in [1,d],v\in N$。

1. Encoding: 将输入的整数转化成长度为$d$ 的01串，对应位取$1$，其余位取$0$，即$Encode(v)=B_0$，其中$B_0$是长度为$d$的01串，并保证$B_0[v]=1,B_0[i]=0,i\ne v$。如$d=5,v=3$，则$B_0=00100$;
2. Perturbing: （Rapper是有两次扰动的，此处简化仅考虑一次）01串$B_0$的每一位分别以$p$（一般来说，$p\ge \frac{1}{2}$）的概率保持，以$q=1-p$的概率反转，产生扰动后的01串$B_1$，即：
   $$Pr[B_1[i]=1]=\{\begin{array}{cr}p,& if{B}_0[i]=1,\\ q=1-p,& if{B}_0[i]=0.\end{array}$$
3. Aggregation: 收集者可以收集到所有用户（设有n个）扰动后的01串$B_1$，按位估计出原始的个数。记第$i$位为$1$的用户个数为$c(i)$，依此可以估计出扰动前$B_0$中第$i$位为$1$的用户个数$\tilde{c}(i)$，扰动前的第$i$ 位为$1$的有$p$的概率保持，为$0$的有$q=1-p$的概率反转：
   $$\begin{array}{rl}& p\cdot c\\ \Rightarrow & \\ \Rightarrow & \end{array}$$