大数据时代下的隐私保护(一)

 

1 引言

 

在大数据的时代,越来越多的服务和产品是围绕用户数据(隐私)建立的。这样虽然带来了 个性化的服务,提高了服务质量和精度,但是在数据收集、使用以及公布的过程中,用户隐 私不可避免的暴露在外。历史上就有很多公开的数据暴露了用户隐私的案例,比如AOL 和Netflix 隐私泄露事件。

 

我们的第一篇文章[6] 主要回顾了几种典型的保护隐私的方法和不足:k- anonymity(k- 匿 名 化),l-diversity(l- 多 样 化),t-closeness, 并 简 单 介 绍 了 ε-differential privacy(差分隐私)。这篇文章,我们着重讲解 ε-differential privacy(差 分隐私) 的背景和典型应用。文章从第二章开始,主要讲解差分隐私的定义和典型架构, 典型的噪音添加方法,中心化差分隐私和本地化差分隐私的区别,以及合成定理。接下来, 文章在第三章主要讲解本地化差分隐私的方法和在工业界的应用。其中重点讲解Google的RAPPOR 差分隐私系统[11] 和苹果的差分隐私系统[9]。

 

2 差分隐私背景介绍

 

差分隐私的概念最早由Cynthia Dwork 等人在2006 年提出。区别以往的ad-hoc 隐私保护方案(比如k-anonymity,l-diversity,t-closeness),差分隐私的主要贡献就是提供了个人隐私泄露的数学的定义。差分隐私的主要目的就是提供最大化utility 的查 询结果的同时还保证个人隐私的泄露不超过预先设定的 ε。

 

差分隐私分为中心化差分隐私和本地化差分隐私。两种差分隐私都可以保障单一用户的 ε-差分要求,但应用的场景略有不同。

 

2.1 中心化和本地化差分隐私

 

图1: (中心化)差分隐私处理流程框架。数据收集者从用户那里收集数据, 供数据分析者使用。

 

中心化差分隐私. 概况来讲,差分隐私就是保证一个统计数据库的查询结果不会受到任 何单一用户的隐私数据的影响。因此,攻击者就无法推测任何单一用户的数据。通常模 型里面会考虑两个相邻的数据库(neighboring databases)D 和D′,其中只有一个用 户的数据不同(增加或者删减一个记录)。ε-差分隐私(ε-DP)的定义如下:

 

Definition 2.1. ε-Differefial Privacy (ε-DP) A randomized function Agives ε-differential privacy iff for any two neighboring databases D and D′and for any output O of A

这里的随机函数A 是运行在服务器上面的,本地用户不需要运行任何差分隐私算法。ε 可以看做是隐私预算,它用来量化一个用户隐私泄露的风险。ε 的值越大,隐私泄露的风 险就越大,反之,ε 越小,隐私泄露的风险就越小。在现实中,个人用户的隐私还会有随着查 询的次数增加的风险。这个问题就是所谓的组合定理[3, 8]。

 

一个典型的差分隐私的架构由三部分组成(见图 2):(1)数据源,一般为拥有数据的个人用 户;(2)数据收集者,一般为大型组织或公司;和(3) 数据分析者,包含任何对数据有兴趣的 个体和组织。这样的差分隐私又称作中心化差分隐私。

图2: 本地化差分隐私的处理流程框架。区别于中心化差分隐私需要可信的 数据收集者,本地化差分隐私不需要可信 的数据收集者。

 

本地化差分隐私. 与中心化差分隐私对应的就是本地化差分隐私。ε-本地化差分隐私(ε-LDP)的定义如下:
Definition 2.2. ε-Local Differefial Privacy (ε-LDP) A randomized function A gives ε-differential privacy iff for any two inputs x and x′and for any output y of A,

 

这里的随机函数A 是单独运行在每一个用户本地,中央数据库不需要运行任何差分隐 私算法。本地化差分隐私没有数据库D 和相邻数据库D′的概念。因此需要特定的噪 音算法来应对 ε-LDP 的要求(算法见2.2 章节)。

 

2.2 典型算法

 

概况来讲,差分隐私的主要方法就是扰动(perturbation)和采样(sampling)。对于扰动方 案,就是对输入数据(input),中间数据(intermediate)或者输出数据(output) 进行扰 动,加入噪音(见图3),使其满足 ε-差分隐私。对于输入数据扰动的典型方案就是随机响 应(Randomized Response), 对于输出数据扰动的典型方案就是拉普拉斯算法(Laplace algorithm)。中间数据可以看做前面一个子阶段的输出,也可以看做是后面子 阶段的输入,因此可以灵活选择输入或者输出扰动的算法。  

 

图3: 扰动方法加入噪音的三种位置:1)输入数据(input),2)中间数据(intermediate),和3)输出数据(output)。

 

对于采样方法,典型的算法分为两步。假设查询函数为f。


1. 把数据分成k 份,对每份数据运行查询函数f,得到查询结果f(d1),f(d2),...,f(dk)。
2. 对查询结果应用任何一个满足 ε-差分隐私的算法(例如拉普拉斯算法 或随机响应), 得到最后结果。
这样做的好处就是最后 ε-差分隐私的算法运行在一个较小的数据集f (d1 ), f (d2 ), . . . , f (dk )上面,可以提高差分隐私的运行效率。详细资料可以参考文章[7]。

 

2.2.1 拉普拉斯算法

 

拉普拉斯算法(Laplace algorithm)是最典型的中心化差分隐私算法。简单来说,拉普拉 斯算法(如图4) 就是在真实答案(比如f(D))的基础上加上符合拉普拉斯分布的噪音。噪 音 η 的取值公式为:

 

其中GS_f 的是函数f 的GS(global sensitivity)。GS_f 取值为:

 

对于拉普拉斯算法,他的mean 为0,variance 是2 ∗ (GS_f)2。variance 越小,说明 处理之后的数据集的utility 越高。但是,从variance 的公式我们可以得知variance 和 ε 成反比,也就是说 ε 和utility 成反比。因此,单纯的追求隐私保护或高utility 都 会损坏另外一方。在实际需求中,我们需要寻找一个平衡点。

 

图4: 拉普拉斯噪音算法示意图。

 

拉普拉斯算法只能处理连续型数据。对于非连续型数据,比如性别、种族等,拉普拉斯会 输出无效的数据。对于这样的非连续型数据,我们需要借助于指数算法(Exponential algorithm)。这里就不详细描述了,可以阅读[3]了解细节。

 

2.2.2随机响应算法

 

随机响应算法(Randomized Response)是最典型的本地化差分隐私算法。最早于1965年被Warner 提出,用于对隐私保护。随机响应技术主要包括两个步骤:扰动性统 计和校正。为帮助理解扰动性统计,我们考虑存在一枚非均匀的硬币,其正面向上的概率 为p,反面向上的概率为q,且p+q = 1。 规则是若正面向上则回答真实答案,反面向上 则回答相反的答案。利用上述扰动方法对n 个用户进行是否换艾滋病统计,在抛n 次硬币之后,可以得到艾滋病患者人数为m,没有得病的人为n −m。其中我们假设真实 的患病人数比例为r,我们可以得到扰动后的统计概率:

 

上述统计比例并非真实比例的无偏估计,因此需要对统计结果进行校正。N 表示统计得 到的艾滋病人数估计值:

 

根据总人数n,回答“是”的人数m 和扰动概率p,即可得到真实患病人数的统计值。 为保证其满足 ε- 本地化差分隐私,根据定义,隐私预算 ε 为:

 

上面公式是适用于只有两种选择情况下的 ε-LDP。如果选择种类有d 种,这时候,我们 就需要扩展上面的随机响应算法,得到一个更普遍使用的随即响应算法,记为Generalized Randomized Response (GRR)。对于GRR 算法,同样需要两个步骤:扰动 性统计(π) 和校正(Γ)。针对用户的输入/采样数据为v 在数据集D,本地运行扰动统 计算法 πGRR(v),得到:

 

算法运行得到y,并把结果发送给服务器。这里 πGRR(·) 满足 ε −LDP 。服务器端运 行 ΓGRR(v),得到:

 

其中I_v = |{j|v = y^j}|,也就是服务器上面获得的采样数,和前面例子中的m 相当。这 样获得的 ΓGRR() ̇ 是公正的,其variance 大小为:

 

2.2.3符合差分隐私的k-anonymity

 

通常大家认为k-anonymity 算法是无法满足 ε-差分隐私需求的。这个认知在文章[5] 里面被证明是正确的。有趣的是,对k-anonymity 算法进行一些改进,就可以使其符合 ε-差分隐私。具体操作步骤如下:


1. β-采样(β-sampling)。对数据集里面的每一个tuple 进行采样,使得每个tuple 都 有 β 大小的概率被选中。对采样后的数据,进行数据无关的泛化(data-independent generalization)。比如每k 个相邻年龄进行合并,使其满足k-anonymity。整个算法过程不考虑年龄分布,也就是 所谓的数据无关。因此会有些年龄段合并之后,可能无法满足k-anonymity 的要求。3. 对第二步产生的结果进。

 

2.行筛选,把不满足k-anonymity 要求的数据从最终结果中 剔除出去。这样,剩下的数据既满足k-anonymity 又满足 ε-差分隐私。 整个过程的证明过程可以参考文章[5]。

 

2.3 中心化和本地化差分隐私比较

 

2.3.1可信与不可信的数据收集者

 

中心化差分隐私中一个重要的假设是可信第三方数据收集者。每个用户将自己的真实数 据记录发送给可信的数据收集者。数据收集者会主动保护收集的数据,并使用差分隐私 算法向数据分析者提供查询服务。本地化差分隐私中第三方数据收集者不需要可信。每 个用户按照差分隐私算法在本地对数据进行处理,然后把处理之后的数据上传给数据收 集者。收据收集者无法看到原始数据,因此不需要数据收集者可信。数据收集者接收查 询请求,并直接进行响应,无需在进行中心化的差分隐私。

 

2.3.2噪音机制

 

为保证算法满足 ε-差分隐私,中心化差分隐私和本地化差分隐私都需要噪声机制。中心 化差分隐私的典型噪音机制是:拉普拉斯噪音机制[3] 和指数噪音机制[3]。其中拉普拉斯噪音机制用来处理连续型数据,而指数噪音机制针对离散型数据。上述两种噪声机制均与查询函数的全局敏感性密切相关,而全局敏感性则是定义在D 和D’ 之上,使 得攻击者无法根据统计结果推测任何一个个体的数据。在本地化差分隐私中,每个用户将自己的数据进行扰动后上传,而任意两个用户之间并不知晓其他人的数据记录。也就是说这个时候的统计数据库D 就只有用户自己的记录。也就是说本地化差分隐私中不 存在全局敏感性的概念,因此拉普拉斯噪音机制和指数噪音机制对本地化差分隐私并不 适用。本地化差分隐私主要采用随机响应技术[3] 来保护隐私。

 

2.4 合成定理

 

当我们了解了基础操作的隐私情况,差分隐私的合成定理(Composition Theorem)[4] 可以帮助我们理解和计算一个复杂的算法的隐私。查询次数的上限(Bound on the Number of Queries). 为了保证一定的utility,对于一个统计数据库的查询总会或多 或少的泄露一定程度的个人隐私。因此,这里存在着一个理论上的查询次数上限。根据Dinur Nissim Result 现实,一个拥有n 条记录的数据库,在服务n ×log(n)2 查询之 后, 就可以被重建出来,即使每次查询的结果都有高达O(√n)的噪音。

 

顺序组合(Sequential Composition). 考虑M1, M2, ..., Mk 是在统计数据库D 跑 的不同的差分隐私算法,而且Mi 满足 εi 差分隐私,这样在顺序执行这些算法之后,总 的隐私泄露仍然满足 ε-差分隐私。这个差分隐私大小为所有算法差分隐私的总和 ε= ε1 + ε2 + ···+ εk。

 

并行组合(Parallel Composition). 考虑差分隐私算法M1, M2, ..., Mk 分布跑在在相 邻的统计数据库D1,D2,...,Dk 上面,而且Mi 满足 εi 差分隐私,这样在并发执行这些 算法之后,总的隐私泄露仍然满足 ε-差分隐私。 这个差分隐私大小为所有算法差分隐 私中最大的 ε= max{ε1, ε2, . . . , εk}。

 

后续处理(Postprocessing). 如果Mi 满足 ε-差分隐私,其在统计数据库D 的输出 结果记为Mi(D)。其他任意差分隐私算法Mj 对于Mi 的输出Mj(Mi(D)) 同样满足 ε-差分隐私。

 

3 差分隐私的典型应用

 

这章主要讲解差分隐私在工业界的应用:(1)Google 的RAPPOR,和(2)Apple 的差分 隐私。

 

3.1 RAPPOR 差分隐私系统

 

单值频数统计是指每个用户只发送一个变量取值的情形, 用户将数据发送给数据收集 者后, 数据收集者根据已有的或统计得到候选值列表, 统计其中每一个候选值的频数并 进行发布。

 

RAPPOR 方法是Google 提出的一个通用的差分隐私方法。该方法可以采集用户的数 据并保证 ε 的差分隐私。RAPPOR 可以统计连续型数据(比如年龄),也可以统计非连 续型数据(比如国家)。假设总共有n 个用户,第i 个用户Ui 对应某个敏感取值xi ∈X, 且|X|=k,现在希望统计取值xi(1 ≤i ≤k) 的频数。

图5: RAPPOR 应用实例。真实的值经过bloom lter,PRR 和IRR 之后, 汇报给服务器。最后的数据(256bits) 中有145bits 为1。

 

3.1.1 RAPPOR 算法

 

RAPPOR 算法需要以下几个参数运行。用户可以根据需要调节这几个参数: •k 为bloom filter 产生的数据大小。图5 的例子中k=256。


h 为hash 函数的个数。图5 的例子中h = 4。


f 决定PRR 中每一个bit 翻转的概率。图5的例子中f=0.5。

 

p 决定IRR 中bit 为1 的翻转概率。图5 的例子中p=0.75。


q 决定IRR 中bit 为0 的翻转概率。图5 的例子中q=0.5。 当确定参数之后,RAPPOR 算法输入要收集的真实数据v(图5 中v 是68),并执行以 下四个步骤。

 

1.布隆过滤。对用户的真实数据v,运行h 个hash 函数H = {H1,H2,...,Hh},每个hash 函数输入一个k长的数组[k] = {0, 1, . . . , k−1}.。整合所有输入,得到一个k 长 的数组B。

 

2/永久性随机响应(Permanent Randomized Response,or PRR)。对生成的数组B 的 每一个bit i (0 ≤i < k),进行随机翻转,生成新的数组Bi′。翻转概率公式如下所示:

这里值得注意的是,以后任何需要使用B 的时候,都需要使用相同的Bi′,否则可能会 有”averaging” 攻击[11]。这一步之后,用户的数据就已经获得 ε-差分隐私保护了。

3.瞬时性随机响应(Instantaneous Randomized Response,or IRR)。

 

申请一个k 个bit 长的数组S,并把每个bit 初始化为0。然后根据B′ 的每一个bit, 对S 的相应bit 进行初始化:

 

而且IRR 的结果S 满足对PRR 结果B′ 的postprocessing,即IRR(PRR(v)),使得IRR 的隐私保护同样满足 ε-差分隐私。相对于PRR,IRR 对于保护用户隐私又前进了一 步。(1)IRR 的结果直接隐藏了PRR 的结果B′,使得服务器端很难跟踪PRR 的结果。(2)IRR 允许用户对于短期隐私加入更多噪音,从而获得更强的短期隐私的保护。最后(3),IRR 允许独立的调节短期隐私和长期隐私,使得用户更加灵活的控制自己的隐私。

 

4.汇报数据。 第三步产生的结果S,提交给服务器

 

3.1.2 RAPPOR 的典型变种

 

RAPPOR 还有三种典型的变种来应对不同条件下的差分隐私要求。

 

One-time RAPPOR. 如果服务器只对用户进行一次数据收集,这个时候就可以跳 过IRR 的步骤,直接报告PRR 的结果。
Basic RAPPOR. 如果用户的数据v 可以确定性的映射到一个bit 串,这个时候RAPPOR 可以跳过第一步,即bloom filter 的阶段,直接进行后面的步骤。比如,对于用 户性别的采样,男性和女性可以分别对应一个 bit。这个时候h 取值为1 即可。Basic One-time RAPPOR. 这个是上面两种模式的简单组合,用于最简单的情况。这个 时候RAPPOR 可以直接跳过第一步和第三步。

 

RAPPOR 系统已经在Github 上面开源(google/rappor)。根据Wang et al. [10] 的 分析,里面有两套典型的参数,可以命名为RAPPOR-1 和RAPPOR-2。两个系统的 ε 取值不同:RAPPOR-1 里面 ε= 4.39,而RAPPOR-2 里面 ε= 7.78。实际应用当中, 本地化差分隐私 ε 的取值应该避免大于4。当 ε> 4 的时候,用户的隐私会被很大概 率恢复出来。

 

3.2 苹果差分隐私系统

 

2016 年6 月,苹果宣布使用本地化差分隐私方法收集用户数据[1, 2], 从而保证用户 信息的隐私性。我们在苹果最近的系统macOS Sierra (10.12)和iOS 10 中都看到了 差分隐私的使用,但是苹果没有公开详细介绍使用本地化差分隐私的细节,比如如何选择 隐私参数,同时保证数据的可用性。

 

2017 年9 月,来自南加州大学、清华大学、印第安纳大学的Jun Tang 等人在arxiv.org 上发表了一篇深入研究苹果差分隐私实现方法的文章:Privacy Loss in Apple’s Implementation of Differential Privacy on MacOS 10.12 [9]。本篇文章 通过逆向分析macOS Sierra 上的查分隐私框架,发现苹果在使用差分隐私的一些细 节,包括差分隐私预算数值,在哪些地方使用了差分隐私,使用差分隐私的算法有哪些,收 集信息的频率等等详细信息。

 

3.2.1苹果差分隐私研究概述

 

这篇文章使用了逆向工程的方法,主要研究了macOS 的以下几个模块:差分隐私框架: /System/Library/PrivateFrameworks/DifferentialPrivacy.frameowrk com.apple.dprivacyd 守护进程(daemon)

存放隐私后数据的数据库,地址在/private/var/db/DifferntialPrivacy

 

差分隐私框架的配置件:/System/Library/DifferentialPrivacy/Configuration/ 发送给服务器的报告文件,文件名以.dpsub 和.json.anon结尾,存放在/Library/Logs/DiagnosticReports 和/private/var/db/DifferentialPrivacy/Reports/ 目录中
macOS 中控制台的日志信息

 

通过逆向逻辑,推测苹果在使用差分隐私的细节。目的是想回答以下几个问题:

 

我们知道隐私数据在进入数据库之前,苹果通过差分隐私的算法使数据隐私化,那么隐私 参数(privacy parameters)是多少?
苹果在收集数据时有多频繁?每次收集多少数据? 对于一个特定的用户,总的隐私损失(privacy loss)是多少,是否有限制? 修改这个差分隐私系统的难度如何?

 

3.2.2苹果差分隐私系统实现细节

 

通过逆向之前介绍的几个模块,我们能得到以下表格6 的信息:

图6: 苹果差分隐私详细数据

 

从表格中我们可以看到,苹果主要收集了输入法的新词语、emoji 的使用频 率,AppDeepLink 的使用数据,健康数据,查询数据。对应的差分隐私算 有 “CountMedianSketch”,“OneBitHistogram”。除此之外,文章还参考了algorithmparameters.plist 和budgetproperties.plist 两个文件。 通过对相关文件 的研究发现,PrivacyParameter的数值规定了用于隐私化数据的隐私参数。文章同时研 究了报告的生成方法和隐私预算的管理,发现SessionAmount 数值规定了有多少记录将被收集,隐私化后传给苹果。同时SessionAmount 也规定了对于一个BudgeKeyName 的剩余隐私预算有多少。 剩余的隐私预算和SessionAmount 用 做决定有多少记录将被写入报告文件中。每隔18 个小时,守护进程将运行一个叫做 “ReportGenerator” 的任务,这个任务会根据SessionAmount 数值以及隐私预算 剩余算出又多少数据将会上报给苹果。同时,有一个不断执行的任务叫 “PrivacyBudgetMaintenance”会提高隐私预算,详细的讲,每隔24 个小时,所有的 隐私预算(除了health 和默认值)将会增加。

 

通过以上结论,我们能够计算出苹果差分隐私的隐私损失(privacy loss): 每隔SessionSeconds 损失PrivacyParameter ·SessionAmount 的数量。所以,对于NewWords,AppDeepLink, Search, Emoji, 他 们 的PrivacyParameter 是2,1,1,1,SessionAmounts 是2,10,1,1,SessionSeconds 是864000,所以,每天总的 隐私损失是16。

 

除了以上结论,文章还讨论了苹果在管理数据库的一些任务,比如说“StorageCulling” 任务每隔24 小时会删除已经报告给苹果的记录。苹果在不同版本的macOS 上使用 的隐私参数也不同,收集的数据也有所不同。

 

3.2.3苹果差分隐私研究结论

 

文章最后讨论了苹果这种本地部署差分隐私方式存在的一些缺点:

 

苹果没有给用户公开差分隐私的参数,这违背了差分隐私的初衷:用户能够了解在收集数 据的过程中有多少隐私泄露出去。 正因为如此,使得苹果有意或无意的滥用差分隐私的功能收集数据,比如说,通过修改某 些隐私参数,苹果可以大大的降低隐私化数据的数量,使数据更精确。 苹果的隐私损失是16/天,这大大高于研究界对于差分隐私损失的合理定义,不仅如此, 隐私损失每天都会补充,长时间会影响总的隐私损失。 因为苹果数据库的结构,用户的某些隐私还是会被泄露,比如说用户的使用语言,地域,键 盘偏好等等。 总结来讲,这篇文章通过逆向苹果差分隐私框架,详细的了解了苹果在实现差分隐私当中 的细节,发现了一些实现上的问题,使得隐私损失不断变大。文章并没有对于苹果的差分 隐私算法做过多的讨论,比如说 “CountMedianSketch”,“OneBitHistogram”。根 据名称,我们还是能够推测可能是使用了sketch 的相关统计学算法。差分隐私虽然在 理论上讨论的比较充分, 在工业界的使用才刚刚开始,每个细节的错误使用都会对用户 的隐私造成巨大的影响。

 

4 结论

 

本文首先介绍了差分隐私的基础概念,典型算法和典型的差分隐私模型的区别。差分隐 私能够从理论上准确的限定隐私泄露的上限,这也是它优于传统的隐私保护方案(k-anonymity,l-diversity 和t-closeness)的主要特点。 随后文章重点讲解两个工业 界的差分隐私的例子:Google 的RAPPOR系统和苹果的差分隐私。这两个差分隐私 系统都是本地化差分隐私(LDP),所使用的 ε 对用户隐私的保护还不尽如人意(尤其是苹果的差分隐私)。希望以后有更多的学者和企业加入到差分隐私的研究和应用当中,全 面提高差分隐私的保护效果和算法效率。

 

参考文献

[1] Apple. Engineering privacy for your users. https://developer. apple.com/videos/play/wwdc2016/709/.

[2] Apple. Wwdc 2016 keynote. https://www.apple.com/apple-events/ june-2016/. 

[3] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of di erential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

[4] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for di erential privacy. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, pages 1376–1385. JMLR.org, 2015. 

[5] Ninghui Li, Wahbeh H. Qardaji, and Dong Su. Provably private data anonymization: Or, k-anonymity meets di erential privacy. abs/1101.2604, 01 2011. 

[6]  Sun Mingshen and Wei Tao. 大数据时代下的隐私保护. August 2017. 

[7]  Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sen- sitivity and sampling in private data analysis. In Proceedings of the Thirty-ninth Annual 

ACM Symposium on Theory of Computing, STOC ’07, pages 75–84, New York, NY, USA, 2007. ACM


[8] Kobbi Nissim, Thomas Steinke, Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, David O’Brien, and Salil Vadhan. Di erential privacy: A primer for a non-technical audi- ence (preliminary version), 2017. 

[9] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and XiaoFeng Wang. Privacy loss in apple’s implementation of di erential privacy on macos 10.12. CoRR, abs/1709.02753, 2017.

[10] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Lo- cally di erentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17), pages 729–745, Vancouver, BC, 2017. USENIX Association. 

[11] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Ran- domized aggregatable privacy-preserving ordinal response. In Proceed- ings of the 21st ACM Conference on Computer and Communications Security, Scottsdale, Arizona, 2014.