RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response 论文阅读
写在前面的话
这篇文章是我在读《AsgLDP: Collecting and Generating Decentralized
Attributed Graphs With Local Differential Privacy》时用到的一篇引文。来自谷歌作者团队，收录于14年的CCS。时间比较久远，但是很经典。这一篇博客写的挺好的点这里。这篇文章还有一点让我比较在意的是它是基于随机响应机制，而不是最常见的拉普拉斯机制和指数机制。
自己的理解（整理）
之前写过这篇文章的部分笔记
大方向：
数据收集过程中的风险同时平衡收集到的数据的有效性。
小方向：
1）隐私与数据的效用问题（隐私问题：直接收集他们的信息可能会损害最终用户的隐私。 数据问题：如果运营商无法收集正确的统计数据，他们就无法为用户带来许多软件和服务改进。）
2）随机响应存在对同一个体重复查询会存在隐私泄露的问题。以及其他匿名化技术也可以通过推理来破坏隐私。
创新点：
找到了众包这个场景，有效解决众包统计数据的问题。
威胁模型：
不受信任的三方
1）攻击者可以访问单个报告
2）攻击者可以访问一个用户的多个报告
3）攻击者能够完全访问客户端所有报告（例如，具有无限访问权限的内部人士）是最难阻止的，但这种攻击在实践中也是最难执行的。
应用领域：云服务运营商需要收集有关其用户活动及其客户端软件的最新统计数据。 在这个领域，RAPPOR已经部署在Google的Chrome Web浏览器中，它已被用于改进用户向谷歌发送的数据。
对策：基于随机响应机制的RAPPOR（匿名数据收集框架）用于保护客户端数据上的人口统计信息的隐私。RAPPOR通过提供差分隐私保证处理来自同一客户端的多个数据收集。高度可调的参数允许根据个人需求很好地平衡隐私和效用。RAPPOR是基于客户端的隐私解决方案。它消除了对可信第三方服务器的需求，并将客户数据的控制权交还给了自己的手中。
技术难点：
1）基于数据多样性如何设计编码解码技术
2）如何实现差分隐私
框架需要实现的效果：允许服务器端在不知道每个单一数据的前提下对数据整体进行分析。
描述：在Bloom Filters运用randomized response，RAPPOR允许收集字符串集合的信息，同时带有DP保证。并且RAPPOR保护重复收集数据的客户端的隐私。RAPPOR可以避免形式上的隐私保护，比如对同一回答保存一个本地结果并每次响应本地结果（可能是linkable的，并被跟踪到）。相比之下，传统的randomized response机制在同一参与者多个信息收集者的情况下不提供任何隐私保护。RAPPOR在本地执行，并且不需要任何可信的第三方。最后，基于假设检验、最小二乘法和LASSO回归，RAPPOR提供了一种新颖的高效用解码框架。
关键技术：随机响应和编码/解码技术
实验：
1）正态分布上的报告
2）字符串集合指数分布上的报告（长尾效应，检测不到频率低）
3）TOP-20的计算结果和真实结果来对比
4）Windows进程调用的实验
5）谷歌页面报告实验
未来研究方向：
1）哈希函数的选择
2）其他Bloom过滤器参数
问题：
1）频率低的串不太能检测出来
2）串之间的线性相关性
攻击模型
我们考虑三种收集RAPPOR报告的不同攻击者。功能最小的攻击者可以从每个用户那里访问单个报告，并且受到关于可能获得多少知识的一次性差异隐私级别ϵ1的限制。该攻击者对应于具有临时窥探用户报告能力的窃听者。
窗口攻击者被认为可以在一段定义良好的时间内访问一个客户端的数据。根据攻击者的学习模型的复杂性，她可以比攻击者了解更多关于用户的信息第一种类型。然而，她侵犯隐私能力的提高却受到了ϵ∞纵向差异隐私保证的严格限制。这个更强大的攻击者可能对应于一个对手，如恶意的云服务员工，他们可能可以临时访问报告，或访问有时间限制的报告日志。
假设第三种类型的攻击者具有无限的收集能力，可以绝对确定地学习永久随机响应B0。由于从B中获得B0的随机化，她也受到ϵ∞的隐私保证的限制，不能通过更多的数据收集来改进这一限制。这对应于最坏情况下的对手，但仍然不能直接访问客户端上的真实数据值。
尽管设想了一个完全本地的隐私模型，用户自己以保护隐私的方式发布数据，然而，RAPPOR集合的操作员可以很容易地操作过程，学习比名义ϵ∞更多的信息。请求用户多次参与一个特定的集合会为每个用户产生多个永久的随机响应，并部分抵消了记忆的好处。在以网络为中心的世界里，用户使用多个账户和多个设备，可以在不知不觉的情况下多次参与，发布的信息比他们预期的更多的信息。这个问题可以通过运行每个帐户的集合和共享一个共同的永久随机响应来在某种程度上得到缓解。注意操作员的角色，以确保这些流程已经到位，以及用户所需或假定的信任。
一些攻击者很可能会通过隔离和分析来自该用户或包含他们的一小群用户的报告来瞄准特定的用户。尽管如此，还是有些随机选择的用户根本不需要担心这样的攻击：当概率为((1/2)f)h时，客户端将生成一个永久的随机响应B0，所有0都在设置的Bloom滤波器位的位置。由于这些客户端没有向收集过程提供任何有用的信息，因此攻击者单独针对它们是适得其反的。攻击者对此特定用户没有任何信息。此外，对于所有用户，在任何时候，都有与不提供信息的客户端比例成比例的合理否认性。
在一个特定的攻击场景中，想象一个攻击者对学习给定客户端是否具有特定的值v感兴趣，其总体频率已知为fv。支持v的最有力证据是在客户端报告中设置的v的两个Bloom过滤器位的形式（如果使用了两个哈希函数）。攻击者可以通过选择具有这两位集的所有报告来制定其目标集。然而，这组将错过一些有v的客户，包括其他没有报告v的客户。错误发现率(FDR)是在目标集中报告与v不同的值的比例。图7显示了FDR作为fv的函数，字符串v的频率。值得注意的是，对于相对罕见的值，目标集中的大多数客户机实际上都有一个不同于v的值，这将有望阻止任何潜在的攻击者。
在低频fv下产生高FDR率的主要原因是，支持v的观测位提供的证据有限。图8清楚地说明了这一点，其中客户端报告（1）或未报告（0）的概率被绘制为fv的函数。对于相对罕见的字符串（那些频率小于10%的字符串），即使在报告中设置了与v对应的两个位，被报告的v的概率也要远远小于它没有被报道。由于先验概率fv很小，单个客户的报告不能提供足够的证据来支持v。
注意事项
尽管RAPPOR提高了最先进的技术，但它并不是灵丹灵药，而是一种工具，当谨慎和正确地使用适合其应用程序上下文的参数时，可以提供显著的好处。即便如此，RAPPOR也应该只作为一个全面的隐私保护策略的一部分来使用，该策略应该包括有限的数据保留和其他实用过程，并且已经被云运营商使用。
与之前关于数据库记录差分隐私的工作一样，RAPPOR为单个客户端的响应提供了隐私保证。我们的方法的局限性之一与当受访者使用参与同一收集事件的几个客户时，额外信息的“泄漏”有关。在现实世界中，这个问题通过将不同的客户连接到同一参与者的内在困难而在某种程度上得到了缓解。当同时收集高度相关，甚至完全相同的谓词时，也会出现类似的问题。然而，这个问题大多可以通过仔细的收集设计来处理。
这种无意的相关性可能在RAPPOR应用程序中以许多不同的方式出现，在每种情况下都可能导致从单个客户端或用户收集到过多的相关信息，并相应地降低隐私保证。显然，如果从每个客户端对太多不同的客户端属性收集RAPPOR报告，则更有可能发生这种情况。然而，它可能也会以更微妙的方式发生。例如，收集设计中使用的队列数量必须仔细选择并随着时间的推移而改变，以避免隐私影响；否则，队列可能很小，以促进客户的跟踪，或者客户可能随着时间的推移作为不同队列的一部分报告，这将降低他们的隐私。RAPPOR响应甚至会影响客户端的匿名性，当它们在所有客户端上相同的不可变客户端值上收集时：如果响应包含太多的位(例如，Bloom过滤器太大)，这将有助于跟踪客户端，因为永久随机响应的位是相关的。其中一些问题可能不适用于实践中（例如，由于加密，跟踪响应可能不可行），但必须在RAPPOR集合设计中考虑。
特别是，由永久随机响应保证的纵向隐私保护假设客户的价值不会随着时间而变化。只有如果值变化非常慢，才会轻微违反。在来自单个用户的相关值流快速变化的情况下，必须采取额外的措施来保证纵向隐私。实施这一措施的实际方法是随着时间的推移为隐私预算制定预算，在每份报告上花费一小部分。在RAPPOR算法中，这将相当于让q在每个收集事件中越来越接近p。
因为差分隐私处理的是最坏的情况，所以bloom滤波器引入的不确定性在其边界的计算中没有发挥任何作用。根据随机抽取，在Bloom过滤器中可能有多个映射到相同h位的候选字符串。然而，对于平均情况的隐私分析，Bloom过滤器确实提供了额外的隐私保护(一种k匿名的味道)，因为很难从其Bloom过滤器表示B[4]可靠地推断客户的值v。
相关工作
从客户那里收集一种保护他们的隐私，同时实现有意义的汇总推断的数据，这是学术界和工业界一个活跃的研究领域。我们的工作适合一类最近探索的问题，一个不受信任的聚合器希望学习客户端数据中的“heavy hitters”，或者在聚合数据上运行某些类型的学习算法，同时保证每个贡献客户端的隐私，在某些情况下，将客户端通信的数量限制到不受信任的聚合器[7,16,18,20]。我们的贡献是提出了一种已经探索的替代方案，直观，易于实现，可能更适合某些学习问题，并为我们的方法提供详细的统计解码方法，以及关于其性能的实验数据。此外，除了保证不同的隐私外，我们还采取了明确的算法步骤，以防止来自同一用户的报告之间的可链接性。
我们很自然地会问，为什么我们的机制建立在随机反应之上，而不是建立在两个最常用于实现不同隐私的原语上：拉普拉斯和指数机制[12,21]。拉普拉斯机制不合适，因为客户端报告的值可能是分类的，而不是数字的，在这种情况下，直接的噪声添加没有语义意义。指数机制不适用，因为我们希望在本地模型中实现系统，其中每个客户端单独确保隐私，而不需要受信任的第三方。在这种情况下，客户端没有关于数据空间的足够信息，以便进行指数机制所需的必要的有偏采样。最后，随机响应还有一个额外的好处，即相对容易向最终用户解释，这使得关于用于确保隐私的算法的推理比其他实现差异隐私的机制更容易访问。
使用各种降维技术来提高算法的隐私特性，同时保留实用程序也是相当常见的[1,17,20,22]。虽然我们依赖Bloom过滤器是由希望获得一个紧凑的数据表示以降低每个客户的潜在传输成本和希望使用技术已经广泛采用在实践[6]，相关工作关于隐私可能是乐观的来源[4]。可以想象，通过仔细选择哈希函数，或选择其他Bloom过滤器参数，可能有可能进一步提高对攻击者的隐私防御，尽管我们还没有详细探索这个方向。
与我们最相似的作品是Mishra和桑德勒[24]。我们工作的主要附加贡献之一是更广泛的解码步骤，它提供了收集的数据的实验和统计分析，这些查询比他们在工作中考虑的数据更复杂。第二个区别是我们使用了第二个随机化步骤，即瞬时随机响应，以便使链接来自单个用户的报告的任务变得困难，以及攻击者能力的更详细的模型。
消除需要信任聚合器的挑战也被分布式解决方案解决，该解决方案信任其他客户端[11]。通过这种方式，差分隐私协议可以通过分布式用户数据实现，通过依赖于诚实但好奇的代理或聚合器，受某些承诺[2,8]的约束。
有几项工作旨在解决具有隐私纵向数据收集的问题。最近的一些工作考虑了对同一数据集询问许多谓词查询的场景，它使用了一种方法，而不是为每个答案单独提供随机化，而是试图基于之前给出的其他查询[25]的答案来重建一些查询的答案。RAPPOR的高水平思想与该技术有一些相似之处——瞬时随机反应正在重复使用永久随机响应步骤的结果。然而，总体目标是不同的——RAPPOR不是回答不同数量的查询，而是通过数据收集到同一查询的报告，这些数据可能会随着时间的推移而变化。虽然它不在与RAPPOR相同的本地模式下运行，但最近关于泛私人流媒体和持续观察下的隐私的工作引入了与隐私[13,14]的纵向数据收集相关的额外想法。
总结
RAPPOR是一个灵活的、数学上严格的和实用的匿名数据收集平台，用于保护隐私的人口统计众包在客户端数据上。RAPPOR通过提供定义良好的纵向差分隐私保证，优雅地处理来自同一客户端的多个数据收集。高度可调的参数允许平衡风险和效用，这取决于一个人的需求和评估不同的攻击模型的可能性。RAPPOR纯粹是一个基于客户端的隐私解决方案。它消除了对受信任的第三方服务器的需要，并将对客户机数据的控制权交回了他们自己的手中。
