本地化差分隐私综述.pdf

数据与计算发展前沿，2 0 2 3，5（5）第5 卷第5 期2 0 2 3 年10 月Vol.5No.5Oct.2023专刊：数据要素安全高效流通的关键技术Special Issue:Key Technologies for safe and Efficient Circulation of Data ElementsISSN 2096-742XCN 10-1649/TPdoiePIcOPersistent Identifiers foreResearch文献CSTR:32002.14.jfdc.CN10-1649/TP.2023.05.007文献DOI:10.11871/jfdc.issn.2096-742X.2023.05.007页码：7 4-9 7获取全文本地化差分隐私综述孙一帆12，张锐1-2 ，陶杨12，高碧柔12，秦诗涵12，安超121.中国科学院信息工程研究所，信息安全国家重点实验室，北京10 0 0 8 52.中国科学院大学，网络空间安全学院，北京10 0 0 4 9摘要：【目的】本地化差分隐私是优秀的隐私保护模型，能够在数据共享、发布的场景下对群体进行统计分析，保护个人数据隐私。本文围绕本地化差分隐私进行综述，为未来工作提供参考。【文献范围】本文调研了来自主流会议、期刊的本地化差分隐私领域的论文，并进行了总结归纳。【方法】本文以数据统计分析任务类型为线索，从基于本地化差分隐私模型的频率估计、均值估计、多维数据统计分析和机器学习4 个方面展开调研。本文对相关研究进行了对比分析，对关键问题进行了总结，对现有工作的不足进行了讨论，对未来的研究方向进行了展望。【结果】本地化差分隐私模型能够在用户数据被采集、分析时，为用户个人数据隐私提供强有力的隐私保护。【局限】本文以数据统计分析任务类型为线索，未对图数据相关研究进行总结。结论】本地化差分隐私作为一种优秀的隐私保护模型，得到学者们的关注后迅速发展，但是仍然面临着诸多问题和挑战，值得进一步研究和探索。关键词：本地化差分隐私；频率估计；均值估计；多维数据统计分析；机器学习A Survey on Local Differential PrivacySUN Yifan,ZHANG Rui,TAO Yang,GAO Birou,QIN Shihan,AN Chao?1.SKLOIS,Institute of Information Engineering,Beijing 100085,China2.School of Cyber Security,University of Chinese Academy of Sciences,Bejing 100049,ChinaAbstract:Objective This paper systematically introduces local differential privacy and provides a refer-ence for the protection of personal data privacy under data sharing and publishing.CoverageThis paper investigates and summarizes papers from mainstream conferences and journals inthe field of local differential privacy.Methods This paper takes the type of statistical dataanalysis task as a clue and conducts research based on local differential privacy from four as-pects,which concludes frequency estimation,mean estimation,multidimensional data statisti-cal analysis,and machine learning.This paper makes a comparative analysis of relevant stud-ies,summarizes key issues,discusses the shortcomings of existing work,and looks forward tofuture research directions.Results The local differential privacy model can provide strong pri-vacy protection for users personal data privacy when user data is collected and analyzed.Lim-itations This paper takes the type of statistical data analysis task as a clue and does not summa-基金项目：国家自然科学基金项目（6 2 17 2 4 11,6 2 17 2 4 0 4,6 19 7 2 0 9 4,6 2 2 0 2 4 5 8)*通信作者：张锐（E-mail:r-)74数据与计算发展前沿，2 0 2 3，5（4）孙一帆等：本地化差分隐私综述rize the research related to graph data.Conclusions Local differential privacy,as an excellent privacy-preserv-ing model,has developed rapidly after gaining the attention of scholars.But it still faces many problems and chal-lenges,which are worthy of further research and exploration.Keywords:local differential privacy;frequency estimation;mean estimation;multidimensional data statistical analysis;machine learning引言近年来，数据共享、发布时的个人数据隐私保护问题受到了广泛的关注。针对个人数据隐私保护问题，各政府、组织陆续出台了相应的法律法规。欧盟于2 0 16 年通过了一般数据保护法案；美国于2 0 2 2 年公布了数据隐私和保护法草案2；2 0 17 年6 月起，我国施行了中华人民共和国网络安全法3 ；2 0 2 1年9 月起，我国施行了中华人民共和国数据安全法。如何在数据统计分析时保护个人数据隐私也是近年来学术界的研究热点。差分隐私5 作为一种优秀的隐私保护模型，能够在数据共享、发布的场景下，实现对群体的统计分析，保护个人的数据隐私。差分隐私相较于数据匿名技术具有显著优势。数据匿名技术，如k-匿名 6 、1-多样性 7 和t-紧密性 8 ,通过保证多条记录间的不可区分性来保护单个用户的隐私，需要特殊的攻击假设,容易受到一致性攻击和背景知识攻击。差分隐私拥有严格的数学定义且不依赖于攻击者的背景知识，任意添加或删除一条记录,得到的查询结果对于攻击者而言是不可区分的,攻击者不能根据统计结果以明显优势推断单个用户的隐私信息。2006年Dwork提出了差分隐私 5 ,随着差分客户端数据分析者可信的数据兴数据编数据扰收集者医疗V1数据隐私化处理V2V(a)中心化差分隐私隐私的深人研究，差分隐私模型主要分为中心化差分隐私9 本地化差分隐私10 和混洗差分隐私 三大类。中心化差分隐私、本地化差分隐私和混洗差分隐私框架对比如图1所示。中心化差分隐私(Centralized Differential Privacy,CDP)对于敏感信息的保护始终基于一个前提假设：可信的数据收集者，即保证数据收集者不会窃取或泄露用户的敏感信息。然而，在实际应用中，即使第三方数据收集者宣称不会窃取和泄露用户的敏感信息，用户的隐私依旧很难得到保障。混洗差分隐私(Shuffled Differential Privacy,SDP)打破了用户和数据的关联性，将经过隐私化处理的数据混洗打乱后发送给数据收集者，然而高维数据之间的关联性也很可能被混洗服务器破坏，影响统计分析结果。本地化差分隐私(Local Differen-tial Privacy,LDP)不同于中心化差分隐私对于可信数据收集者的假设，其针对的是不可信的数据收集者，且无需设置额外的服务器。本地化差分隐私模型中，每个用户独立地对个人数据进行隐私化处理。隐私化处理过程从数据收集方转移到单个用户端上，可降低从不可信数据收集者泄露原始数据的风险。本文围绕本地化差分隐私展开调研和总结归纳。本地化差分隐私模型能够保护统计分析时用户个人数据的隐私。基于本地化差分隐私的客户端P(E(vi)E(v)不可信码处理动处理主教育E(v2)、数据编数据扰金融码处理E数擦优：电商鹤处理动理P(E(v)(b)本地化差分隐私图1中心化差分隐私、本地化差分隐私和混洗差分隐私框架对比Fig.1Comparisons of framework of CDP,LDP and SDP数据分析者的数据医疗+鹤处理收集者P(E(v2)教育、数据编动处理金融鹤处理E(v)电商数据编欧P(EC数据扰码处理(c)混洗差分隐私客户端E(v)数据编数据扰动处理E(v2)P(E(v)数据扰动处理：P(E(vi)数据混洗的数据置医疗收集者服务器主教育?金融电商75数据分析者不可信数据与计算发展前沿，2 0 2 3 5（5）孙一帆等：本地化差分隐私综述数据采集、分析流程主要分成四步：编码、扰动、聚合和分析。编码使用户数据能够被本地化差分隐私机制处理；扰动是对编码后的数据进行扰动处理，用户发送扰动数据给数据收集者；聚合是服务器端的数据收集者对不同用户端发送的扰动数据进行聚合和发布；分析是由数据分析者根据数据发布结果进行数据统计分析。针对不同的数据类型、数据统计分析任务，本地化差分隐私机制有很大区别。对现有本地化差分隐私进行综述总结，为该领域工作提供参考，是有重要意义的。现有的本地化差分隐私综述 12-15 能够对该领域的研究工作起到启发作用，然而，仍有不足之处需要完善。Zhao等人12 仅讨论了车联网场景下的本地化差分隐私机制。论文 13-15 1未关注针对本地化差分隐私模型的投毒攻击。本文调研了来自主流会议、期刊的本地化差分隐私领域的论文，聚焦最新的研究进展，以数据统计分析任务类型为线索，从基于本地化差分隐私模型的频率估计、均值估计、多维数据统计分析和机器学习4 个方面进行了总结归纳。本文其余部分组织结构如下：本文第1节介绍了本地化差分隐私基础知识；第2 节对基于本地化差分隐私的频率估计进行了总结归纳；第3节对基于本地化差分隐私的均值估计进行了对比分析；第4 节概述了基于本地化差分隐私的多维数据统计分析；第5 节介绍了本地化差分隐私与机器学习的结合；第6 节对未来研究方向进行了展望；第7 节对全文进行了总结。1本地化差分隐私基础本节将介绍本地化差分隐私基础，包括符号介绍、本地化差分隐私的定义、性质和针对本地化差分隐私的攻击方法。1.1符号假设共有n个用户，用户集可形式化表示为U=(ui,uz,u)。每个用户发送h维数据。对于分类型数据而言，一个属性A对应d个可能的取值,属性域A=u1,2,a)。对于数值型数据而言，数据值取值范围为-1,1。每个用户j(1jn)将编码、扰动处理后的数据发送给服务器端，服务器端的数据收集者对收集的数据聚合、发布，由数据分析者完成数据统计分析。常用的符号及其描述如表1所示。表1符号Table1Notations符号描述n用户总数数据维度d属性域空间大小/u原始数据/扰动数据R随机算法E隐私预算P/q扰动概率H/H哈希函数集合/哈希函数数据，的真实/统计/估计频数.数据！的真实/估计频率1.2本地化差分隐私本地化差分隐私作为一种优秀的隐私保护模型，能够在统计分析群体信息时，保护用户个人数据隐私。用户个人数据的变化不会对数据统计结果产生显著的影响，攻击者无法以明显优势根据发布数据的统计分析结果推断用户个体的隐私信息。本地化差分隐私形式化定义如下。定义1:本地化差分隐私(-LDP)。给定一个随机算法R及其定义域Dom(R)和值域Ran(R)，当且仅当算法R对两个输人值和u(u,ueDom(R)进行计算得到相同输出结果y(yERan(R)的概率满足下列不等式：PrR(u)=y e.PrR(u)=g则称算法R满足E-LDP。其中，E为隐私预算，E越小，隐私保护程度越高，扰动后数据的可用性越差；反之，E越大，隐私保护程度越低，扰动后数据的可用性越好。(1)76数据与计算发展前沿，2 0 2 3，5（4）孙一帆等：本地化差分隐私综述1.3本地化差分隐私性质MSE=d(3)本地化差分隐私具有顺序组合性质，即满足本地化差分隐私的个算法应用于同一数据的结果也是满足本地化差分隐私的。性质1：顺序组合。给定数据以及任意m个算法(R,R2,Rm),且R,(1im)满足E;-LDP。那么将m个算法(R,R2,Rm)作用于同一数据时,算法序列(R(),R,(u),Rm()将满足e-LDP,其中e=Ze。1.4数据可用性本地化差分隐私模型中，用户在本地对数据隐私化处理，不可避免地对统计分析结果产生影响。学者们设计本地化差分隐私机制时，在隐私性和数据可用性之间做权衡。数据可用性的度量方法主要分为两类，一类为误差度量法,另一类为信息损失度量法7。误差度量法，包括平均绝对误差(MeanAb-solute Error,MAE)和均方误差(Mean Squared Er-ror,MSE)。把数据分析者得到的基于本地化差分隐私的估计结果和原始数据真实数值进行比较。以属性A频率估计为例，属性域A=(,D2,),对于经过本地化差分隐私机制处理后的属性A的取值，得到估计频率后度量误差，其中.-MAE=1di=1客户端VE(v)数据编码处理数据扰动处理P(E(vi)V2E(v2)数据编码处理一类数据扰动处理：数据编码处理类E(v)数据扰动处理P(E(v)(a)伪造原始数据的投毒攻击图2针对本地化差分隐私不同的投毒攻击方式Fig.2Different data poisoning methods for LDP信息损失度量法，可以根据KL散度(Kull-back-LeiblerDivergence)衡量两个分布之间的差异。假设P(s)，Q()是随机变量X上的两个概率分布，可以对应为统计结果的真实分布和估计分布,那么,两个分布的相对嫡,即KL散度,可以定义为：KL(PIQ)=EP(a)log=1误差或者信息损失越小，数据可用性越好，也越容易泄露用户个人隐私。学者们致力于保护数据隐私的同时，提高数据可用性。1.5攻击方式本地化差分隐私模型中,用户在本地对数据进行隐私化处理后发送给数据收集者，数据收集者对数据进行聚合和发布，数据分析者进行数据统计分析。攻击者想要通过投毒攻击的方式改变数据统计分析的结果。针对本地化差分隐私的投毒攻击的方式主要包括两大类，分别为伪造原始数据的投毒攻击和伪造扰动数据的投毒攻击，如图2 所示。其中，伪造原始数据的投毒攻击,攻击者将LDP机制视为一个黑盒，不关心具体参数，只设计输入的原始数据，原始数据经过LDP机制处理后发送给数据收集者。伪造原始数据的投毒攻击的虚假用户不容易被检测出来，然而该方法受限LDP(2)机制，不能以最少的数据量达到影响统计分析结数据分析者客户端V1E(v)数据收集者不可信的教育P(E(v2)V-1数据编码处理楼数据扰动处理￥金融：电商P()Q(x)医疗数据编码处理里数据扰动处理P(E(vi)数据收集者不可信的医疗：E(vr-1)P(E(ve-1)(b)伪造扰动数据的投毒攻击(4)数据分析者教育?金融：电商77数据与计算发展前沿，2 0 2 3 5（5）孙一帆 等：本地化差分隐私综述果的目的。伪造扰动数据的投毒攻击,攻击者知悉客户端采用的LDP机制。攻击者根据LDP机制直接伪造扰动数据，将设计的扰动数据直接发送给数据收集者。其中的关键是攻击者根据LDP机制设计什么样的伪造数据、最少发送多少伪造数据给数据收集者,能够使数据统计分析的结果达到攻击者的预期。针对本地化差分隐私，现有的投毒攻击主要集中在分类型数据 8 数值型数据 19 和键值数据 2 0 上。为了减弱投毒攻击对基于本地化差分隐私的数据统计分析的影响,学者们也提出了相关方法抵御投毒攻击，包括虚假用户检测18 、聚类分析 19 、异常值检测 2 0 等。2基于本地化差分隐私的频率估计基于本地化差分隐私的频率估计，是指原始的分类型数据经过编码、扰动后发送给数据收集者，由数据收集者对数据进行聚合、校准得到频率估计的结果 2 1-2 3 。频率数据，是数据统计分析的重要基础，也是构建数据分布,完成数据挖掘、机器学习不可或缺的数据。针对一个问题,用户可能有一个回答(如民族)或者多个回答(如喜欢的电影）。本节按照一维属性下分类型数据用户回答的数据值数量进行分类，从单属性单值数据和单属性集值数据两方面，对基于本地化差分隐私的频率估计机制展开分析和总结。2.1单属性单值数据的频率估计单属性单值数据是指用户仅发送一个数据值。数据收集者对来自多用户的数据值进行聚合和校准，得到属性域中每一个值对应的频率。可形式化表示为，假设共有n个用户，用户集可表示为U=(u,uz,un)，一个属性A对应d个数据值，属性域A=(u,2,a)，每个用户j(1jn)仅发送一个数据值u;(u;EA),在本地化差分隐私模型下估计v(1id)的频率于,用于统计分析。按照数据编码、扰动的技术特点进行划分，单值分类型数据的频率估计机制分为直接扰动 17-2 4 和先编码后扰动两大类，其中先编码后扰动包括独热编码 2 5 、基于哈希函数的机制 2 4 2 6 、基于矩阵变换的机制 2 7-2 8 1和子集选择机制 2 9-3 1。接下来将介绍直接扰动和先编码后扰动的典型机制,并对它们进行对比分析。2.1.1直接扰动直接扰动，即用户的数据能够直接进行随机响应，无需进行数据编码步骤，通过随机响应扰动完成本地原始数据的隐私化处理。典型机制包括二元随机响应(BinaryRandomized Response,BRR)17和广义随机响应(Generalized Random-ized Response,GRR)24(1)BRR机制。BRR机制为二元数据提供基础的随机响应，数据项的域d=2。随机响应 3 主要是利用对敏感问题响应的不确定性对原始数据进行隐私保护，是本地化差分隐私模型中采用的主要的扰动机制。BRR机制中，二元数据以p的概率输出真实值,以q(q=1-p)的概率输出相反值。用户的数据经过扰动变成，该扰动过程如公式（5)所示。PrR(u,)=u)其中,扰动概率p=e一e+1数据收集者对扰动后的结果进行聚合和校准。通过聚合可以得到数据，的统计结果，。因为统计结果并非真实比例的无偏估计，所以需要对统计结果进行校准,得到,的频数估计值，：i-nn=p-q进一步计算得到频率估计值于，：n代人p和g的值,可得.的频率估计值于pBR：e=e+11e+11e+1=V(5)(6)(7)78数据与计算发展前沿，2 0 2 3，5（4）孙一帆等：本地化差分隐私综述(8)数据项进行先编码后扰动。.e+1,BRRne+1)e-1BRR机制中u,的频率估计值j,BR的近似方Varlr(9)S-1(2)GRR机制。GRR是二元随机响应BRR的扩展。BRR仅对包含两种取值的离散型数据进行响应，对于超过两种取值的数据并不适用。GRR对于数据项d(d2)个取值的情况，以1的的向量进行扰动。UE将数据项,按照独热编码的概率响应真实的结果,以d-1+e概率响应d-1个结果中的任意一种,使其满足E-LDP。当数据项的取值空间逐渐增大时，GRR方法的精度急剧下降。用户的数据；经过扰动变成；，该扰动过程如公式(10)所示。e,ifv,=V;PR(o.)=0i=d-1+esE1,ifu(d-1+e其中,扰动概率p=ed-1+e?q=d-1+es数据收集者通过聚合可以得到数据，的统计结果亢，因为统计结果并非真实比例的无偏估计，所以需要对统计结果进行校准，校准后可得，的频率估计值f.cR：1GRR机制中;的频率估计值f,CR的近似方差Var,为：JGRR直接扰动机制对原始数据项的数据格式有很高要求，且当数据项的取值空间d较大时，直接扰动后得到的频率估计的精度下降，通信开销大，数据可用性变差。为了解决数据项取值空间较大的问题，学者们设计本地化差分隐私机制对2.1.2先编码扰动先编码后扰动，即用户数据的格式不适合直接进行随机响应，需要先对原始数据编码，再对编码后的数据扰动，通过随机化扰动完成本地原始数据的隐私化处理。先编码后扰动机制主要分为四类，分别为独热编码、基于哈希函数、基于矩阵变换和子集选择。(1)独热编码。一元编码(Unary Encoding,UE)25与上述两种机制直接对数据项扰动不同，UE对数据项进行独热编码,然后将编码后生成d-1+e的原则将原始数据编码为d位的向量B,其中，该数据项对应的第i位比特位为1,其余比特位都为0,例如可表示为B=0,1,0,0。比特位为1时，以p的概率输出真实值，以1-p的概率输出相反值；比特位为0 时,以1-q的概率输出真实值，以的概率输出相反值。编码后的向量B的扰动过程如公式(13)所示。(10)其中,p1,且P=(-1)g+11时,UE满足E-LDP。UE机制中o,的频率估计值Jue：(-y(p-d-1+e(11)e-1=e+d-2n(es-1)(13)q,if Bi=0.qes当E=ln(1-p)q(14)UE机制中,的频率估计值ue的近似方差Va为:JUE(12)对称的一元编码（Symmetric Unary Encod-ing,SUE)2,在UE的基础上,令p+q=1,使得对 0 和 1 的处理对称。结合公式 P=（-1)+1E/2可得，P=eE/2e+Pp(1-Q)(e-1)g+1)(15)qe1E/2e+179数据与计算发展前沿，2 0 2 3，5（5）孙一帆等：本地化差分隐私综述SUE机制中,的频率估计值f，的近似方差Variu为:U:JSUEVar优化的一元编码(Optimized Unary Encod-ing,OUE)25,和UE机制一样将数据项转换为具有d个取值的向量，扰动后将向量发送至服务器端，解决了估计的方差依赖于d的大小的问题。UE中对二元向量中的1和0 的扰动概率可以不同，为了获得最小的估计方差，OUE机制中令11P=e+1OUE机制中，的频率估计值了，的近似方差Variu为:OUEVarf.lou(e-1)(2)基于哈希函数。为了解决取值空间比较大引起的通信开销高的问题，可应用哈希映射的方法把较大的原始取值空间映射到较小的取值空间，对哈希后的数据值进行扰动，可以降低用户和服务器的通信开销。基于哈希函数的典型机制随机可聚合保护隐私的有序响应(Randomized Aggregatable Priva-cy-Preserving Ordinal Response,RAPPOR)20,将随机响应机制与布隆过滤器结合使用,是一种典型的基于哈希函数的本地化差分隐私频率估计机制。设布隆过滤串B(也称比特串)的长度为l，哈希函数个数为h，即哈希函数集合H=(H,H2,H)。用户首先使用布隆过滤器将v;映射到B，可表示为：J1,if FHe H,s.t.,H(u.)=j,BO,otherwise然后使用随机响应机制对B的每一位比特进行扰动。扰动过程分为两步，分别为永久随机响应和瞬时随机响应。记永久随机响应的结果为B，B,在用户端被缓存，这样用户需要多次报告数据时，不用重复编码。永久随机响应的扰动过程如下：i=0.w.p-21,B.LiE/2(16)Jsun(e-1y4e(19)Bi,w.p.1-r其中，re0,1是用户可调节的参数,用户可以通过r控制隐私保护的程度。瞬时随机响应步骤，对B,再次进行随机响应得到B2，然后用户将B,发送给服务器端。瞬时随机响应的扰动过程如下：(20)q,if B,i=0服务器端的数据收集者需要统计收集到的B,中每一位出现1的次数并校准,其中第i位的估计值元；为：(17)n:-(p+f-fp)n(1-/)(q-p)然后结合可能取值的数据与布隆过滤串的映射关系矩阵，通过LASSO和线性回归的方法确定系数，即估计频数，可通过频数计算频率。RAPPOR机制中；的频率估计值于，的近似方差VarroJRAPPOR为：VaraDJRAPPORn(es/2-1针对数据收集者不能预知统计的数据项所有可能的值的情况,有学者提出了O-RAPPOR24和O-RR24的解决方案,进一步降低用户和服务器的通信开销，有更简化的编码方式。为了进一步降低通信开销，二元本地哈希法(Binary Local Hashing,BLH)25,基于哈希函数将(18)用户的数据u,映射到一个单一比特位,即y=H(u)，H 是从H中随机选取的哈希函数，然后将该比特进行随机响应。BLH扰动过程如下述公式所示。Pr(21)E/2eee+11,ify=oLe+1(22)(23)80数据与计算发展前沿，2 0 2 3，5（4）孙一帆等：本地化差分隐私综述1其中,p=-ee+1BLH机制中,的频率估计值，的近似方差Varl为:U:JBLHVaruJBLHn优化的本地哈希法(Optimized Local Hash-ing,OLH)25将用户数据v;映射到一个取值为g的空间,其中g2,不再和BLH一样使g=2，用以平衡信息损失。OLH的信息损失主要来自两个方面：编码阶段和扰动阶段。当g取值较大时，LDP频率估计机制在编码阶段可保留更多信息，但在扰动时会损失更多信息，因此在选择g时需要权衡两种操作之间的信息损失。通过对估计值近似方差求偏微分,OLH算法得到g的最优值为心+1，+2-2=g1+1OLH机制中,的频率估计值了，的近似方差Var.为:JOLHVar(3)基于矩阵变换。出于减小通信开销的考量,基于矩阵变换的机制，将用户数据编码从d比特位转换为1比特位。该类方法的不足是产生较大的信息损失，影响数据统计分析的可用性。基于转换方法的典型机制为 S-Hist27,该机制中服务器端根据Johnson-Lindenstrauss引理定义一个md的随机投影矩阵,其中m=og(2d/l),B0 且 是log(d+1)log(2/B)=En_2由服务器端定义的参数。随机投影矩阵中每1个元素可能取值的集合为,其中每NmVm个列向量内积为1,任意两个列向量的内积为0。用户将数据进行编码得到 Encode(u)=s,x，其中s是从 m中均匀随机选择的，是的第se+1行中对应的元素的值,可表示为=s,。对s的随机选择降低统计结果的可用性。然后对s,x中的x进行扰动，得到s,z，扰动过程如下：(24)2(e-1)其中c=+1e-1用户发送数据对s,z给服务器。服务器端接收到来自所有用户的sj,z(j=1,nl),S-Hist机制中对于ie的频率估计值于,，计算如下：(27)nS-Hist机制中,的频率估计值于，的近似方e14en(e-1)W.p.Z=+T1-c,mx,w.p.+1差Var,为:Var,哈达玛随机响应(Hadamard Randomized Re-sponse,HRR)343,适用于矩阵稀疏的情况。HRR(25)中哈达玛变换矩阵是正交且对称的，的大小为2 2 ,其中 i;=2-2(-1)，i j 为二进制表示的有关i和i的位点积。用户的数据，首先被编码为稀疏的二元向量B,，然后随机采样je2,对dB,=-1,1)进行扰动,以p的概率输出原来的值,以1-p的概率输出相反的值。用户通过和扰动后的B,计算哈达玛变换的系数Q,=B,将Q,和i发送给服务器。由服务器端对接收到的数据进行聚合和校准。当p=时,HRR机制中 2.的频率估计e+1值了,的近似方差Var为：4e（4)子集选择。先前介绍的基于本地化差分(26)(28)HRR(29)81数据与计算发展前沿，2 0 2 3，5（5)孙一帆等：本地化差分隐私综述隐私的机制大多考虑输出为单一的数据项的情况，而子集选择 2 9-3 1 考虑的是输出为数据项集合的情况。其中，子集选择的关键是选择K个数据项。输入数据值;ED(d=|D)，输出的数据项集合SeD且大小为k。子集选择k-subset的扰动扰动过程如下：PFslol=(he+d-h)cil1,if,s在k-subset机制的随机扰动过程中,需要对来自D-(e)的k或k-1个数据项随机采样，当k=1时，k-subset机制等价于GRR。当k=或=，时，频率估计方差最e+1e+1小。k-subset机制中,的频率估计值于，的最小方差Var,为：Var=e+d-2(e-1)表2 单属性单值数据的频率估计机制对比Table2Comparisons of frequency estimation mechanisms for single-value data in single attribute编码扰动方式方差BRRU70(1)直接扰动GRR124SUE25独热编码OUE251RAPPOR20基于哈希函数BLH(25先编码后扰动OLHI(25.3S-Hist(27基于矩阵变换HRR(34.35)子集选择h-subsetf29-311以上为基于本地化差分隐私的单属性单值数据的频率估计机制，表2 对上述机制从通信代价、渐近误差边界和方差等方面进行了对比分析。2.2单属性集值数据的频率估计Je,ifu;es,单属性集值数据，是针对一个属性包含多个d(30)(31)典型机制通信代价0(log.d)0(d)0(d)0(d)0(logd)0(logd)0(log m)0(logd)0(1)数据值，例如，近期浏览的网页、看过的电影和访问过的位置等。用户将数据发送给数据收集者后,数据收集者对数据进行聚合和校准，得到每一个数据值对应的频率。可形式化表示为，假设共有n个用户，用户集可表示为U=ui,u2,u)，一个属性 A对应d个数据值,属性域A=u,2,a)，每个用户j(1jn)发送数据集合S，其中l=|S(Old),在本地化差分隐私模型下估计,(1id)的频率于，用于统计分析。渐近误差边界EVndlogdEVnVloghEnlogdEndEVn/logdEnlogdEnlogdEVlogdEVnJdlogdEne+d-2n(e-1)e/2ne-14ene-1(e+1)n(e-14e(e-1ene-1y4ene-1e+d-2n(e-1)82数据与计算发展前沿，2 0 2 3，5（4）孙一帆等：本地化差分隐私综述表3 为集值数据集示例，包含了6 个用户的集值数据,其中属性域A=(1,2,3,4,5)。用户根据实际情况发送的数据集合不是定长的。表3 集值数据集示例Table 3Example of set-valued dataset用户集值数据u(1,3,4)u2(2,5)山(1,3,4,5)u4(3)us(1,2,3,4,5)按照数据统计分析任务分类，将单属性集值数据的频率估计机制分为两大类，分别为频繁项挖掘和频繁项集挖掘。接下来将对这两类任务的典型机制总结归纳。2.2.1频繁项挖掘频繁项挖掘，亦称HeavyHitters识别或者top-k挖掘，目的是发现频率高于给定阈值的数据项，例如找到频率大于15%的数据项。在表3中,top-3频繁项为1、3 和4。频繁项挖掘能够用于数据分析，在侧写用户画像、预测用户行为等方面提供很强的数据支持，帮助进一步提升电商、金融等行业的服务质量。频繁项挖掘面临的挑战包括两个方面：第一，隐私预算的分割将导致数据可用性急剧下降。对单属性集值数据进行频率估计,如果将单值数据的编码扰动机制重复应用在不同数据项上,将会导致随着隐私预算的分割,数据噪声增多,数据可用性降低。第二,异构的集合大小导致采样概率不均匀。不同用户的集值数据集合大小不是定长的，会导致数据项采样概率不均匀,难以获得准确的频率估计。频繁项挖掘解决异构集合问题的主要方法为裁剪填充。由数据收集者设置一个系统参数，m为指定集合大小,若lm，则对用户集合进行裁剪,使其大小等于m；若lm，则对用户集合进行填充，使其大小等于，填充信息为工，不计人频繁项的统计。用户从长度为m的集合中采样一个数据项进行报告，再采用满足本地化差分隐私的单值数据扰动机制。Qin等人 3 设计了LDPMiner机制,采取分割隐私预算的策略,第一阶段利用一部分隐私预算得到top-k频繁项候选集合，第二阶段应用剩余的隐私预算并结合填充采样和RAPPOR，修正候选集合后得到最终的频繁项。Wang等人 3 7 针对属性域大时计算复杂度高的问题，提出了前缀扩展方法PEM,将用户分成g组，每组的用户报告一个一定长度的前缀,且j+1组比j组的前缀长，第g组报告的前缀为整个字符串。数据收集者根据前缀迭代地去获得频繁项。Wang等人 3 8 提出了PrivSet机制，该机制中隐私预算不需要进行划分，因为集合数据整体被随机化为一个子集。Jia等人 2 2 设计Calibrate，通过先验知识建模噪声和数据项频率的概率分布，计算数据项频率的条件概率分布做为数据项频率估计的校准。朱美琪等人 3 9 提出了GFIM,利用运行过程分成两个阶段、用户分为两组的策略，两组用户的频繁项候选集合不同，用户设置九余项减少挖掘时计算的次数,提高频繁项挖掘效率。Zhao等人 4 0 利用灵活的分割方法将数据分成若干子域，利用交互的假阳率降低识别误差。现有工作在频繁项挖掘方向有了长足的进步，但是在如何降低通信开销，合理地设置隐私预算，使频繁项挖掘更准确、更高效方面，依然有待研究。2.2.2频繁项集挖掘频繁项集挖掘，是对于频繁项挖掘问题的扩展，在找到频繁项的基础上，挖掘发现频繁项集，使结果更适用于分析用户的行为模式。它的目的是找到频繁的数据项的集合。例如,在表3 中,top-2频繁项集为(3)，1)，(4)，(1,3)和(1,4)。假设总共有d个数据项,用户最多有1个数据项，那么频繁项集将有d种组合结果。随着属性域（0）的增长，频繁项集的组合数量呈指数增长，频繁项集挖掘难度大幅度增大。83数据与计算发展前沿，2 0 2 3，5（5）孙一帆等：本地化差分隐私综述在属性域空间很大的情况下,频繁项集的挖掘更有现实意义，也更有挑战。频繁项集挖掘面临的挑战是在属性域空间很大时,如何选择高效的数据的编码扰动方式使通信开销变小以及如何减小候选集的大小。Wang等人 3 7 提出了SVSM方法，利用用户分组和自适应频率估计机制，优化频繁项集挖掘。当数据项长度de(4l-1)+1时，选择GRR机制,否则选择OLH机制,根据频繁项的猜测频率去减小候选集的大小。Ma等人 4 采用了Hadamard响应算法进行编码扰动,用于降低通信代价，并且将应用FP-tree方法用于频繁项集挖掘。Afrose等人 4 2 提出了Priv_OA,应用了两级的随机化技术进行数据处理，除此之外，还考虑了数据项之间的关联性。Chen等人(4 3 提出了基于频繁模式树的LDP-FPMiner,根据数据项集频率关联性构建、优化噪声FP-tre。K o n g 等人(对属性进行分层操作获取每层的频繁项集，提高了搜索的效率,再根据用户剪枝的思想进行迭代,得到最终的频繁项集。Chen等人 4 5 提出Fed-FIM联邦学习架构,用于频繁项集的挖掘。未来在减小通信、计算开销的同时去优化候选集仍值得重点关注。综上，按照数据分析任务类型进行划分，单属性集值数据的频率估计机制分为两大类，分别为频繁项挖掘和频繁项集挖掘。表4 对上述机制从关键技术、优点、缺点等