随着数据驱动的人工智能等技术的飞速发展，用户数据收集的需求越来越迫切.但随着隐私泄露事件的频发，用户隐私保障逐步成为各企业数据收集的“壁垒”[1-2].具体而言，近几年典型的隐私泄露事件包括Uber账户数据泄露事件、Facebook剑桥分析事件，造成了千万级的用户数据外泄或滥用[3].为严防此类事件的频发，各国政府都颁布了相关法令以对用户隐私数据进行法律意义上的保护.典型的，2016年4月，欧盟通过了《通用数据保护条例》(General Data Protection Regulation, GDPR)[4]，明确规定用户在数据上的查阅权、被遗忘权等权利；2019年5月，中国国家互联网信息办公室发布了《数据安全管理办法(征求意见稿)》[5]，以保障用户个人信息和重要数据在网络空间中的安全，并从数据收集、处理使用、安全监管3个方面讨论其办法.然而，数据的特殊性质决定用户的隐私问题不能仅通过法律法规界定其归属解决[6]，企业也不能因此放弃对用户敏感数据的收集，发展在大数据收集场景下兼顾数据隐私性与可用性的隐私保护技术势在必行.

隐私保护技术经过近20年的发展，已经有了诸多较为成熟的方法与体系[7]，典型的包括匿名化技术[8-11]、差分隐私技术[12-13]、密码学技术等.在大数据场景下，当前主流的隐私保护技术是差分隐私技术，更具体的指本地化差分隐私技术(local differential privacy, LDP)[14]，谷歌[15]、微软[16]和苹果[17]等企业都借助该技术完成特定的用户行为信息统计.差分隐私类方法本质上都是在保证数据整体分布不变的情况下对数据进行扰动，本地化差分隐私技术的优势主要体现在对隐私的严格定义和对数据收集场景的适用性上.具体地，在隐私定义上，它保证了任意一条用户数据的增、删、改都对用户发布数据的统计分布几乎无影响，可从根本上抵御匿名化方法难以应对的背景知识攻击；在场景适用性上，它直接在用户本地端对数据进行扰动，并只对外发布扰动数据以保护隐私，无需依赖任何第三方.但该方法也存在着致命的缺点，即在本地端添加过多噪声，使得数据的可用性较差.使用该方法，企业要么承受该数据误差，要么为提高数据可用性提高隐私损失ε，从而使得用户数据的隐私度降低.

从理想的角度出发，是否存在一种隐私保护方法在不对数据扰动的情况下保护隐私，使得数据的隐私性与可用性两者兼得?2017年谷歌的Bittau等人[18]提出ESA(encode-shuffle-analyze)框架，向该理想状态跨出有力的一步.该框架主要由编码器(encoder)、混洗器(shuffler)和分析器(analyzer)3部分组成：编码器运行在客户端，对用户数据进行本地化的编码、分割、扰动等处理；混洗器运行在一个半诚信的第三方，它可借助现有的安全混洗协议[19-25]在对数据一无所知的情况下完成安全的混洗操作；分析器运行在真正的数据收集者端，对收集的数据进行校正与分析.该框架中，混洗器完成了对用户数据完全匿名的操作，使得用户可以在尽可能对数据本身进行较小扰动的情况，获得较多的隐私保护.

ESA框架对数据可用性的提高是十分显著的.借用差分隐私技术来实现该框架，可以获得比本地化差分隐私方法小倍的数据误差[26].举例来看，假设存在10万用户，每个用户拥有一个整数xi∈[1,100]，用户分别基于ESA框架和本地化差分隐私方法在本地对数据进行扰动，数据收集者基于扰动数据进行频数估计.为方便比较，假设这2种方法都基于k值随机响应[27]实现，且对数据收集者而言发布数据都满足隐私损失ε=0.5的差分隐私.用户使用本地化差分隐私方法时，需要在本地进行隐私预算ε=0.5的数据扰动，扰动后的数据24.49%为真实值，其他均为随机噪声；而用户使用ESA框架时，混洗器的隐私放大作用使得用户仅需在本地进行隐私预算ε=10.5的数据扰动，扰动后的数据99.84%为真实值，其余为随机噪声.这一简明对比说明了ESA框架尽可能保留了原始的真实数据，从而在提供相同隐私保证的情况下提高了数据的可用性.

更具体地，图1对该例子中数据收集者获得频数估计的分布进行展示，基于ESA框架扰动后的结果更接近于原始数据，而本地化差分隐私方法扰动后的结果则与真实结果相距甚远.值得说明的是，基于ESA框架扰动后的结果与中心化差分隐私方法(central differential privacy, CDP)在该案例下获得的结果近似，但该中心化差分隐私方法假设数据收集者可信(或存在一个可信第三方)，是在对用户真实数据的计算结果(即直方图)上直接添加1次Laplace噪声得到的，而基于ESA框架的方法上需在用户本地添加总共n次噪声.

鉴于差分隐私在数学上优雅且严格的隐私定义，当前对ESA框架的研究通常与差分隐私进行结合，使得最终的收集者获得的数据满足差分隐私的定义，该类方法又称混洗差分隐私(shuffle differential privacy, SDP)[28].混洗差分隐私摒弃了中心化差分隐私下对可信第三方的依赖，即无需任何可信第三方对用户的原始数据进行统一的扰动处理，提高了隐私性；弥补了中心化差分隐私与本地化差分隐私在可用性上约的间隙[29-30]，在差分隐私的保证下实现了数据隐私度与可用性之间的更好平衡.混洗差分隐私作为ESA框架下的主流隐私保护方法，是本文研究的主要对象.

当前对ESA框架的研究仍处于起步阶段，以混洗差分隐私为主要方法，主要集中在2个方面：1)对其隐私增强效果的理论证明，即隐私放大(privacy amplification)理论；2)基于该模型提出不同统计估计方法.就混洗差分隐私而言，隐私放大理论是指用户在本地通过本地化差分隐私的方法对数据进行扰动，使得扰动后的数据经混洗实现接近于中心化方法所获得的数据统计结果.在不同统计估计方法实现时，可基于现有的差分隐私技术[31-32]进行设计，为了进一步提高准确性，也可借助密码学中Split-Mix方法[33]进行构建.

本文对该新型的隐私保护框架进行综述，主要贡献有4个方面：

1) 本文对ESA框架的实现机理与隐私保护程度进行详尽的分析，并以混洗差分隐私为例与其他差分隐私模型进行对比，以说明该框架的优势(第1节)；

2) 本文对ESA框架实现的主要方法——混洗差分隐私进行分析总结，包括该方法设计与实现的基础理论与技术(第2，3节)，以及该方法下具体的隐私保护机制(第4，5节).具体地，本文按研究问题分类，对混洗差分隐私的计数估计、频数估计、求和估计及其他的简单统计问题进行了对比分析.

3) 本文通过实验对混洗差分隐私下不同统计问题的隐私保护机制进行对比.当前绝大多数工作都是理论研究，本文通过实验对比，可以更直观地说明不同理论机制在实际应用时的效用和效率差异.

4) 基于对混洗差分隐私的理论与实验分析，本文提出ESA框架应用与发展的挑战问题，对本文进行总结.其中，考虑到混洗差分隐私在应用上固有的局限性、在方法设计中的明显不足，本文对ESA框架下的非差分隐私方法进行展望(第6，7节).

1 ESA隐私保护框架

首先，本节对ESA的隐私保护框架进行介绍，阐述编码器、混洗器和分析器各自的机理、作用和实现方式；并对不同攻击模式下该框架的隐私保护程度进行分析，定义该框架在最优情况下和最坏情况下分别可获取的隐私保护度和

之后，以当前主流的混洗差分隐私框架(即ESA框架与差分隐私的结合)为主要案例，在实现同样隐私目标的情况下，与传统的隐私保护框架对比，包括中心化差分隐私框架、本地化差分隐私框架及基于密码学的差分隐私框架.最终通过对比说明，ESA框架不仅有利于隐私保护中数据高隐私度与高可用性的实现，对当前各企业已部署的本地化差分隐私框架也极具适应性.

1.1 ESA框架定义

ESA框架如图2所示，主要由编码器、混洗器和分析器构成，并假设这三方是不可合谋的.

① 半诚信参与方(semi-honest party)[36]，又称诚实且好奇的参与方(honest-but-curious party)，是源于密码学中的一个安全假设，假设该参与方会正确遵循协议的执行，但对计算的中间结果保持好奇，并依此进行推理攻击(inference attack).

1) 编码器.主要运行在用户的本地客户端，通常被认为是可信的.它的作用是对用户数据进行编码，以完成对用户数据的发布范围、粒度、扰动程度以及随机化程度的控制，在不依赖任何信任假设的情况下保护用户数据隐私[15].

编码器可根据其输出消息的多寡分为单消息模式和多消息模式[34-35].单消息模式指用户将数据编码为1条消息，形式上可以是1个数值、1个二元组或1个数组，每个消息都是后续处理的最小单元；多消息模式指用户将数据编码为多条可分别处理的消息，如多个数值、二元组和数组等.对于同一输入，通常情况下多消息模式可携带更多信息，有助于分析器获取更准确的分析结果.

编码器的具体实现，可通过数据泛化、数据分割、加密、添加差分隐私噪声的方式实现，以达到消除或减少数据所蕴含的隐私信息的目的[18].

2) 混洗器.是独立的半诚信(semi-honest)①服务器，可在对数据内容一无所知的情况下执行安全的混洗操作，是ESA框架的核心组件.它的作用是接收用户编码后的数据，消除相应的元数据(包括接收时间、顺序、IP地址等)，并对接收数据进行混洗(即打乱顺序)，以达到匿名目的.为保证足够的隐私保护效果，该混洗器需等待一段时间收集足够的用户数据进行混洗，并对数据量满足一定阈值的数据进行发布.当数据量为敏感信息时，可对该阈值添加满足差分隐私的噪声进行扰动，或者随机丢掉一些数据使数据量满足差分隐私[18]，从而保护数据量隐私.

在混洗器的模式上，可分为单混洗器模式和多混洗器模式[34-35].单混洗器模式是将所有编码器输出的数据一起混洗，即从逻辑上使用1个混洗器进行混洗；多混洗器模式是将编码器输出的数据按属性或其他特征进行分类，从逻辑上使用多个混洗器对每个分类内的数据分别进行混洗.多混洗器模式通常用于属性或分类特征不敏感的情况下，与多消息模式的编码器相结合.但多混洗器模式并不与编码器中的多消息模式对应，多消息的消息也可以使用单混洗模式的混洗器.单混洗模式将所有数据混淆，具有更高的隐私性；但对多消息的分类特征不敏感的情况，使用多混洗模式会获得更高的数据可用性.

混洗器的具体实现可根据该模型部署的条件借助已有的安全混洗协议[18-24]，基于可信硬件[25]、同态加密[36-38]或安全多方计算[39]等方式完成.特别地，单混洗模式和多混洗模式并不与混洗器具体实现的数量一一对应，这2个混洗模式是从隐私的逻辑层面进行定义的.多混洗模式可使用1个混洗器实现，即为每个分类添加标签，对属于不同标签的数据分别进行混洗；这2个混洗模式都可基于现有的安全协议使用多个混洗器实现，以避免单点失败.

3) 分析器.由数据收集者运行，是不可信服务器.它的作用是接收混洗器发布的数据，依据相应的编码和混洗规则对数据进行分析与校正，并获取最终的统计结果.该框架中数据的隐私性主要是针对分析器而言的，即将分析器视为数据的窥探者.

本文综述的重点在于如何设计编码器和分析器，选择恰当的混洗模式来进行满足一定隐私保证的统计计算.本文将混洗器作为黑盒来使用，假设其可以完成安全的混洗操作，主要原因是安全混洗协议已经发展成熟，在诸多安全相关的文献中已有过总结和论述[18-24]；同时安全混洗协议的不同实现并不会对该框架下隐私保护方法的隐私性和可用性造成明显影响.

1.2 ESA隐私分析

ESA框架假设编码器、混洗器和分析器互不串通，但一旦其中两者合谋，该模型的最终获得的隐私效果就会大打折扣.此处假设分析器作为攻击者，该模型获得的隐私保护程度在三者无合谋时为分析器与混洗器合谋时为分析器与编码器合谋时为则这3种隐私保护效果的关系应为具体分析如下：

当分析器与混洗器合谋时，用户数据仅可获得编码器所带来的保护，即特别地，当该框架下隐私保护的最终目标是实现差分隐私，编码器使用本地化差分隐私方法进行编码时，用户可获得相对较弱的差分隐私保护.

当分析器与编码器合谋时，参与合谋的编码器数量的不同，会获得不同效果的当只有部分编码器参与合谋时，混洗的效果会减弱，但依旧会得到大于小于的隐私保护效果.极端情况下，除被攻击对象外的编码器都参与合谋，此时混洗器失效，该用户仅可获得程度的隐私保护效果.

由此，和分别作为不同攻击模式下隐私保护程度的上界与下界，在后述基于ESA框架的隐私保护方法对比时，探讨和分别对应的隐私保证十分关键.为方便表述，本文将称为中心端隐私，将称为本地端隐私.

1.3 应用实例：混洗差分隐私方法

通常情况下，研究者们将ESA框架与隐私定义严格的差分隐私进行结合，即保证分析器所获得的最终输出满足差分隐私定义，以此来对数据隐私进行保证与度量.该结合被称为混洗差分隐私，如图3(b)所示，是本文所探讨的核心方法.

对发展历史已久的差分隐私方法而言，现存在着中心化差分隐私、本地化差分隐私、基于加密的差分隐私等多种基于不同隐私保护框架实现的差分隐私方法.本节将混洗差分隐私与其他差分隐私方法进行对比，以说明ESA框架在数据隐私性、数据可用性和框架易用性上的显著优势.

1.3.1 与中心化、本地化差分隐私对比

混洗差分隐私方法与本地化差分隐私方法具有高度的相似性，它们可使用相同的编码器，实现用户本地数据的差分隐私.混洗差分隐私方法可视为在本地差分隐私框架上增加混洗器得到的，该混洗器依赖于半诚信的安全假设，相比于无任何可信依赖的本地化差分隐私框架，其可信假设更强.但混洗器所完成的匿名操作，可有效实现隐私增强的效果，意味着在保证同样ε-差分隐私保护的前提下，混洗差分隐私框架可通过编码器添加较小的噪声来提高最终数据的可用性.

中心化差分隐私使用集中式隐私保护框架，将分析器和编码器集成在一起，放置于一个可信的第三方，该第三方可视为数据收集者.该方法中，数据收集者收集用户原始数据，在该数据上进行分析，之后发布添加差分隐私噪声的分析结果.混洗差分隐私方法与之相比，虽在用户数据上添加了较多噪声损失了一定数据的可用性，但摆脱了对可信服务器的强依赖.

总体而言，在模型对可信第三方的依赖程度上，本地化差分隐私<混洗差分隐私<中心化差分隐私，即本地化差分隐私拥有最小的可信假设；以同一ε-差分隐私为目的，在分析结果的可用性上，中心化差分隐私>混洗差分隐私>本地化差分隐私，即中心化差分隐私拥有最高的结果可用性.由此可发现，混洗差分隐私方法在隐私与可用性上，均介于本地化与中心化差分隐私两者之间，实现了更好的平衡.

1.3.2 与基于加密的差分隐私对比

仅从数据可用性的角度出发，基于加密的差分隐私也可在无需可信第三方支持的隐私保护框架上，实现可用性与中心化方法接近的差分隐私[41]，与混洗差分隐私方法的结果相似.如图4所示，在该框架中，用户需在本地端对数据进行同态加密，将加密后的数据发送给服务器.之后，服务器借助2个不可共谋的云，在加密数据上计算查询结果并添加满足差分隐私的噪声，发布该扰动的数据.

但相比混洗差分隐私方法，该方法借助同态加密完成查询计算，会产生较高的计算代价和通信代价.同时，该框架需针对每一个查询特别设计隐私协议，而混洗差分隐私框架可通过简单的更改部署在现有的、广泛应用的本地化差分隐私框架上，具有较强的适应性.类似基于图4的加密差分隐私方法还有文献[42-43]，均具有上述不足.

综上，通过对不同框架下差分隐私方法的直观对比，说明了混洗差分隐私在隐私性、可用性和易用性上的突出优势，而这些优势均得益于ESA框架的应用与部署.后文，将对该混洗差分隐私方法进行详细的理论分析与实验对比，同时对ESA框架下其他隐私保护问题与方法的实现进行分析与展望.

2 基于ESA的隐私保护基础理论

本节以混洗差分隐私为主要方法，对ESA框架下隐私保护机制设计与实现的基础理论进行介绍.首先，本节对差分隐私的基本定义和重要性质进行回顾，之后，在ESA框架下基于差分隐私概念提出混洗差分隐私.最终，基于混洗差分隐私，本节给出ESA框架下隐私放大理论的严格定义与实验分析.该理论严格证明了混洗器对用户本地端隐私保证的增强效果，说明ESA框架可在本地添加较少噪声来实现较强的隐私保护效果，从而提高数据可用性.

2.1 差分隐私

定义1. (ε,δ)-差分隐私[44].给定2个相邻数据集除第i项外其余项都相等.给定一个随机化算法若对于所有的式(1)成立，则算法M满足(ε,δ)-差分隐私，即(ε,δ)-DP.

Pr(M(D)∈S)≤eεPr(M(D′)∈S)+δ.

(1)

该定义为差分隐私的一般定义，也可将其视作中心化差分隐私的定义.相应地，本地化差分隐私考虑分布式数据集，即每个用户拥有1个数据，且数据收集者可将收集的数据和用户相关联.为保证数据收集者所收集的数据满足差分隐私，需保证每个用户的输出均满足差分隐私，因此得到如下本地化差分隐私的定义：

定义2. (ε,δ)-本地化差分隐私[14].给定独立运行在用户端的随机化算法若对于所有的式(2)成立，则算法M满足(ε,δ)-本地化差分隐私，即(ε,δ)-LDP.

Pr(M(x)∈S)≤eεPr(M(x′)∈S)+δ.

(2)

在定义1和定义2中，当δ=0时，可得到纯差分隐私(pure differential privacy)的定义，可分别标记为ε-DP和ε-LDP；否则称为近似差分隐私(approximate differential privacy).ε被称为隐私代价或隐私预算，该值越小，说明相邻数据集或不同用户输入产生同一结果的概率越相近，该算法的隐私保护程度越高.δ表示相邻数据集输出结果存在概率δ使其不满足纯差分隐私，该值越小，该算法的隐私保护程度越高.

中心化与本地化的差分隐私均具有序列组合性(sequential composition)、并行组合性(parallel composition)和后处理性(post-processing)这样3条重要性质.差分隐私的组合性可帮助协议设计者进行隐私预算ε的分割，后处理性质对定义在ESA框架上的差分隐私十分关键.

性质1. 序列组合性[45].给定数据集D和m个随机化算法{M1,M2,…,Mm}，算法Mi，1≤i≤m满足εi-DP，则这m个Mi(D)算法构成的序列满足∑εi-DP.

性质2. 并行组合性[45].给定数据集D={D1∪D2∪…∪Dm}，其中Di，1≤i≤m和Dj，1≤j≤m且i≠j为互不相交的数据集，设Mi满足εi-DP的算法，则这m个Mi(Di)算法构成的序列满足max{εi}-DP.

性质3. 后处理性[46].给定满足(ε,δ)-DP的随机化算法M，令f为任意的随机化函数，则f∘M依旧满足(ε,δ)-DP.

序列组合性说明隐私预算ε可以在算法设计的不同步骤进行分配；并行组合性则定义了算法在不相交数据集上的隐私保证；后处理性则强调，在满足ε-DP的数据结果上进行随机操作，其输出依旧满足ε-DP.这3条性质适用于本地化差分隐私时，数据集D相应地定义在用户本地的数据集上.

2.2 混洗差分隐私

基于定义1～2与性质1～3，结合ESA框架，本节给出混洗差分隐私的定义.简单而言，混洗差分隐私要求对分析器来说，其收集的数据满足定义1中差分隐私的要求.同时，差分隐私的后处理性说明，只要ESA框架中的随机化编码器R和混洗器S处理过后的数据满足差分隐私，最终结果即满足差分隐私.该结果的隐私效果与分析器无关，分析器的重要作用是对扰动数据进行计算，对估计结果进行校正.

定义3. 混洗差分隐私[47].给定n个可信用户，每个用户对应1条记录xi.令R:X→Ym表示随机化的编码器，其中m表示编码后消息的数量；S:Ym→Π(Ym)表示混洗操作；算法A:Π(Ym)→Z为分析函数，其中Π表示乱序，则混洗差分隐私协议可表示为P=(R,S,A).根据后处理性，则协议P满足(ε,δ)-DP,当且仅当扰动后的数据S∘Rn=S(R(x1),R(x2),…,R(xn))=Π(R(x1),R(x2),…,R(xn))满足(ε,δ)-DP.

定义3假设参与计算的用户都是可信的，即都会按照协议正确地参与计算.但如果存在用户不可信、掉线或者与分析器共谋，则会大大影响混洗的效果，从而影响最终的差分隐私效果，由此，具有鲁棒性的混洗差分隐私被提出.

定义4. 具有鲁棒性的混洗差分隐私(robust shuffle differential privacy, RSDP)[48].给定N个用户和可信用户比例γ∈(0,1]，如果对于所有的N∈+，γ′>γ，算法S∘Rγ′N满足(ε,δ)-DP，则混洗差分隐私协议P=(R,S,A)满足(ε,δ,γ)-RSDP.

定义4保证了，在至少有γ比例的用户正确遵循协议的情况下，混洗差分隐私协议P满足(ε,δ)-DP.特别说明，此处的鲁棒性是对隐私性的保证，而非算法可用性的保证.

2.3 隐私放大理论

隐私放大(privacy amplification)是ESA框架中混洗器对隐私效果增强的理论分析，基于该理论，可将现有的本地化差分隐私方法直接应用在ESA框架上.具体地，在混洗差分隐私框架中，假设用户在本地端通过随机编码器R扰动后的数据满足εl-LDP，经过混洗后，分析器所获取的数据满足εc-DP，从εl到εc的转变可通过隐私放大理论获取.εl对应于较大的数值，表示较低的隐私性；εc对应于较小的数值，表示较高的隐私性.针对具体的差分隐私机制，研究者们提出了不同的隐私放大定理.

2.3.1 通用隐私放大定理

与差分隐私相同，混洗差分隐私也存在交互式和非交互式2种隐私保护机制[49-50]，如图5所示.假设存在n个可信用户，每个用户拥有输入xi和相同的随机化的编码协议Ri，在交互机制中，协议Ri的输入为{R1(x1),R2(x2),…,Ri-1(xi-1),xi}，即与前i-1个编码器结果和用户的输入xi相关；而非交互机制中协议Ri仅与用户的输入xi有关，可视为交互机制的简化.

交互机制可以处理较为复杂的、用户间有关联关系的统计分析，如果一些遗传病的统计，被统计者与其亲属可能存在关联关系；而非交互机制仅可以处理用户数据独立的统计分析.相应地，基于这2种机制，研究者们提出了2个通用隐私放大定理.

定理1. 通用交互机制的隐私放大定理[26].给定n个用户，每个用户对应1条记录xi，且在本地运行随机化编码协议R.对于任意的n>1 000，δ∈(0,0.01)，如果协议R满足εl-本地化差分隐私，且εl∈(0,0.5)，则协议S∘Rn对应混洗后的n个输出满足(εc,δ)-DP，其中

(3)

定理2. 通用非交互机制的隐私放大定理[47].给定n个用户，每个用户对应1条记录xi，且在本地运行随机化编码协议R.对于任意的n∈+，δ∈[0,1]，εl∈(0,ln(n/ln(1/δ))/2]，如果协议R满足εl-LDP，则协议S∘Rn对应混洗后的n个输出满足(εc,δ)-DP，其中

(4)

根据定理1和定理2，设定δ=10-9，可得到表1和表2中隐私放大结果.令n表示参与计算的可信用户数量，表1为根据式(3)计算εl经隐私放大后得到的εc取值；表2为根据式(4)计算εc对应的被放大前的εl取值.根据表1和表2可发现，通过隐私放大，可轻易实现在用户本地端添加满足较大εl-LDP的噪声，而在分析器端获得较小的εc-DP保证.同时，隐私放大效果随着参与用户数量的增加而增大.

通过表1中的分析计算可发现，通用交互机制的隐私放大结果是不适用于现实情况的.由于该机制仅在εl∈(0,0.5)时生效，此时εc的取值往往小于0.2.现实情况中，通常并不需要如此严格的(如此小的εc)差分隐私保证，并且用户端添加过小的εl，会给统计结果造成较大误差.由此，通用非交互机制的隐私放大定理往往会有更多的应用.

2.3.2 基于随机响应的隐私放大定理

为了获取更好的隐私放大的效果，研究者们针对具体的差分隐私机制提出了更精确的隐私放大定理.被应用最多的，是基于随机响应机制提出的隐私放大定理.随机响应机制是本地化差分隐私的基本扰动技术，Warner[51]于1965年提出.为方便后续应用，本节对该机制进行一定程度的扩展，并描述如下[27,47].

假设有n个可信用户参与计算，每个用户拥有1个值xi，其对应的取值范围为{v1,v2,…,vk}.当用户对该值进行发布时，以1-λ的概率发布真实值，以λ的概率从{v1,v2,…,vk}中随机输出1个值.混洗器接收这些数据后，仅对其顺序进行打乱，而不改变值本身.令分析器收集到的每个值vj(j∈{1,2,…,k})的数量为通过式(5)，分析器可以估计每个值vj的真实数量，表示为

(5)

当k=2时，假设v1=‘Yes’，v2=‘No’，则上述机制即为经典的随机响应机制，回答“Yes/No”的问题，本文将其称为布尔随机响应机制(Boolean random response mechanism).当k≥2时，本文将其称为k值随机响应机制(k-random response mech-anism, kRR).之所以将其区分开，是由于在进行复杂差分隐私机制设计时，通常要考虑对数据01编码或直接使用该数值的问题，涉及上述2种不同方案.基于此，研究者们提出了2种相应的隐私放大定理.

定理3. 布尔随机响应机制的隐私放大定理[28].给定n个用户，每个用户对应1条记录xi∈{0,1}，且在本地运行协议R.对于任意的n∈+，δ∈[0,1]，λ∈[14 ln(4/δ)/n,1]，如果协议R以λ的概率均匀输出{0,1}中的值，1-λ的概率输出真实值，则协议S∘Rn对应混洗后的n个输出满足(εc,δ)-DP，其中

(6)

在定理3中，当λ=2/(eεl+1)时，布尔随机响应机制满足εl-LDP.将该式代入式(6)，通过简化，可得到宽松的隐私放大效果[52],即当0<εl≤ln n-ln(14 ln(4/δ))时，

(7)

定理4. k值随机响应机制的隐私放大定理[47].给定n个用户，每个用户对应1条记录xi∈{1,2,…,k}，且在本地运行协议R.对于任意的k,n∈+，λ∈[0,1]，εc∈(0,1]，如果协议R以λ的概率均匀输出{1,2,…,k}中的值，以1-λ的概率输出真实值，则当λ满足式(8)时，协议S∘Rn对应混洗后的n个输出满足(εc,δ)-DP.

(8)

在定理4中，当λ=k/(eεl+k-1)时，k值随机响应机制满足εl-LDP.将该值代入式(8)，通过简化可得到宽松的隐私放大效果[40],即当时，

(9)

与2.3.1节相同，设定δ=10-9，针对不同的可信用户数量n，表3表示根据定理3在给定n和εc的情况下，计算εl的取值情况；表4表示根据定理4，在给定n，εc，并假设k=2的情况下，计算εl的取值情况.在表3(表4)的结果中，None表示εl的取值不满足定理3(定理4)，无法进行隐私放大.

显然，在针对2个离散值进行扰动时，定理4的隐私放大效果优于定理3，由此选用定理4进行基于随机响应机制的隐私放大是更明智的选择.同时通过分析发现，随着k值的增大，定理4的隐私放大效果会缩减，但并不明显.通过实验发现，在给定n和εc的情况下，不同k值所造成隐私放大逆向计算结果εl的差异仅在小数点后几位体现.由于该计算结果较为简单，此处不予以展示.

3 基于ESA的隐私保护基础技术

本节以混洗差分隐私作为ESA实现的主要方案，对该方案构建的基础技术进行总结与介绍，为后文不同隐私保护方法的对比分析奠定基础.

这些基础技术主要分为2类：一类是差分隐私技术，包括中心化差分隐私、分布式差分隐私和本地化差分隐私中的具体隐私保护机制；另一类是基于匿名的密码学技术，具体指Split-Mix方法.差分隐私技术中，本地化差分隐私技术可与2.3节所述的隐私放大定理相结合以实现混洗差分隐私，该途径所获得的差分隐私模型较为简洁.基于匿名的密码学技术Split-Mix方法通常与中心化或分布式的差分隐私技术相结合以满足最终的差分隐私保证，在该过程中Split-Mix方法可进一步减少在原始数据中添加的噪声，使计数结果具有较高的准确性，但同时也会产生较高的通信代价.

3.1 差分隐私技术

差分隐私技术根据不同的使用场景，可分为中心化差分隐私、分布式差分隐私和本地化差分隐私3种，均可通过与ESA框架不同的结合方式实现混洗差分隐私，具体技术如下.

3.1.1 中心化差分隐私技术

中心化差分隐私技术指一般的差分隐私机制，该机制通常在统计分析结果(如直方图)上添加满足一定分布的噪声，使该扰动后的结果满足(ε,δ)-DP，以响应用户查询.为保证扰动后结果的无偏性，通常需要保证添加噪声的期望为0.常用差分隐私机制如下：

定理5. 拉普拉斯机制[46].令f:Xn→是一个敏感度为Δ的函数，即对所有的相邻数据集D,D′∈Xn，|f(D)-f(D′)|≤Δ.当ε>0时，生成噪声η～Lap(Δ/ε)，则添加噪声后的输出f(D)+η满足ε-DP.

其中，Lap(Δ/ε)表示拉普拉斯分布，它对应的概率密度函数为该机制通常为连续型数值添加噪声.

定理6. 二项分布机制[53].令f:Xn→是一个敏感度为Δ的函数，即对所有的相邻数据集D,D′∈Xn，|f(D)-f(D′)|≤Δ.当ε>0，δ∈(0,1)，λ≥20(eε/Δ+1)/(eε/Δ-1)2ln(2/δ)时，生成噪声则添加噪声后的输出f(D)+η满足(ε,δ)-DP.

其中，Bin(λ,1/2)表示二项分布，它对应的概率分布函数为该机制通常为整数数值添加噪声.

定理7. 几何分布机制[54].令f:Xn→是一个敏感度为Δ的函数，即对所有相邻数据集D,D′∈Xn，|f(D)-f(D′)|≤Δ.当ε>0时，生成噪声η～SG(ε)，添加噪声后的输出f(D)+η满足ε-DP.

其中，SG(ε)表示对称几何分布，它对应的概率分布函数为Pr(η=x)=e-ε|x|/Δ×(eε/Δ-1)/(eε/Δ+1).该分布可看作离散化的拉普拉斯分布，其期望为0.该机制通常为整数数值添加噪声.

3.1.2 分布式差分隐私技术

分布式差分隐私技术与中心化差分隐私技术不同的是，该方法不直接在统计结果上添加噪声，而在用户端的原始数据上独立添加满足一定分布的随机噪声，并使得扰动后的数据在服务器端满足差分隐私.分布式差分隐私技术通常利用拉普拉斯分布无限可分性质，在用户端独立添加满足一定分布的噪声，使得在服务器端这些噪声的和满足拉普拉斯分布[31].

定理8. 分布式几何分布机制[32,55].令n为可信用户数量,f:Xn→是一个敏感度为Δ的函数，即对所有的相邻数据集D,D′∈Xn，|f(D)-f(D′)|≤Δ，独立随机变量满足分布Pólya(1/n,e-ε/Δ)，则噪声η～SG(ε)可通过式(10)模拟：

(10)

在该机制中，用户在本地端对数据添加噪声用户发布数据的和在中心端相当于添加了噪声η，满足ε-DP.满足Pólya(r,α)分布的随机变量可使用泊松-伽马混合方案[55]生成，即首先生成满足伽马分布的随机变量t～Gamma(r,α/(1-α))，之后借助该变量生成满足泊松分布的随机变量

3.1.3 本地化差分隐私技术

本地化差分隐私技术在用户端的原始数据上添加噪声，并保证任一用户的发布数据均满足差分隐私定义.该技术中最常用的是随机响应机制，亦可基于一般的差分隐私机制(指中心化差分隐私技术)实现，但会产生较多噪声.该技术是混洗差分隐私方法设计中最常用的基础技术，它结合混洗器的隐私放大效果可达到较强的差分隐私保护效果.

具体技术中，为了在随机响应机制的基础上进一步降低通信代价和均方误差，使计算结果不依赖于用户数据的值域，基于略图的本地化差分隐私(sketch-based local differential privacy)算法[56-57]被提出，即首先使用散列函数对用户数据进行映射，对该映射后的值进行扰动.Wang等人[57]针对此类方法以均方误差为目标函数对该最小值问题进行求解，提出了OLH方法，可在值域较大的情况下，实现与值域[d]大小无关的最优误差，[d]表示{1,2,…,d}.该方法将较大的数据值域[d]通过散列函数进行压缩，映射至较小的值域[d′]，用户将其拥有的值先用该散列函数进行散列，而后进行随机扰动，即以εl/(εl+d′-1)的概率保持该值不变，以1/(εl+d′-1)的概率扰动为值域{1,2,…,d′}内的其他值.当d′=eεl+1时，可使结果对应的均方误差最小.较大值域[d]指的是d≥3eεl+2时，否则应用通用的k值随机响应算法即可获得较小的均方误差.更多本地化差分隐私方法在文献[14]中已有详细综述，本节不再赘述.

3.2 基于匿名的密码学技术

针对匿名化模型中的安全聚合问题，Ishai等人[33]曾提出Split-Mix协议.该协议将每个用户的值xi分割为m个随机数xij，使得mod q=ximod q，q为加法群q的阶.分析器收集到这mn个匿名数据后，求和即可获得结果.文献[33]证明，只要m超过阈值Θ(lb n+σ+lb q)，该协议就是σ-安全的，即相同结果对应的不同输入之间的统计距离不超过2-σ.

ESA框架中的混洗器相当于完成了彻底的匿名操作，由此可基于Split-Mix方法设计实现满足分析器端差分隐私的算法.同时，利用Split-Mix方法中类似秘密共享的操作，可进一步对用户端编码后的数据提供保护，分析器将会看到几乎完全随机的数据分片，如此可进一步减小差分隐私噪声的添加.Split-Mix方法与加法秘密共享不同的是，后者需保证不同的数据分片(即shares)由不同的参与者拥有，而该算法对数据分割获得的数据分片可由1个或多个混洗器持有，取决于混洗器的实现方式.

Ghazi等人首次提出并证明使用该算法可以在ESA框架中实现差分隐私[58]，并证明了该算法的误差上界，以及一轮协议(one-round protocol)下的误差下界[59].Balle等人[60]给出了与Split-Mix方法结合的差分隐私保证，见定理9.基于定理9，可以进一步设计出多消息模式下的混洗差分隐私机制.

定理9. 假设算法M和算法M′的统计距离(总体方差)为μ(σ)，算法M满足(ε,δ)-DP，则算法M′满足(ε,δ+(1+eε)μ(σ))-DP.

4 基于ESA的隐私保护方法对比

基于ESA的隐私保护方法以混洗差分隐私方法为主要内容，主要集中于基础的数据统计问题，包括计数估计、频数估计、求和估计以及其他统计问题，如表5所示.本节将针对不同的统计问题，对这些方法进行对比分析，包括这些方法的编码器模式、混洗器模式、算法误差、通信代价、计算代价以及中心端隐私和本地端隐私对应的隐私保证.

其中，计数估计、频数估计和求和估计是统计估计的基础问题，受到广泛关注，也是本节分析的重点.在本节的理论分析中，一般假设有n个用户参与计算，实现了分析器端(εc,δ)-DP的隐私保护效果.部分机制假设参与计算的用户不完全可信，此时使用的N表示用户数量，γ表示可信用户比例，可在分析器端实现具有鲁棒性的(ε,δ,γ)-RSDP；当γ=1时，它等同于(εc,δ)-DP.同时，在文中使用[d]表示{1,2,…,d}，[n]表示{1,2,…,n}.在不同估计机制的对比表中，通信代价指每个用户发送消息的数量，“—”表示该项隐私未得到严格的理论保证.

4.1 计数估计

计数估计问题(counting estimation)是后续所综述的绝大多数统计估计问题的基础，即每个用户拥有1个数值xi∈{0,1}，分析器端基于匿名的用户扰动数据估计拥有“1”的用户数量，即估计这些数值的和由此该问题又称布尔求和(Boolean summation)或二项求和(binary summation)问题.

针对该问题，研究者们提出了若干方法，分别实现了不同的隐私目标.Cnt_RR[28]基于隐私放大理论，可实现不同ε的中心端差分隐私和本地端差分隐私.Cnt_2M[61]，Cnt_PURE[62]，Cnt_SGM[48]，Cnt_BN[48]仅考虑中心端差分隐私，其中，Cnt_2M实现近似差分隐私，Cnt_PURE实现纯差分隐私，Cnt_SGM和Cnt_BN则进一步考虑了用户不完全可信的场景，分别实现了分析器端具有鲁棒性的纯差分隐私和近似差分隐私.具体方法对比见表6，方法分析为：

Cnt_RR[28]在ESA框架上应用基础的随机响应机制对用户拥有的xi∈{0,1}进行估计.用户以λ的概率随机输出yi∈{0,1}，以1-λ的概率输出其本身的值yi=xi.混洗器收到这些值后，将其匿名并乱序后发送给分析器,分析器利用式(5)进行无偏的计数估计，即估计拥有“1”的用户数量.文献[28]提出该方法的隐私放大定理(即定理3)，并对其误差边界进行了严格估计.依据定理3，当满足式(11)时，该方法满足(εc,δ)-DP.

(11)

Cnt_2M[61]进一步探索多消息模式下的差分隐私方法，为后续多消息模式下的其他估计问题奠定基础.该方法在用户端并不满足差分隐私，仅保证分析器端满足(εc,δ)-DP.在该方法中，用户将其拥有的xi∈{0,1}扰动为最多2个值.具体地，用户以的概率输出xi+1个1，以1-λ的概率输出xi个1,表示为集合yi.经混洗后，分析器计算当c*>n时，输出校正后的值c*-nλ，否则输出0.该方法的估计结果不是无偏的，但可保证当真实的和为0时，估计值一定为0；否则得到一个扰动的估计.

Cnt_PURE[62]与Cnt_RR和Cnt_2M方法不同的是，它实现了中心端纯差分隐私保护.该方法的核心思想是将与用户输入相关的扰动消息和与输入无关的噪声联系起来，保证相邻数据集扰动后的分布在任一点上的概率密度相差在一个很小的乘积因子的范围内.具体地，用户以概率1-λ将数据xi扰动为与输入相关的τ个消息，即当xi=0时，返回(τ-1)/2个1和(τ+1)/2个0，否则返回(τ+1)/2个1和(τ-1)/2个0；以概率λ生成满足截断离散化差分隐私DLap(τ/2,Δ/εc)的随机变量z，发布z个1和τ-z个0作为噪声数据.截断离散化差分隐私DLap基于本文在3.1节介绍的对称几何分布机制SG实现，即将对称几何分布SG的均值由0变为τ/2，对于超过[0,τ]范围的噪声截断为0或τ.至此，用户得到扰动数据y，并将这些数据经混洗后发送给分析器，分析器可依据公式对拥有1的用户数量进行估计.当3时，该方法满足εc-DP.

Cnt_SGM[48]进一步考虑了在分析器端具有鲁棒性的纯差分隐私，即满足(3εc/γ,0,γ)-RSDP.该方法通过在用户数据上直接添加满足对称几何分布SG的噪声实现，为满足对称性，首先将用户拥有的xi通过将其映射到{-1,1}.而后用户以一定的概率λ为添加对称几何分布噪声，即否则保留原值.为实现彻底的混洗，并隐藏原有的数值信息，用户将该值扰动为个发送混洗器.例如，当扰动后的时，发送时，发送-1,-1.最终分析器通过计算得到无偏的求和估计结果.据分析，当λ=min{1,2(eεc+1)/((eεc-1)2n)}时，该方法满足(3εc/γ,0,γ)-RSDP.

Cnt_BN[48]亦考虑了隐私的鲁棒性，并实现了在分析器端具有鲁棒性的近似差分隐私，即满足(εc,δ,γ)-RSDP.该方法基于泊松分布实现，即将用户值xi与si个满足伯努利分布Ber(1/2)的噪声所组成的集合作为扰动值，发送给混洗器.分析器接收这些混洗数据，并通过公式估计拥有1的用户数量，其中n1表示分析器端收到1的数量，n0表示分析器端收到0的数量.当伯努利分布的噪声数量si满足时，该方法满足(εc,δ,γ)-RSDP.

4.2 频数估计

频数估计中假设每个用户拥有1个离散型的值xi∈[d]，分析器端基于匿名的用户扰动数据估计这些数值频数count(j),j∈[d]，即估计用户数据的直方图.

针对该问题，研究者们提出了若干方法.总结来看，Hist_KR[47]方法基于随机响应机制提出，是最为简单的频数估计方法；为了进一步提高结果的可用性，即减小结果误差，Hist_MM[61]，SLH[40,63]，MURS[40]机制实现了与值域d大小无关的误差，可用于值域d较大的情况；PRHR[64]和PUCM[64]基于多消息模式进行编码，实现了相比前几种方法更小的误差.在隐私方面，绝大多数方法都考虑了和这2种模型中的隐私问题，即同时保证了用户端和分析器端的隐私；只有Hist_MM方法仅考虑了分析器端的隐私保证；而MURS进一步对混洗器与分析器共谋情况下的用户隐私进行了一定程度的保护.此外， Erlingsson等人[52]提出“属性分段”和“报告分段”的方法，可与混洗差分隐私频数估计中的任一方法结合以进一步提升它们在不同情形下的可用性与隐私性.频数估计的方法对比见表7，方法分析如下.

Hist_KR[47]在ESA框架上应用基础的随机响应机制，基于隐私放大理论，对用户拥有的xi∈[d]进行估计，是频数估计中最简单而直接的方法.如2.3.2节所描述的，用户以λ的概率随机输出以1-λ的概率输出其本身的值混洗器收到这些值后，将其匿名并乱序后发送给分析器,分析器利用式对每一个值j∈[d]的频数进行无偏估计.Balle等人在文献[47]中将这λn个随机值称为“隐私毯子”(privacy blanket)，任意用户值在被混洗后均获得了“隐私毯子”带来的增强隐私效果.基于该思想，作者对该方法的隐私保证和误差进行了严格且优雅的证明，当λ根据式(8)进行取值时，可获得分析器端(εc,δ)-DP的隐私保护，本地端获得εl-LDP的隐私保护，其中:

为了在值域[d]较大时进一步减少频数估计的误差，研究者们相继提出了若干频数估计方案，可实现与值域[d]无关的误差边界.

Hist_MM[61]方法基于计数机制Cnt_2M构建，仅考虑分析器端的差分隐私，不考虑用户端的差分隐私，由此无需根据值域[d]对用户端的隐私预算进行划分，分析器也可计算得到与[d]无关的误差边界.在该方法中，每个用户将其拥有的数据进行独热(one-hot)编码，即生成1个d长的向量，第xi位为1，其余位为0.之后对每一位{0,1}分别使用满足(εc/2,δ/2)-DP的Cnt_2M中的扰动机制进行扰动，得到yij={1}*.为了使得分析器能够在彻底的混洗后依然识别yij对应于哪一个离散值，用户将j×yij发送给混洗器进行扰动.最终分析器分别统计每一个值j∈[d]的计数，使用Cnt_2M中的校正机制进行校正，计算其频数.该机制的优点在于它的误差边界并不依赖于值域[d],但该机制所获得的估计结果是有偏的，且仅考虑了分析器作为攻击者时的隐私保护，不能保证对任意攻击者的用户端隐私.

Wang等人[57]基于优化的本地化差分隐私方法OLH，结合隐私放大理论提出了SLH机制[40,63].该机制考虑在值域较大的情况下，实现与值域d大小无关的最优误差，且兼顾了分析器端和本地端的隐私与具体地，用户在本地端用OLH方法对其拥有的数据xi进行扰动，在分析器端使用公式对每个j∈[d]的频数进行估计，其中d′=eεl/2+1，p′=eεl/2/(eεl/2+1)，为扰动数据中j的频数.根据定理4，可求得εc=时，SLH机制在分析器端满足(εc,δ)-DP.但该方法存在的问题是，当应用OLH方法对用户数据进行扰动时，为了尽可能避免散列函数冲突，每个用户使用1个单独的散列函数Hi，分析器在统计频数时需计算每一个值j∈[d]对应的散列值Hi(j)，共需计算nd个散列值并进行n2次比较，相比其他方法具有明显增加的计算代价.

SLH机制使用1个混洗器进行混洗，一旦该混洗器与分析器串通，用户的隐私将不能得到保证.为了解决该问题，Wang等人[40]在SLH方法的基础上进一步提出了一个通用协议MURS(multi uniform random shufflers)，使用m个混洗器对用户数据进行混洗，每个混洗器在混洗的过程中都随机添加一些均匀分布的假数据.此处的多个混洗器完成的是几乎相同的工作，仍对应于1.1节中介绍的单混洗器模式，只是使用多个服务器来实现该模式.这样一来，即使有m-1个混洗器和除被攻击用户外其余n-1个用户都与分析器合谋，用户数据至少能得到由1个混洗器所添加的假数据构成的“隐私毯子”带来的保护.

MURS[40]方法中混洗器添加的均匀分布的假数据数量用nr表示，分析器使用SLH中的方法计算后，需要通过对该值进行较正，将混洗器添加的假数据减掉.相应地，根据定理4，可计算得到:

分析器端满足(εc,δ)-DP.

上述方法的误差均在多项式级别，Ghazi等人在文献[64]中证明，对于编码器单消息模式下的频数估计机制，其最优的渐近误差为为进一步得到对数多项式的更小误差，Ghazi等人[64]基于多消息模式的编码器提出了2种频数估计方法.PRHR和PUCM这2种方法充分借鉴并扩展了Balle等人[47]“隐私毯子”的思想.在单消息模式中，用户以一定概率在真实值和构成“隐私毯子”的随机数中选择一项输出；在多消息模式中，用户可将这2项都保留，以此提高结果的准确性.用户可以通过方法中具体的参数设置使得“隐私毯子”发挥足够作用，以满足分析器端(εc,δ)-DP差分隐私.这2种方法涉及2种随机性：一种是private-coin，即随机性的资源是被用户独立拥有的；另一种是public-coin，即用户端产生随机数的算法可与分析器共享.这2种随机性的应用仅会影响方法可用性，而对方法的隐私度无任何影响.

PRHR(private-coin-based Hadamard response)方法采用private-coin机制，将本地化差分隐私技术Hadamard Response扩展为多消息模式的混洗差分隐私方法.该方法应用的Hadamard矩阵是1个正交方阵，具备2个重要性质：1)除第1行外每行1的个数为B/2；2)任2行对应的向量正交，且有B/2个位置对应的元素相同.基于Hadamard矩阵H，用户将其拥有的数据xi进行扰动为多消息模式对应的输出集合Ti.Ti中包含1+ρ个元组，可分为2个部分：一部分是真实值对应的元组，即从H的第xi+1行数值1对应的索引中均匀采样τ个，标记为ai1=(a11,a12,…,a1τ)；另一部分是ρ个随机元组构成的“隐私毯子”，该元组中每个随机数都是从[B]中均匀采样的τ个值air=(ar1,ar2,…,arτ)，r∈{2,3,…,ρ+1}，[B]={1,2,…,B}.用户将自己生成的Ti发送给混洗器进行混洗，混洗时每个元组air,r∈{1,2,…,ρ+1}都作为1个独立的单元.分析器收到混洗后的数据，针对每一个值j∈[B]计算，有多少个air属于矩阵H第j+1行1对应的索引值，并将该计数结果标记为最终，通过公式分析器可计算得到无偏的频数估计结果.令εc≤1，τ=lb n，ρ=(36 ln(1/δ))/，该方法可获得分析器端(εc,δeεc/εc)-DP的隐私保护.该方法优点在于误差较小，但缺点在于分析器端进行计算时需将扰动数据与H中的每一行一一比较匹配，具有较高的计算代价

PUCM(public-coin-based Count Min)方法借助于public-coin机制，结合多消息模式下的随机响应机制与Count-Min数据结构，进一步实现了对数多项式误差的混洗差分隐私方法，同时可将分析器端查询响应的计算代价降至但美中不足的是该方法的估计结果不具备无偏性，Count-Min使得该方法频数估计的结果略微偏大，具有单边误差(one-sided error).具体地，该方法假设存在一个用户和分析器都知晓的随机散列簇{ht:[d]→[s],∀t∈[τ]}，用户基于该散列簇将数据xi扰动为多消息模式对应的集合Ti.与PRHR类似，Ti中一部分为真实结果的编码，即将xi通过散列函数映射为τ个值，得到τ个元组(t,ht(xi))；另一部分为随机数，即针对每个t∈[τ]，l∈[s]，以λ的概率将(t,l)添加至集合Ti中.用户将集合Ti发给混洗器进行混洗，分析器收集到这些匿名数据后，计算每一个C[t,l]的值，其中C表示Count-Min数据结构.之后，分析器根据公式估计每个值j∈[d]的频数.令s=2n，λ≥90τ2ln(2τ/δ)/n，则该方法满足(εc,δ)-DP.

至此，上述分析的所有方法均针对单值频数估计，对于多值频数估计(即用户拥有多个值的情况)，通常情况下，可通过对隐私预算εc进行分割，或从多值中随机采样1个值进行扰动，文献[65-66]证明后者的误差更小.而针对ESA模型下的多值频数估计，Erlingsson等人[52]提出了“属性分段”(attribute fragmenting)的通用方法.对于一些独立的自然属性，如统计人群的年龄、性别等，可将不同的属性作为单独的分段分别扰动，每个属性使用1个单独的混洗器进行混洗，以提高数据可用性；对于非自然属性，可人为将其拆分为多个分段，应用该属性分段技术.该属性分段的应用特例是，对于用户拥有的数值xi可进行独热编码，而后使用Cnt_RR方法对每一比特位的数据分别进行扰动与混洗.

对于基于混洗的隐私放大理论设计的方法，仍存在1个实际问题，即用户端的隐私保证εl通常较大.事实上，当εl=10时，99.996%的扰动后数据为原数据.为了切实地保护用户直接发布数据的隐私，Erlingsson等人[52]提出了“报告分段”(report fragmenting)的通用方法.该方法的核心思想与Rappor类似，即使用εlb作为隐私后盾，用εlb对用户拥有的数据xi做1次永久性的扰动得到之后使用较小的εlf作为临时性的隐私保证，用户可多次发布在上用εlf扰动的数据.由此，用户可发布ω个先后基于εlb和εlf扰动的数据，用户端对应的隐私保证为上述方案基于混洗的隐私放大理论构建的方法均可借助该方法对用户端的隐私进一步加强.

4.3 求和估计

求和估计主要针对实数完成，即假设每个用户拥有1个数值xi∈[0,1]，分析器端基于匿名的用户扰动数据估计这些数值的和

研究者们基于上述针对离散值的扰动方法(包括计数估计方法和频数估计方法)，提出了若干实数求和估计机制，如RSum_RR，RSum_KR，RSum_RM，RSum_DSG，RSum_PURE，其中RSum_PURE实现了纯差分隐私，其余均实现了近似差分隐私.每一个方法的提出，都相比前一个方法降低了统计结果的误差边界；但兼顾结果可用性和方法通信代价，RSum_RM应是当前可行性较高的估计方法.

在具体实现时，为了应用上述对离散值扰动的方法，首先需要将该实数根据一定规则编码为若干整数.通常情况下，研究者们会依据一定的准确度p将实数值xi其放大p倍得到pxi，而后将其无偏映射为离散型的整数，该过程称为随机舍入(random rounding).最终，在若干离散型数据上，基于布尔求和或频数估计方法进行计算.通常随机舍入算法需保证无偏，以保证最终结果的可用性.求和估计的方法对比见表8，具体方案如下所述.

RSum_RR[28]在ESA框架上基于随机响应机制对用户拥有的xi∈[0,1]进行估计，具体基于Cnt_RR方法构建.其核心思想是将用户值xi通过随机舍入算法无偏映射为bi=(bi1,bi2,…,bip)∈{0,1}p，该向量中1的数量代表pxi.具体地，bi中有xip+Ber(xip-xip)个值为1，其余为0，Ber表示伯努利分布.举个例子，当用户值xi=0.732，p=10时，用户进行随机舍入，以0.32的概率舍入为8个1和2个0，以0.68的概率舍入为7个1和3个0.之后，编码器在每个bij上分别使用Cnt_RR进行扰动，i∈[n]，j∈[p].此时需要对隐私预算εc进行隐私分割，为提高结果的准确性，可使用高级组合定理[46]，使每一个bij扰动后满足最终分析器收集这些扰动结果后，使用式(5)计算得到的无偏估计，对该结果除以p即为的无偏估计.经证明，该方法的准确度时，可满足表6中所列出的渐近误差边界.

RSum_KR[47]基于随机响应机制下的直方图统计方法实现，避免了对隐私预算εc进行分割，从而相比RSum_RR提高了准确性.其核心思想是将用户值xi∈[0,1]放大p倍，得到之后通过随机舍入方法进行的无偏映射，即以的概率将映射为否则映射为

之后便可借助Hist_KR方法对进行扰动，分析器通过计算即可基于混洗后的数据计算每一个的无偏估计值.该方法中使用的Hist_KR方法相比Cnt_RR方法，由于值域的变大，在相同的ε下会引入较大的噪声，但总体而言，由于无需对总体的隐私预算εc进行分割，且得益于定理4中更为优良的隐私放大效果，RSum_KR的估计结果相比RSum_RR误差更小，可用性更高.

实数求和估计结果的准确性一方面依赖于隐私预算εc的分配与方法的隐私放大效果；另一方面也与随机舍入的结果的准确性有关.进一步地，RSum_RM[35]方法将用户拥有的xi∈[0,1]随机舍入为多个更为准确的值，以提高方法的可用性.

RSum_RM[35]方法的核心思想是，通过将用户拥有的数值xi∈[0,1]依据m个固定的准确度编码为多个值，并对编码后的值分别独立地应用随机响应方法，从而尽可能利用混洗器提供的隐私保护.具体地，给定一系列准确度p1,p2,…,pm∈+，令则

其中

sij=pj(qj-1 xi-qj-1-xi)=qjxi-pjqj-1xi.

也就是说，给定m个准确度，xi可编码为m个整数si.举个例子，设xi=0.23456，令p1=10，p2=100，则xi可编码为si=(2,34).为保证xi到si的无偏映射，对sij，j∈{1,2,…m}进行随机舍入，即sij=sij+Ber(qjxi-pjqj-1xi).用户将这些si分别发送至m个独立的混洗器进行混洗，分析器收集数据后依据方法Hist_KR对每一个进行估计.此处，si1至si(m-1)的值域应为pj-1，而sim的值域为pm.由于使用了m个独立的混洗器和扰动方法，此时中心化的隐私预算εc不再是0≤εc≤1，而是0≤εc≤m.而对m个值进行扰动时，需对每一个sij扰动的隐私预算εc和参数δ进行分割，即使用εc/m和δ/m进行扰动.在对均方误差MSE进行估计时，m个准确度会使随机舍入带来的误差降低倍，而εc的分割会使扰动带来的误差增加约O(m2)倍，当pj=n3j-m-1时，可得到最优的均方误差Oδ(n3-m(1+m3/)).进一步地，当m=log3(lb n)，pj=23j时，可得到最优的均方误差Oδ((ln(ln n))3/).

上述方法的误差均与可信用户数量n有关，Balle等人[35,60]进一步基于Split-Mix方法提出了误差与n无关的实数估计方法RSum_DSG.该方法的随机舍入过程与RSum_KR方法类似，即根据精确度p将该值随机映射为整数其核心思想是对舍入后的整数添加满足对称几何分布SG(e-εc/p)的噪声，并对该加噪后对数据用Split-Mix方法进行安全的聚合运算.令Split-Mix方法中加法群q的阶为q，则每个数据被分割为m个秘密，即在分析器对估计值进行矫正时，对于的情况，计算z=z-q，以解决z在q中上溢或下溢的问题.最终计算z/p得到实数和的估计值.经证明，当混洗器选用多混洗器模式时，可获得与n无关的均方误差边界O(1/εc).

虽然RSum_DSG方法从理论上获得了与n无关的均方误差MSE，但该方法的通信代价过大.通常情况下，选择方法RSum_RM更具实用性，用户可根据其带宽选择多消息模式编码器中消息的数量m，当m=2或3时，即可取得可用性相对较好的结果.

至此，上述方法都讨论了近似差分隐私方法下的求和估计.Ghazi等人[62]提出的RSum_PURE是一种纯差分隐私下的求和估计方法.该方法使用了一种更自然、通信代价更低、误差更小的用户端的编码方式，即将用户所拥有的实数使用二进制进行编码，将xi编码为p位二进制数.之后，即可利用Cnt_PURE方法对每一位01的数量进行扰动与估计，结果用表示.基于二进制的编码方式，令表示用户求和的估计值，则当p=2 lb n时，该方法满足εc-DP.

4.4 其他统计问题

除了基本的计数估计和频数估计，研究者们还关注了其他相对复杂的统计和查询问题，包括不同元素计数(distinct elements counting)、范围计数和均匀性检验，具体可见表7.本节对这些方法进行理论分析与总结，由于这些方法均使用了多消息模式和单洗牌器模式，不再将这2项罗列在对比的表格当中.

4.4.1 不同元素计数

给定数据的值域[d]，每个用户拥有1个xi∈[d], 该问题统计n个用户拥有的不同值的数量，即f(x)=|{j∈[d]|∃i where xi=j}|.文献[48]将该问题转化相当于对用户拥有的{0,1}值求“或”的问题.而这n个值的“或”可用(Ix1=j+Ix2=j…+Ixn=j)mod 2来估计，I为示性函数.即当该值有偶数个用户拥有时，该函数输出为0；否则，输出为1.

据此，文献[48]提出了DisEle方法，在该方法中，用户首先将其拥有的值xi用独热编码表示，之后对编码后的每一位xij进行扰动.当xij=1时，将该值扰动为yij=Ber(1/2)；当xij=0时，将该值扰动为yij=Ber((1-(1-e-εc)1/n)/2).对于上述讨论的OR操作，如此扰动相当于对OR(x)=1扰动为Ber(1/2)，对OR(x)=0扰动为Ber(1/2eεc).用户将这些扰动后的yij用Split-Mix方法分割为m个值连同其对应的标签j∈[d]一起发送给混洗器，以便分析器对不同的元素j进行统计.最终分析器通过来计算用户所拥有的不同元素的计数.

假设可信用户比例为γ，则DisEle方法满足(2ε(γ),4δ/γ,γ)-RSDP，其中，当εc≤ln 2时，否则ε(γ)=εc+ln(1/δ).

4.4.2 范围计数

给定数据的值域[d]，每个用户拥有1个xi∈[d],该问题统计在范围[j,j′]内值的计数，也就是取范围[j,j′]对应的直方图.令Y=hist(X)表示用户数据的直方图统计，w∈{0,1}d为该范围的编码表示，其中1≤j≤j′≤d， wj=wj+1=…=wj′=1，其余项为0，则范围计数的结果可以用[w,Y]表示，[·,·]表示点积.

Ghazi等人在文献[64]通过矩阵机制[67-68]将该范围计数问题归约为频数估计问题.根据矩阵机制，对于给定的数据集X，可基于可逆矩阵M∈{0,1}d×d，构造噪声扰动的直方图Y+ΔM-1ψ，Δ表示敏感度，即M中列的最大1范数，z表示随机的噪声向量.扰动后范围计数的结果[w,Y+ΔM-1ψ]等同于[wM-1,MY+Δψ]，令表示正常的频数估计方法扰动后的结果，由此范围计数可通过频数估计问题得到.基于该归约，用户可根据其拥有的数据xi，选择矩阵M中第xi列非0项对应的索引值j∈[d]作为其编码，并调用之前任一频数估计方法分别对每一个值进行扰动并输出；分析器收到混洗后的用户数据，首先估计频数之后通过即可返回范围计数的结果.

为降低范围计数的误差，矩阵机制中M需满足2个条件，即wM-1有最多polylog(d)项非0值，并且Δ≤polylog(d).此时，该方法的核心问题在于如何构造满足条件的M.Ghazi等人[64]基于范围查询树T构造该矩阵M∈{0,1}d×d，不失一般性，可假设d是以2为底的幂函数.范围查询树T如图6所示，每一个结点的频数等于其孩子结点频数之和，如y2=x1+x2.该方法的核心思想是，使用y表示树T的根结点及左孩子结点对应的频数，对于任一范围内的频数均可以由y计算得到，如与用户数据相对应的叶结点v2,4对应的频数为x4=y1-y2-y4.矩阵M表示从数据x到结点y的线性变换，该矩阵中Mij=1表示yj包括了xi的值；而该矩阵的逆M-1表示y到x的线性映射.对该矩阵M而言，它的敏感度Δ=1+lb(d).结合上述矩阵机制，应用该矩阵M即可得到满足混洗差分隐私的方法.当矩阵机制中的频数估计方法基于private-coin的PRHR方法实现时，令ρ=(36(lb(2d))2dln(e×(lb(2d))d/(εcδ)))/,可得到范围计数方法PRRQ，其隐私保证与误差边界如表9所示.

4.4.3 均匀性检验

均匀性检验是指对于1个在值域[d]上的未知分布，检验该分布是否是均匀分布.下述用于均匀性检验的2个方法，均满足具有鲁棒性的差分隐私.

PUT[48]基于求和估计Cnt_SGM完成，实现了具有鲁棒性的纯差分隐私.首先，用户将其拥有的值xi独热编码为bi，对bi中的每一位用Cnt_SGM扰动为为保持混洗后不同位的区分，用户将发送给混洗器.分析器收集这些扰动后的数据，基于Cnt_SGM估计值域[d]中每一个值的计数cj，并根据这些计数[69]以及泊松参数m计算统计量当z小于均匀性检验的给定阈值τ时，该分布是均匀的.

AUT[48]实现了具有鲁棒性的近似差分隐私.该方法的编码和扰动过程与PUT方法相似，将应用于编码后每一位的Cnt_SGM方法替换为Cnt_BN方法即可.与其他问题不同的是，在表9中，这2个方法的误差用样本复杂度来度量.

5 实验评估

基于ESA的隐私保护方法对比中，计数估计、求和估计和频数估计作为重点的基础问题，存在着若干种隐私保护方法.本节将这些方法进行了实现，并对其中的重要参数进行实验评估，对于本节未提及的参数，使用该方法在获得最优边界时的参数设定.该实验一方面评估部分参数对分析结果的影响，另一方面使同一问题下不同方法的对比更加直观.

本节的实验环境为Ubuntu系统，2个6核1.70 GHz的Intel® Xeon® CPU，94 GB内存.本节所使用的数据集为不同分布的人工合成数据集，此类数据集易于调整参数，以便观察不同分布数据集对不同方法结果的影响.该实验的参数设置中，所有实验都给定同一个εc，满足近似差分隐私的方法给定δ=10-6，使它们尽可能在同一隐私保护程度下进行对比.

本节实验对比的主要内容是不同方法的均方根误差RMSE、计算代价和通信代价.其中，均方根误差表示真实值，表示方法估计值.计算代价主要以分析器的计算代价为主，用方法运行时间来衡量.通信代价以混洗器接收并转发的数据量为主，用int值的数量来衡量.

5.1 计数估计实验评估

该节通过人工生成n项满足伯努利分布Ber(q)的{0,1}数据作为数据集，并假设每个用户拥有其中1个数值，对计数估计问题中的Cnt_RR，Cnt_2M，Cnt_SGM，Cnt_BN方法进行实验评估.此处没有对Cnt_PURE进行评估，主要原因是根据其理论，该方法仅对n较大且ε较小的情况下适用，很难与其他方法放在同一标尺下度量.如当n=107时，εc需小于0.1，该方法对数据扰动的概率λ才能处于其正确的区间[0,1]，更具体地，εc=0.01时，λ=0.82；而通常其他方法的εc取小数点后第1位即可.

给定参数n=106，εc=0.9，q=0.5，上述方法的对比结果如图7(a)所示.在该部分，本节实现了随机响应方法[51]和Laplace方法[46]作为本地化差分隐私(LDP)方法和中心化差分隐私(CDP)方法的实现与这些方法进行对比.结果显示，所有混洗差分隐私方法的RMSE都介于LDP与CDP方法之间，且计算代价和通信代价均高于这2种方法.不同混洗差分隐私方法中，Cnt_SGM有着最小的估计误差；而Cnt_2M由于使用了多消息模式编码，并为了保证计数为0时结果永远为0，对估计结果使用了较为暴力的截断，有着比其他方法明显较高的估计误差和通信代价，以及较低的计算代价.

在图8～10中，分别评估不同εc，n和q对不同计数估计方法的影响.

1) 随着εc的增大，即隐私要求的降低，这些计数估计方法的误差都有明显减低，但计算代价和通信代价并无明显变化.

2) 随着n的增大，LDP方法误差增大，但混洗差分隐私方法的误差却几乎维持不动，进一步证明了在n较大的情况下混洗差分隐私方法的优越性.在计算代价和通信代价上，这些方法都随着n的增大而指数级上升.特别地，在对n值变化的实验对比中，Cnt_SGM方法一直维持着最小的估计误差；Cnt_2M方法不仅计算代价小，其计算代价增长的速度也比其他混洗差分隐私方法缓慢.

3) 随着q值的增加，数据集中1的数量变多，大多数混洗差分隐私方法的RMSE、计算代价和通信代价并无明显变化，Cnt_2M方法由于在用户端输出了更多扰动结果{1,1}，因此有着明显增加的通信代价.

5.2 频数估计实验评估

该节通过人工生成在给定值域[d]内满足正态分布的数据作为数据集，并假设每个用户拥有其中1个数值，对频数估计问题中的Hist_KR，Hist_MM，SLH，MURS进行评估，MURS方法实现时假设其添加假数据的数量为用户数量的1%.而PRHR由于计算代价和通信代价过大，不对其进行实验评估；PUCM适用于用户数量小于数据值域d的情况，亦难以与其他方法一同进行实验比较.具体地，在图7(b)所给定的参数下对PRHR方法进行评估，仅对30%用户数据进行编码就需要花费5 h并占用22 GB内存.对于同样计算代价较大的SLH和MURS方法，本节实现时通过预计算散列值与原值对应的索引表，并将该表保存，通过足够大的存储空间来换取实验结果中该方法较小的计算代价.由于现实世界中数据的存储相对廉价，该技巧对这2个方法的实际应用也是可行的.

图7(b)中对比的LDP方法是k值随机响应机制[27]，CDP方法是Laplace机制[46].在该图中，误差RMSE的纵轴坐标指数变化，Hist_KR方法有着最小的估计误差，与CDP方法近似.该结果产生的原因是，限于计算代价和通信代价，本实验选取了较小的值域对这些方法进行对比，而SLH，MURS方法主要针对值域较大的情况进行优化，当值域接近或大于用户数量时，这些方法才能体现出明显优势.从计算代价和通信代价上看，基于Cnt_2M方法实现的Hist_MM方法在这2方面均与其他方法有明显不同，并与Cnt_2M方法的实验结果相一致.

在图11～13中，分别评估不同εc，d和n对不同频数估计方法的影响.

1) 结果显示随着εc的增大，频数估计的误差和计算代价都有明显降低，通信代价几乎无变化，这与前面的理论分析是一致的.

2) 随着值域[d]的增大，Hist_KR方法的估计误差随之增大，与LDP方法变化的趋势一致；MURS方法的计算代价逐步增大，但其他混洗差分隐私方法并无明显变化，与4.2节的理论分析一致.

3) 随着用户数量n的增大，大多数方法在各个方面并没有显现出明显的变化，仅MURS方法的计算代价增加明显，这主要是混洗器添加假数据所造成的.而该实验设置中n仅从104变化到106，主要原因是除Hist_KR方法外，其他方法在本机模拟构建的总体计算代价过大(实验图仅展示分析器的计算代价)，难以进行评估.需说明的是，总体计算代价大并不代表实际中该方法难以应用，主要原因是实际应用时每个用户分别对自己的数据进行扰动，n个编码器是完全并行的；而本节进行实验模拟时这n个编码器串行或部分并行地计算，大多数消息模式方法的编码过程都长达数小时.

5.3 求和估计实验评估

该节通过人工生成满足正态分布的[0,1]数据作为数据集，并假设每个用户拥有其中1个数值，对求和估计问题中的RSum_RR，RSum_KR，RSum_RM，RSum_DSG进行评估.由于RSum_PURE方法基于Cnt_PURE方法实现，基于5.1节的分析，不对其进行实验评估.

图7(c)中，用作对比的LDP方法是Harmony机制[70]，CDP方法是Laplace机制[46].该实验中，将RSum_RM方法中多消息模式的消息数量设为3，其他方法随机舍入的精度设为10.结果显示，RSum_RM方法有着接近小的估计误差和明显较小的计算代价，RSum_DSG虽计算代价和通信代价较大，但估计误差在所有混洗差分隐私方法中最低，与4.3节的理论分析一致.

在图14，15中，分别评估不同εc和n对不同求和估计方法的影响.

1) 结果显示，随着εc的增大，求和估计的误差有明显降低，但计算代价和通信代价并无明显变化.

2) 随着n的增大，绝大多数混洗差分隐私方法的计算代价和通信代价明显升高，估计误差有轻微下降.但RSum_DSG方法出现了与前文分析不同的结果，即其RMSE随着n的增大而增加.经分析，出现该结果的主要原因是，本节使用了导出最优边界的参数，即设该方法中随机舍入的准确度使得方法的敏感度随n的增大而增加，从而导致添加噪声的变大.

5.4 实验小结

从实验分析的总体上看，混洗差分隐私方法在各统计问题的结果可用性上都有着相比本地化差分隐私方法明显更优的结果.但从通信代价和计算代价的角度分析，ESA框架中混洗器的引入，一方面使得用户数据与用户所使用的编码器之间的关联性消失，使得分析器端的计算代价增大；另一方面促使研究者们使用富含信息更多的多消息模式对数据编码，造成了分析器端的通信代价增大.如何兼顾数据的隐私性、可用性、方法的计算代价和通信代价是后续基于ESA框架构建的隐私保护方法需加以考量的部分.

从各混洗差分隐私方法评估的结果看，随着εc的增大，各方法的数据可用性均会得到提高；而随着用户数据n的增加，基于本地化差分隐私方法设计的混洗差分隐私方法在计算误差上会有轻微的增加，其他大多数混洗差分隐私方法在计算误差上没有明显变化，甚至部分方法有着轻微的降低.总体上，基于多消息模式设计的混洗差分隐私协议由于携带了更多与用户数据相关的信息，有着相对较高的数据可用性，与第4节的理论分析相一致.

6 挑战问题

当前对ESA框架的研究，以混洗差分隐私方法为主，而该方法主要聚焦于理想假设下的理论研究，重点侧重在2个方面：一方面是对该机制本身的隐私放大等理论的研究；另一方面致力于统计问题的估计，以谋求比LDP方法更高的可用性，比CDP方法更好的隐私性.但ESA框架在实际应用上，仍存在着诸多挑战，这些挑战问题一部分是ESA框架与生俱来的，另一部分是差分隐私方法的应用所带来的.由此，本节提出，在ESA框架下探索非差分隐私的隐私保护方法以应对更多更为复杂的隐私问题，是ESA框架未来发展的主要挑战与趋势.

6.1 ESA的有效性

如实验部分所示，ESA框架中混洗器的引入，打破数据之间的关联性，有效增加了数据的隐私性和可用性，但相比同类方法，分析器端存在着明显增加的计算代价和通信代价.同时由于混洗器本身通常基于MixNet等密码学网络构建，对加密数据的安全混洗操作本身就有着昂贵的计算与通信开销.带宽受限、算力受限、需要处理实时任务，这些都是ESA框架应用受阻的重要因素.如何基于该框架设计兼顾隐私度、准确度、计算代价和通信代价的隐私保护方法是ESA框架的挑战之一.

对于基于ESA框架实现的混洗差分隐私，为提高结果的准确性，设计方法通常会引入如散列簇、多消息模式的编码器、多混洗模式的混洗器等方法对数据进行处理，往往伴随着计算代价或通信代价的增加.尽管保证数据隐私性和可用性是差分隐私方法的核心，算法的计算代价和通信代价亦不容忽视.

6.2 ESA的鲁棒性

ESA框架中的混洗器作为ESA框架隐私保护的核心组件，存在着单点失败的可能，极易对整个框架的平稳运行造成影响.一旦框架中的混洗器出现问题，如被攻击、与分析器合谋、宕机等，分析器便不能收集或收集到错误的用户信息.如何增强混洗器在实际应用过程中的鲁棒性，对其混洗结果的正确性进行有效验证，亦是ESA框架的挑战之一.

对于基于ESA框架实现的混洗差分隐私方法，其方法的鲁棒性难以得到保证.一方面，当前方法假设参与计算的n个用户是可信用户，且会几乎同时发送他们扰动后的数据给混洗器.但实际问题中，该条件很难获得保证.基于现有的上述方案，当存在用户端被攻击者控制或网络状况差使用户掉线时，要么混洗器需等待极其长的时间，收集满足要求(有时是为了满足隐私放大定理中的参数n)的足量数据；要么，分析器会得到可用性和隐私性都相对理论较差的结果.另一方面，当前的混洗器分为单混洗器模式和多混洗器模式2种，但无论哪种，任一混洗器失效都会使系统存在单点失败的可能.应用现有的具有鲁棒性的秘密共享机制实现混洗器[32]是一种可能的解决方案，但应如何与基于ESA模型实现的具体问题进行结合，尚待研究.

此处，仍需重复阐明一点，第4节中介绍的部分方法可实现具有鲁棒性的差分隐私RSDP，但该鲁棒性并非本节所探讨的系统鲁棒性.RSDP的鲁棒性是仅针对隐私而言，即保证可信用户数量大于一定阈值γ时，分析器端依旧可以获得满足(ε,δ)-DP，该定义不对与数据的可用性、算法(尤其是混洗器)的等待时间、混洗器本身相关的鲁棒性做任何定义与约束.

6.3 ESA的复杂问题应用

当前ESA框架主要通过与差分隐私结合，用于解决简单的统计问题，但ESA框架本身应支持解决更复杂的问题，并不局限于此.具体而言，该复杂问题应包含2类：

一类是ESA与差分隐私结合可能解决，但尚未解决的复杂问题.如值域未知情形下的混洗差分隐私、高维度数据上的混洗差分隐私、复杂数据类型上的混洗差分隐私等.在实际应用中，这样复杂的应用场景随处可见，如当需要对用户浏览的网页进行统计时，由于网页的数量在不断增长，很难对当前作为候选集的网页进行枚举，需可处理值域未知的混洗差分隐私方法；又如，将混洗差分隐私应用在机器学习上，往往涉及到成千上万个维度的数据，需有效的隐私保护方法对其进行处理；再如，生活中常见的相对复杂的键值对类型数据，如果对键与值分别扰动，键与值之间的关联性很可能被混洗器打断，难以获得有效的估计结果.这些问题通过应用散列函数映射[52]、数据降维[71]等可能会被解决，但如何应用仍是挑战.

另一类是ESA可能解决，但差分隐私不能解决的问题，需要基于该框架对非差分隐私的方法进行探索.具体而言，差分隐私本质上可用于回答“有多少”的问题，而不是回答“是什么”的问题，对一个点是不是异常点、一个人是不是新冠肺炎的感染者这样的问题，应用差分隐私将这些数据进行扰动并不能得到可用的答案，差分隐私更趋向于将这样出现频数极低的点抹平，使其不在结果中凸显以保护隐私[72-73].但ESA框架为这样问题的回答创造了可能性，即ESA框架可在对数据进行尽可能少的扰动情况下保护隐私，便为异常点检测、新冠肺炎发现这样的问题提供条件.由此，发展非差分隐私的ESA方法十分关键!

6.4 ESA与联邦学习

联邦学习算法近2年在工业界和学术界迅速发展，该模型一定程度上打破数据孤岛，解决了隐私问题[74].该模型的基本思想是基于用户或企业独立的数据在本地进行模型的训练与更新，将模型的参数(如梯度)在服务器端进行安全聚合，从而训练一个中心化的模型提供服务器.虽然联邦学习不直接传递用户数据，仅与服务器共享模型参数，但该参数往往包含着一定程度的用户隐私，易遭受成员推理攻击[75-76]，需使用高可用性的隐私保护方法进行保护.

ESA框架与联邦学习均适用于用户在本地端进行数据处理，对处理后数据进行收集的场景，ESA框架本身的特性与联邦学习的需求不谋而合.ESA与联邦学习最简单的结合，即使用第4节所述的混洗差分隐私方法对用户共享的梯度进行保护，但该方法如何适用于参数维度巨大的机器学习模型的训练仍是难点[77-78].同时，混洗差分隐私虽相比本地化差分隐私方法引入了较小噪声，但在数据量较小、隐私损失较小的情况下仍对数据可用性有着不小的威胁.基于ESA框架发展与联邦学习高度适配的隐私保护方法应该是该方向的主要挑战.

7 结束语

数据驱动的人工智能时代，数据隐私问题备受关注，但数据可用性亦是社会与科技发展的重中之重.ESA框架为提出数据可用性更好、隐私性亦更好的隐私保护方法开辟了新的路径，混洗差分隐私即为该框架下的典型方法.混洗差分隐私方法兼具了本地化差分隐私在数据收集场景中的易用性和中心化差分隐私在数据分析结果上的可用性，在多种统计问题上的表现卓越.本文对ESA框架及其应用——混洗差分隐私方法进行了详细的综述，对混洗差分隐私下的研究方向进行总结，针对不同统计问题的若干算法进行理论分析与实验对比.基于上述总结分析的结果，本文提出了当前ESA框架应用面临的主要挑战，并以混洗差分隐私为例对这些挑战进行详细的说明.本文提出，混洗差分隐私是ESA框架应用的有效途径，但不是唯一途径，存在着诸多具有现实意义的复杂问题混洗差分隐私难以解决，但ESA为这些问题的解决创造了条件.基于ESA框架探索适用性更广的、可用性更高的、非差分隐私的隐私保护算法是数据隐私保护未来可能的发展方向之一.

作者贡献声明：王雷霞负责论文总结、撰写与实验；孟小峰指导总体架构.

参考文献

[1]Meng Xiaofeng, Zhu Minjie, Liu Junxu. Quantitative research on pivacy risk of large-scale mobile users[J]. Journal of Information Security Research, 2019, 5(9): 778-788 (in Chinese)(孟小峰, 朱敏杰, 刘俊旭. 大规模用户隐私风险量化研究[J]. 信息安全研究, 2019, 5(9): 778-788)

[2]Meng Xiaofeng, Zhu Minjie, Liu Lixin. Research on data monopoly and its governance modes[J]. Journal of Information Security Research, 2019, 5(9): 789-797 (in Chinese)(孟小峰, 朱敏杰, 刘立新, 等. 数据垄断与其治理模式研究[J]. 信息安全研究, 2019, 5(9): 789-797)

[3]Galoc N.15 of the biggest data breaches in the last 15 years[EB/OL]. [2021-04-20]. https://hostingtribunal.com/blog/biggest-data-breach-statistics/

[4]Intersoft Consulting. General Data Protection Regulation[EB/OL]. [2021-04-20]. https://gdpr-info.eu/

[5]National Internet Information Office. Measures for Data Security Management(Draft for Comments)[EB/OL]. [2021-04-20]. http://www.moj.gov.cn/government_public/content/2019-05/28/657_235862.html

[6]Meng Xiaofeng, Wang Leixia, Liu Junxu. Data privacy, monopoly and fairness for AI[J]. Big Data Research, 2020, 6(1): 35-46 (in Chinese)(孟小峰, 王雷霞, 刘俊旭. 人工智能时代的数据隐私、垄断与公平[J].大数据, 2020, 6(1): 35-46)

[7]Meng Xiaofeng, Zhang Xiaojian. Big data privacy management[J]. Journal of Computer Research and Development, 2015, 52(2): 265-281 (in Chinese)(孟小峰, 张啸剑. 大数据隐私管理[J]. 计算机研究与发展, 2015, 52(2): 265-281)

[8]Sweeney L. Achieving k-anonymity privacy protection using generalization and suppression[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 571-588

[9]Machanavajjhala A, Kifer D, Gehrke J, et al. l-diversity: Privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 44-95

[10]Li Ninghui, Li Tiancheng, Venkatasubramanian S. t-closeness: Privacy beyond k-anonymity and l-diversity[C] //Proc of the 23rd IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2007: 106-115

[11]Xiao Xiaokui, Tao Yufei. M-invariance: Towards privacy preserving re-publication of dynamic datasets[C] //Proc of the 2007 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2007: 689-700

[12]Dwork C. Differential privacy: A survey of results[C] //Proc of the 5th Int Conf on Theory and Applications of Models of Computation. Berlin: Springer, 2008: 1-19

[13]Dwork C, Smith A. Differential privacy for statistics: What we know and what we want to learn[J]. Journal of Privacy and Confidentiality, 2009, 1(2): 135-154

[14]Ye Qingqing, Meng Xiaofeng, Zhu Minjie, et al. Survey on local differential privacy[J]. Journal of Software, 2018, 29(7): 159-183 (in Chinese)(叶青青, 孟小峰, 朱敏杰, 等. 本地化差分隐私研究综述[J]. 软件学报, 2018, 29(7): 159-183)

[15]Erlingsson , Pihur V, Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C] //Proc of the 2014 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 1054-1067

[16]Cormode G, Jha S, Kulkarni T, et al. Privacy at scale: Local differential privacy in practice[C] //Proc of the 2018 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2018: 1655-1658

[17]Ding Bolin, Kulkarni J, Yekhanin S. Collecting telemetry data privately[C] //Advances in Neural Information Processing Systems. New York: Curran Associates, 2017: 3571-3580

[18]Bittau A, Erlingsson ú, Maniatis P, et al. Prochlo: Strong privacy for analytics in the crowd[C] //Proc of the 26th ACM Symp on Operating Systems Principles. New York: ACM, 2017: 441-459

[19]Laur S, Willemson J, Zhang Bingsheng. Round-efficient oblivious database manipulation[C] //Proc of the 14th Int Conf on Information Security. Berlin: Springer, 2011: 262-277

[20]Sampigethaya K, Poovendran R. A survey on mix networks and their secure applications[J]. Proceedings of the IEEE, 2006, 94(12): 2142-2181

[21]Hackenjos T, Hahn F, Kerschbaum F. SAGMA: Secure aggregation grouped by multiple attributes[C] //Proc of the 2020 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2020: 587-601

[22]Rass S, Wigoutschnigg R, Schartner P. Doubly-anonymous crowds: Using secret-sharing to achieve sender and receiver anonymity[J]. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, 2011, 2(4): 27-41

[23]Fauzi P, Lipmaa H, Zając M. A shuffle argument secure in the generic model[C] //Proc of the 22nd Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2016: 841-872

[24]Maniatis P, Mironov I, Talwar K. Oblivious stash shuffle[J]. arXiv preprint, arXiv: 1709.07553, 2017

[25]Sabt M, Achemlal M, Bouabdallah A. Trusted execution environment: What it is, and what it is not[C] //Proc of the 14th IEEE Int Conf on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ: IEEE, 2015: 57-64

[26]Erlingsson ú, Feldman V, Mironov I, et al. Amplification by shuffling: From local to central differential privacy via anonymity[C] //Proc of the 30th Annual ACM-SIAM Symp on Discrete Algorithms. New York: ACM, 2019: 2468-2479

[27]Kairouz P, Oh S, Viswanath P. Extremal mechanisms for local differential privacy[J]. The Journal of Machine Learning Research, 2016, 17(1): 492-542

[28]Cheu A, Smith A, Ullman J, et al. Distributed differential privacy via shuffling[C] //Proc of the 38th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2019: 375-403

[29]Beimel A, Nissim K, Omri E. Distributed private data analysis: Simultaneously solving how and what[C] //Proc of the 28th Annual Int Cryptology Conf. Berlin: Springer, 2008: 451-468

[30]Chan T H H, Shi E, Song Dawn. Optimal lower bound for differentially private multi-party aggregation[C] //Proc of the 20th Annual European Symp on Algorithms. Berlin: Springer, 2012: 277-288

[31]Shi E, Chan T H H, Rieffel E, et al. Privacy-preserving aggregation of time-series data[C/OL] //Proc of the 18th Annual Network & Distributed System Security Symp. ISOC, 2011: 1-17 [2021-04-28]. https://www.ndss-symposium.org/wp-content/uploads/2017/09/shi.pdf

[32]Goryczka S, Xiong Li. A comprehensive comparison of multiparty secure additions with differential privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2015, 14(5): 463-477

[33]Ishai Y, Kushilevitz E, Ostrovsky R, et al. Cryptography from anonymity[C] //Proc of the 47th Annual IEEE Symp on Foundations of Computer Science(FOCS’06). Piscataway, NJ: IEEE, 2006: 239-248

[34]Balle B, Bell J, Gascón A, et al. Improved summation from shuffling[J]. arXiv preprint, arXiv: 1909.11225, 2019

[35]Balle B, Bell J, Gascón A, et al. Private summation in the multi-message shuffle model[J]. arXiv preprint, arXiv: 2002.00817, 2020

[36]Goldreich O. Foundations of Cryptography(Volume 2): Basic Applications[M]. Cambridge, UK: Cambridge University Press, 2009: 619-626

[37]Paillier P. Public-key cryptosystems based on composite degree residuosity classes[C] //Proc of the Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1999: 223-238

[38]Damgard I, Geisler M, Kroigard M. Homomorphic encryption and secure comparison[J]. International Journal of Applied Cryptography, 2008, 1(1): 22-31

[39]Chaum D, Crépeau C, Damgard I. Multiparty unconditionally secure protocols[C] //Proc of the 20th Annual ACM Symp on Theory of Computing. New York: ACM, 1988: 11-19

[40]Wang Tianhao, Ding Bolin, Xu Min. MURS: Practical and robust privacy amplification with multi-party differential privacy[J]. arXiv preprint, arXiv: 1908.11515, 2019

[41]Chowdhury A R, Wang Chenghong, He Xi, et al. Crypt-ε: Crypto-assisted differential privacy on untrusted servers[C] //Proc of the 2020 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2020: 603-619

[42]Roth E, Noble D, Falk B H, et al. Honeycrisp: Large-scale differentially private aggregation without a trusted core[C] //Proc of the 27th ACM Symp on Operating Systems Principles. New York: ACM, 2019: 196-210

[43]Allen J, Ding Bolin, Kulkarni J, et al. An algorithmic framework for differentially private data analysis on trusted processors[J]. arXiv preprint, arXiv:1807.00736, 2018

[44]Dwork C. Differential privacy[C] //Proc of the 33rd Int Colloquium, Part II, Automata, Languages and Programming. Berlin: Springer, 2006: 1-12

[45]Zhang Xiaojian, Meng Xiaofeng. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949 (in Chinese)(张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[J].计算机学报, 2014, 37(4): 927-949)

[46]Dwork C, Roth A. The algorithmic foundations of differential privacy[J]. Foundations and Trends in Theoretical Computer Science, 2014, 9(3/4): 211-407

[47]Balle B, Bell J, Gascón A, et al. The privacy blanket of the shuffle model[C] //Proc of the 39th Annual Int Cryptology Conf. Berlin: Springer, 2019: 638-667

[48]Balcer V, Cheu A, Joseph M, et al. Connecting robust shuffle privacy and pan-privacy[J]. arXiv preprint, arXiv: 2004.09481, 2020

[49]Duchi J C, Jordan M I, Wainwright M J. Local privacy, data processing inequalities, and statistical minimax rates[J]. arXiv preprint, arXiv: 1302.3203, 2013

[50]Duchi J C, Jordan M I, Wainwright M J. Minimax optimal procedures for locally private estimation[J]. Journal of the American Statistical Association, 2018, 113(521): 182-201

[51]Warner S L. Randomized response: A survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309): 63-69

[52]Erlingsson , Feldman V, Mironov I, et al. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation[J]. arXiv preprint, arXiv: 2001.03618, 2020

[53]Dwork C, Kenthapadi K, McSherry F, et al. Our data, ourselves: Privacy via distributed noise generation[C] //Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2006: 486-503

[54]Ghosh A, Roughgarden T, Sundararajan M. Universally utility-maximizing privacy mechanisms[J]. SIAM Journal on Computing, 2012, 41(6): 1673-1693

[55]Johnson N L, Kemp A W, Kotz S. Univariate Discrete Distributions[M]. Hoboken, NJ: John Wiley & Sons, 2005

[56]Cormode G, Muthukrishnan S. An improved data stream summary: The count-min sketch and its applications[J]. Journal of Algorithms, 2005, 55(1): 58-75

[57]Wang Tianhao, Blocki J, Li Ninghui, et al. Locally differentially private protocols for frequency estimation[C] //Proc of the 26th USENIX Security Symp Security. Berkeley, CA: USENIX Association, 2017: 729-745

[58]Ghazi B, Pagh R, Velingker A. Scalable and differentially private distributed aggregation in the shuffled model[J]. arXiv preprint, arXiv: 1906.08320, 2019

[59]Ghazi B, Manurangsi P, Pagh R, et al. Private aggregation from fewer anonymous messages[C] //Proc of the 39th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2020: 798-827

[60]Balle B, Bell J, Gascón A, et al. Differentially private summation with multi-message shuffling[J]. arXiv preprint, arXiv: 1906.09116, 2019

[61]Balcer V, Cheu A. Separating local & shuffled differential privacy via histograms[J]. arXiv preprint, arXiv: 1911.06879, 2019

[62]Ghazi B, Golowich N, Kumar R, et al. Pure differentially private summation from anonymous messages[J]. arXiv preprint, arXiv: 2002.01919, 2020

[63]Wang Tianhao, Ding Bolin, Xu Min, et al. Improving utility and security of the shuffler-based differential privacy[J]. arXiv preprint, arXiv: 1908.11515, 2019

[64]Ghazi B, Golowich N, Kumar R, et al. On the power of multiple anonymous messages[J]. arXiv preprint, arXiv: 1908.11358, 2019

[65]Bassily R, Nissim K, Stemmer U, et al. Practical locally private heavy hitters[J/OL]. Journal of Machine Learning Research, 2020, 21(16): 1-42 [2021-04-28]. https://jmlr.org/papers/volume21/18-786/18-786.pdf

[66]Bun M, Nelson J, Stemmer U. Heavy hitters and the structure of local privacy[J/OL]. ACM Transactions on Algorithms, 2019, 15(4): 1-40 [2021-04-28]. https://dl.acm.org/doi/pdf/10.1145/3344722

[67]Li Chao, Hay M, Rastogi V, et al. Optimizing linear counting queries under differential privacy[C] //Proc of the 29th ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems. New York: ACM, 2010: 123-134

[68]Li Chao, Miklau G. An adaptive mechanism for accurate query answering under differential privacy[J]. The VLDB Journal, 2012, 5(6): 514-525

[69]Amin K, Joseph M, Mao Jieming. Pan-private uniformity testing[C/OL] //Proc of the 33rd Conf on Learning Theory. PMLR, 2020: 183-218 [2021-04-28]. http://proceedings.mlr.press/v125/amin20a.html

[70]Nguyên T T, Xiao Xiaokui, Yang Yin, et al. Collecting and analyzing data from smart device users with local differential privacy[J]. arXiv preprint, arXiv: 1606.05053, 2016

[71]Qin Zhan, Yang Yin, Yu Ting, et al. Heavy hitter estimation over set-valued data with local differential privacy[C] //Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 192-203

[72]Asif H, Papakonstantinou P A, Vaidya J. How to accurately and privately identify anomalies[C] //Proc of the 2019 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2019: 719-736

[73]Asif H, Talukdar T, Vaidya J, et al. Differentially private outlier detection in a collaborative environment[J]. International Journal of Cooperative Information Systems, 2018, 27(3): No.1850005

[74]Yang Qiang, Liu Yang, Chen Tianjian, et al. Federated machine learning: Concept and applications[J/OL]. ACM Transactions on Intelligent Systems and Technology, 2019, 10(2): 1-19 [2021-04-28]. https://dl.acm.org/doi/pdf/10.1145/3298981

[75]Liu Junxu, Meng Xiaofeng. Survey on privacy-preserving machine learning[J]. Journal of Computer Research and Development, 2020, 57(2): 346-362 (in Chinese)

(刘俊旭, 孟小峰. 机器学习的隐私保护研究综述[J]. 计算机研究与发展, 2020, 57(2): 346-362)

[76]Nasr M, Shokri R, Houmansadr A. Comprehensive privacy analysis of deep learning: Stand-alone and federated learning under passive and active white-box inference attacks[J]. arXiv preprint, arXiv: 1812.00910, 2018

[77]Liu Ruixuan, Cao Yang, Chen Hong, et al. FLAME: Differentially private federated learning in the shuffle model[J]. arXiv preprint, arXiv: 2009.08063, 2020

[78]Girgis A M, Data D, Diggavi S, et al. Shuffled model of federated learning: Privacy, communication and accuracy trade-offs[J]. IEEE Journal on Selected Areas in Information Theory, 2021, 2(1): 464-478

ESA: A Novel Privacy Preserving Framework

Wang Leixia and Meng Xiaofeng

(School of Information, Renmin University of China, Beijing 100872)

Abstract With the rapid development of data-driven intelligent technologies, large-scale data collection has become a main application scenario of data governance and privacy-preserving. Local differential privacy technology as a mainstream technology has been widely used in companies, such as Google, Apple, and Microsoft. However, this technology has a fatal drawback, which is its poor data utility caused by accumulative noises added to users’ data. To juggle the data privacy and utility, the ESA (encode-shuffle-analyze) framework is proposed. This framework tries adding noises as little as possible while maintaining the same degree of data privacy, which ensures that any user’s sensitive information can be used effectively but cannot be recognized from collected data. Considering the elegant and strict definition of differential privacy in math, the major implementation of the ESA framework is based on differential privacy, named shuffle differential privacy. In the case of the same privacy loss, the data utility of shuffled differential privacy method is higher than that of local differential privacy, closing to the central differential privacy but does not rely on a trusted third party. This paper is a survey about this novel privacy-preserving framework. Based on the popular shuffle differential privacy technology, it analyzes this framework, summarizes the theoretical and technical foundations, and compares different privacy-preserving mechanisms under different statistical issues theoretically and experimentally. Finally, this work proposes the challenges of the ESA, and prospects the implementation of non-differential privacy methods over this framework.

Key words privacy preserving; ESA framework; local differential privacy; central differential privacy; shuffle differential privacy; data collection

(leixiawang@ruc.edu.cn)

中图法分类号 TP309

收稿日期：20201221；修回日期：20210527

基金项目：国家自然科学基金项目(61941121,91846204,62172423)

This work was supported by the National Natural Science Foundation of China (61941121, 91846204, 62172423).

通信作者：孟小峰(xfmeng@ruc.edu.cn)

Wang Leixia, born in 1994. PhD candidate. Her main research interests include secure data collection, differential privacy and its application.

王雷霞，1994年生.博士研究生.主要研究方向为安全数据收集、差分隐私及其应用.

Meng Xiaofeng, born in 1964. PhD, professor and PhD supervisor. Fellow of CCF. His main research interests include database systems, data intelligence, data privacy and governance, spatial and social computing.

孟小峰，1964年生.博士，教授，博士生导师，CCF会士.主要研究方向为数据库系统、数据智能、隐私保护与数据治理、社会计算.