差分隐私保护及其应用

第３７卷第１期　计　算　机　学　报　ＶｏＬ　３７　Ｎｏ．１　２０１４年１月　ＯＦ　ＣＯＭＰＵＴＥＲＳ　ＣＨＩＮＥＳＥ　ＪＯＵＲＮＡＬ　Ｊａｎ．２０１４　差分隐私保护及其应用　熊　平”　朱天清　王晓峰”　４３００７３）　”（中南财经政法大学信息与安全工程学院　武汉（澳大利亚迪肯大学信息技术学院　墨尔本澳大利亚　３１２５）　”（中国科学院计算技术研究所无线传感网络实验室（武汉轻工大学数学与计算机学院　武汉北京　１００１９０）　４３００２３）　摘　要数据发布与数据挖掘中的隐私保护问题是目前信息安全领域的一个研究热点．作为一种严格的和可证明　的隐私定义，差分隐私近年来受到了极大关注并被广泛研究．文中分析了差分隐私保护模型相对于传统安全模型　的优势，对差分隐私基础理论及其在数据发布与数据挖掘中的应用研究进行综述．在数据发布方面，介绍了各种交　互式和非交互式的差分隐私保护发布方法，并着重从精确度和样本复杂度的角度对这些方法进行了比较．在数据　挖掘方面，阐述了差分隐私保护数据挖掘算法在接口模式和完全访问模式下的实现方式，并对这些算法的执行性　能进行了分析．最后，介绍了差分隐私保护在其它领域的应用，并展望未来的研究方向．　关键词　差分隐私；数据发布；数据挖掘；机器学习；统计查询；隐私保护　中图法分类号ＴＰ３９１　ＤＯＩ号１０．３７２４／ＳＰ．Ｊ．１０１６．２０１４．００１０１　Ａ　Ｓｕｒｖｅｙ　ｏｎ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｐｒｉｖａｃｙ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　ＸＩＯＮＧ　Ｐｉｎｇ　’　ＺＨＵ　Ｔｉａｎ—Ｑｉｎｇ　，　ＷＡＮＧ　Ｘｉａｏ—Ｆｅｎｇ。　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｓｅｃｕｒｉｔｙ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｚｈｏｎｇｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｃｏｎｏｍｉｃｓ　ａｎｄ　Ｌａｗ，Ｗｕｈａｎ　４３００７３）　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｄｅａｋｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｍｅｌｂｏｕｒｎｅ　３１２５，Ａｕｓｔｒａｌｉａ）　”（Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋ　Ｌａｂｏｒａｔｏｒｙ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１００１９０）　”（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｗｕｈａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００２３）　Ａｂｓｔｒａｃｔ　Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｉｎ　ｄａｔａ　ｒｅｌｅａｓｅ　ａｎｄ　ｍｉｎｉｎｇ　ｉｓ　ａ　ｈｏｔ　ｔｏｐｉｃ　ｉｎ　ｔｈｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ　ｆｉｅｌｄ　ｃｕｒｒｅｎｔｌｙ．Ａｓ　ａ　ｎｅｗ　ｐｒｉｖａｃｙ　ｎｏｔｉｏｎ，ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ（ＤＰ）ｈａｓ　ｇｒｏｗｎ　ｉｎ　ｐｏｐｕｌａｒｉｔｙ　ｒｅｃｅｎｔｌｙ　ｄｕｅ　ｔｏ　ｉｔｓ　ｒｉｇｉｄ　ａｎｄ　ｐｒｏｖａｂｌｅ　ｐｒｉｖａｃｙ　ｇｕａｒａｎｔｅｅ．Ａｆｔｅｒ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ａｄｖａｎｔａｇｅ　ｏｆ　ｄｉｆｆｅｒ—　ｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｍｏｄｅｌ　ｒｅｌａｔｉｖｅ　ｔｏ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｏｎｅｓ，ｔｈｉｓ　ｐａｐｅｒ　ｓｕｒｖｅｙｓ　ｔｈｅ　ｔｈｅｏｒｙ　ｏｆ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｏｎ　ｔｗｏ　ａｓｐｅｃｔｓ，ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｒｅｌｅａｓｅ（ＰＰＤＲ）ａｎｄ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ（ＰＰＤＭ）．Ｉｎ　ＰＰＤＲ，ｗｅ　ｉｎｔｒｏｄｕｃｅ　ｔｈｅ　ＤＰ—ｂａｓｅｄ　ｄａｔａ　ｒｅｌｅａｓｅ　ｍｅｔｈｏｄｏｌｏ－　ｇｉｅｓ　ｉｎ　ｉｎｔｅｒａｃｔｉｖｅ／ｎｏｎ－ｉｎｔｅｒａｃｔｉｖｅ　ｓｅｔｔｉｎｇｓ　ａｎｄ　ｃｏｍｐａｒｅ　ｔｈｅｍ　ｉｎ　ｔｅｒｍｓ　ｏｆ　ａｃｃｕｒａｃｙ　ａｎｄ　ｓａｍｐｌｅ　ｃｏｍｐｌｅｘｉｔｙ．Ｉｎ　ＰＰＤＭ，ｗｅ　ｍａｉｎｌｙ　ｓｕｍｍａｒｉｚｅ　ｔｈｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ＤＰ　ｉｎ　ｖａｒｉｏｕｓ　ｄａｔａ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｗｉｔｈ　ｉｎｔｅｒｆａｃｅ——ｂａｓｅｄ／ｆｕｌｌｙ　ａｃｃｅｓｓ——ｂａｓｅｄ　ｍｏｄｅｓ　ａｓ　ｗｅｌｌ　３Ｓ　ｅｖａｌｕａｔｉｎｇ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ．Ｗｅ　ｆｉｎａｌｌｙ　ｒｅｖｉｅｗ　ｏｔｈｅｒ　ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　ＤＰ　ｉｎ　ｖａｒｉｏｕｓ　ｆｉｅｌｄｓ　ａｎｄ　ｄｉｓｃｕｓｓ　ｔｈｅ　ｆｕｔｕｒｅ　ｒｅｓｅａｒｃｈ　ｄｉｒｅｃｔｉｏｎｓ．　Ｋｅｙｗｏｒｄｓ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ；ｄａｔａ　ｒｅｌｅａｓｅ；ｄａｔａ　ｍｉｎｉｎｇ；ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ；ｓｔａｔｉｓｔｉｃａｌ　ｑｕｅｒｙ；　ｐｍｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　收稿日期：２０１３—０４—１６；最终修改稿收到日期：２０１３—１１－２Ｏ．本课题得到国家自然科学基金（６１２０２２１１，６１３０４０６７）、教育部人文社科研究青　年基金（１２ＹＪＣ６３ＯＯ７８）、中央高校基本科研业务费专项资金（３１５４１３１１３０２，３１５４１１１１３０５）资助．熊　平，男，１９７４年生，博士，副教授，主　要研究方向为信息安全、机器学习、数据挖掘．Ｅ—ｍａｉｌ：ｐｉｎｇｘｉｏｎｇ＠ｚｎｕｆｅ．ｅｄｕ．ｃｎ．朱天清，女，１９７９年生，博士研究生，讲师，主要研究方　向为隐私保护与网络安全．王晓峰，男，１９７８年生，博士，助理研究员，主要研究方向为人工智能、数据挖掘、无线传感网络．　１Ｏ２　计　算　机　学　报　引　言　随着信息技术应用的不断普及和深入，各种信　息系统存储并积累了丰富的数据，例如医疗机构建　立的患者诊断数据集，电子商务企业收集的客户在　线交易数据集等．对这些数据集进行分析可以使人　们获得更多关于真实世：界的知识．因此，对于研究机　构、信息咨询组织以及政府决策部门来说，数据是非　常重要的基础资源．这种需求极大地促进了数据的　发布、共享与分析．　然而，数据集里通常包含着许多个人的隐私信　息，如医疗诊断结果、个人消费习惯以及其它能够体　现个人特征的数据，这些信息会随着数据集的发布　和共享而被泄露．虽然删除数据集的标识符属性（如　姓名、ＩＤ号等）能够在一定程度上保护个人隐私，但　一些攻击案例口　表明，这种简单的操作远不足以保　证隐私信息的安全．　数据的隐私保护问题最早由统计学家Ｄａｌｅｎｉｕｓ　在２Ｏ世纪７０年代末提出．他认为，保护数据库中的　隐私信息，就是要使任何用户（包括合法用户和潜在　的攻击者）在访问数据库的过程中无法获取关于任　意个体的确切信息　ｊ．虽然这一定义具有理论上的　指导意义，但显然它是主观的和模糊的．以这一定义　为目标，学者们在后续的研究中提出了许多量化指　标更明确、可操作性强的隐私保护模型和方法．　从已有的研究来看，ｋ—ａｎｏｎｙｍｉｔｙｌ６　及其扩展模　型在隐私保护领域影响深远且被广泛研究．这些模　型的基本思想是将数据集里与攻击者背景知识相关　的属性定义为准标识符。通过对记录的准标识符值　进行泛化、压缩处理，使得所有记录被划分到若干个　等价类（Ｅｑｕｉｖａｌｅｎｃｅ　Ｇｒｏｕｐ），每个等价类中的记录　具有相同的准标识符值．从而实现将一个记录隐藏　在一组记录中．因此，这类模型也被称为基于分组的　隐私保护模型．　然而后续研究表明，这些模型存在两个主要缺　陷．其一，这些模型并不能提供足够的安全保障，它　们总是因新型攻击的出现而需要不断完善．例如为　了抵制“一致性”攻击，ｚ—ｄｉｖｅｒｓｉｔｙ＿７］、ｔ—ｃｌｏｓｅｎｅｓｓｌ８］、　（ａ，ｋ）一ａｎｏｎｙｍｉｔｙＥｇ］、Ｍ—ｉｎｖａｒｉａｎｃｅ＿１。。等模型相继被　提出；文献［１１］提出了７　—ｃｏｎｆｉｄｅｎｔｉａｌｉｔｙ模型以抵　制“最小性”攻击．许多新型的攻击方式都对基于分　组的隐私保护模型形成了挑战，例如“合成式”攻　击　］、“前景知识”攻击¨１　、“ｄｅＦｉｎｅｔｔｉ”攻击口　等．　出现这一局面的根本原因在于，基于分组的隐私保　护模型的安全性与攻击者所掌握的背景知识相关，　而所有可能的背景知识很难被充分定义．所以，一个　与背景知识无关的隐私保护模型才町能抵抗任何新　型的攻击．第二个缺陷是这些早期的隐私保护模型　无法提供一种有效且严格的方法来证明其隐私保护　水平，因此当模型参数改变时，无法对隐私保护水平　进行定量分析．这个缺点削弱了隐私保护处理结果　的可靠性．因此，研究人员试图寻求一种新的、鲁棒　性足够好的隐私保护模型，能够在攻击者拥有最大　背景知识的条件下抵抗各种形式的攻击．差分隐私　（Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｐｒｉｖａｃｙ，ＤＰ）ｌ１　的提出使得实现这种　设想成为可能．　差分隐私是Ｄｗｏｒｋ在２００６年针对统计数据库　的隐私泄露问题提出的一种新的隐私定义［１　．在此　定义下，对数据集的计算处理结果对于具体某个记　录的变化是不敏感的，单个记录在数据集中或者不　在数据集中，对计算结果的影响微乎其微．所以，一　个记录因其加入到数据集中所产生的隐私泄露风险　被控制在极小的、可接受的范围内，攻击者无法通过　观察计算结果而获取准确的个体信息．　差分隐私能够解决传统隐私保护模型的两个缺　陷．首先，差分隐私保护模型假设攻击者能够获得除　目标记录外所有其它记录的信息，这些信息的总和　可以理解为攻击者所能掌握的最大背景知识．在这　一最大背景知识假设下，差分隐私保护无需考虑攻　击者所拥有的任何可能的背景知识，因为这些背景　知识不可能提供比最大背景知识更丰富的信息．其　次，它建立在坚实的数学基础之上，对隐私保护进行　了严格的定义并提供了量化评估方法，使得不同参　数处理下的数据集所提供的隐私保护水平具有可比　较性．因此，差分隐私理论迅速被业界认可，并逐渐　成为隐私保护领域的一个研究热点．近几年来，差分　隐私和其它领域研究的结合使得大量新的成果不断　涌现．本文在总结已有研究成果的基础上，对差分隐　私的理论发展及其在数据发布与数据挖掘领域的应　用进行综述．　本文第２节介绍差分隐私保护模型的相关定义　与基础理论；第３节介绍差分隐私保护数据发布在　交互式和非交互式环境下的实现方法，并对这些方　法进行分析和比较；第４节阐述差分隐私保护数据　挖掘在接口模式和完全访问模式上的差异，并着重　介绍差分隐私保护在各种挖掘算法中的实现；第５　节简介差分隐私保护在其它领域的应用；最后在第　１期　熊平等：差分隐私保护及其应用　１０３　６节讨论差分隐私保护研究所面临的挑战和未来的　发展方向．　Ｐｒ［Ｍ（Ｄ）Ｅ　ＳＭ］　ｅｘｐ（￡）×Ｐｒ［Ｍ（Ｄ　）Ｅ　ＳＭ］（１）　则称算法Ｍ提供ｅ一差分隐私保护，其中参数ｅ称为　隐私保护预算＿ｌ引．　如图ｌ所示，算法Ｍ通过对输出结果的随机化　２差分隐私保护模型　差分隐私保护模型的思想源自于一个很朴素的　观察：当数据集Ｄ中包含个体Ａｌｉｃｅ时，设对Ｄ进　行任意查询操作，（例如计数、求和、平均值、中位数　或其它范围查询等）所得到的结果为厂（Ｄ），如果将　来提供隐私保护，同时通过参数ｅ来保证在数据集　中删除任一记录时，算法输出同一结果的概率不发　生显著变化．　Ａｌｉｃｅ的信息从Ｄ中删除后进行查询得到的结果仍　然为ｆ（Ｄ），则可以认为，Ａｌｉｃｅ的信息并没有因为　被包含在数据集Ｄ中而产生额外的风险．差分隐私　保护就是要保证任一个体在数据集中或者不在数据　集中时，对最终发布的查询结果几乎没有影响．具体　地说，设有两个几乎完全相同的数据集（两者的区别　仅在于一个记录不同），分别对这两个数据集进行查　询访问，同一查询在两个数据集上产生同一结果的　概率的比值接近于１．　差分隐私保护模型最初被应用在统计数据库安　全领域，旨在发布统计信息时保护数据库中个体的　隐私信息，之后被广泛应用于隐私保护数据发布　（Ｐｒｉｖａｃｙ　Ｐｒｅｓｅｒｖｉｎｇ　Ｄａｔａ　Ｒｅｌｅａｓｅ，ＰＰＤＲ）与隐私　保护数据挖掘（Ｐｒｉｖａｃｙ　Ｐｒｅｓｅｒｖｉｎｇ　Ｄａｔａ　Ｍｉｎｉｎｇ，　ＰＰＤＭ）等领域．已有的研究表明，差分隐私保护方　法既可以应用于交互式的统计查询，也可以应用在　各种非交互式的信息发布场合．　２．１　差分隐私的定义与相关概念　２．１．１基本定义　对于一个有限域Ｚ，　ＥＺ为Ｚ中的元素，从ｚ　中抽样所得　的集合组成数据集Ｄ，其样本量为ｎ，　属性的个数为维度ｄ．　对数据集Ｄ的各种映射函数被定义为查询　（Ｑｕｅｒｙ），用Ｆ一｛ｆ　，＿厂２，…｝来表示一组查询，算法　Ｍ对查询Ｆ的结果进行处理，使之满足隐私保护的　条件，此过程称为隐私保护机制．　设数据集Ｄ和Ｄ　，具有相同的属性结构，两者　的对称差记作Ｄ△Ｄ　，ｌ　ＤＡＤ　ｉ表示Ｄ△Ｄ　中记录的　数量．若ｌ　Ｄ△Ｄ　ｌ一１，则称Ｄ和Ｄ　为邻近数据集　（Ａｄｊａｃｅｎｔ　Ｄａｔａｓｅｔ）．　定义１＿】　．　差分隐私．设有随机算法Ｍ，ＰＭ　为Ｍ所有可能的输出构成的集合．对于任意两个邻　近数据集Ｄ和Ｄ　以及ＰＭ的任何子集ＳＭ，若算法　Ｍ满足　，（Ｄ），（Ｄ　）　输出值　图１　随机算法在邻近数据集上的输出概率　例如，表１显示了一个医疗数据集Ｄ，其中的每　个记录表示某个人是否患有癌症（１表示是，０表示　否）．数据集为用户提供统计查询服务（例如计数查　询），但不能泄露具体记录的值．设用户输入参数ｉ，　调用查询函数．厂（　）一ｃｏｕｎｔ（　）来得到数据集前ｉ行　中满足“诊断结果”一１的记录数量，并将函数值反　馈给用户．假设攻击者欲推测Ａｌｉｃｅ是否患有癌症，　并且知道Ａｌｉｃｅ在数据集的第５行，那么可以用　ｃｏｕｎｔ（５）一ｃｏｕｎｔ（４）来推出正确的结果．　表１医疗数据集示例　姓名　诊断结果　Ｔｏｍ　Ｊａｃｋ　Ｈｅｎｒｙ　Ｄｉｅｇｏ　Ａｌｉｃｅ　但是，如果，是一个提供ｅ一差分隐私保护的查　询函数，例如厂（　）＝＝＝ｃｏｕｎｔ（　）＋ｎｏｉｓｅ，其中ｎｏｉｓｅ是　服从某种随机分布的噪声．假设厂（５）可能的输出来　自集合｛２，２．５，３｝，那么，厂（４）也将以几乎完全相同　的概率输出｛２，２．５，３）中的任一可能的值，因此攻击　者无法通过厂（５）一，（４）来得到想要的结果．这种针　对统计输出的随机化方式使得攻击者无法得到查询　结果间的差异，从而能保证数据集中每个个体的　安全．　２．１．２相关概念　（１）隐私保护预算　从定义１可以看出，隐私保护预算ｅ用来控制　算法Ｍ在两个邻近数据集上获得相同输出的概率　１０４　计　算　机　学　报　比值，它事实上体现了Ｍ所能够提供的隐私保护水　平．在实际应用中，ｓ通常取很小的值，例如０．Ｏ１，　０．１，或者ｌｎ２，ｌｎ３等　越小，表示隐私保护水平越　高．当ｅ等于０时，保护水平达到最高，此时对于任　意邻近数据集，算法都将输出两个概率分布完全相　同的结果，这些结果也不能反映任何关于数据集的　有用的信息．因此，ｅ的取值要结合具体需求来达到　输出结果的安全性与可用性的平衡．　（２）敏感度　差分隐私保护可以通过在查询函数的返回值中　加入适量的干扰噪声来实现．加入噪声过多会影响　结果的可用性，过少则无法提供足够的安全保障．敏　感度是决定加入噪声量大小的关键参数，它指删除　数据集中任一记录对查询结果造成的最大改变．　在差分隐私保护方法中定义了两种敏感度，即全局　敏感度（Ｇｌｏｂａｌ　Ｓｅｎｓｉｔｉｖｉｔｙ）和局部敏感度（Ｌｏｃａｌ　Ｓｅｎｓｉｔｉｖｉｔｙ）．　定义２ｌ１引．　全局敏感度．设有函数．厂：Ｄ—Ｒ　，　输入为一数据集，输出为一ｄ维实数向量．对于任　意的邻近数据集Ｄ和Ｄ　，　ＧＳ／一ｍａｘ　Ｉｌ厂（Ｄ）－－ｆ（Ｄ　）ｌ　＿（２）　Ｄ，Ｄ　称为函数／’的全局敏感度．　其中，【ｌ　（Ｄ）一　（Ｄ，）ｌｌ　是厂（Ｄ）和ｆ（Ｄ　）之间　的１一阶范数距离．　函数的全局敏感度由函数本身决定，不同的函　数会有不同的全局敏感度．一些函数具有较小的全　局敏感度（例如计数函数，其全局敏感度为１），因此　只需加人少量噪声即可掩盖因一个记录被删除对查　询结果所产生的影响，实现差分隐私保护．但对于某　些函数而言，例如求平均值、求中位数等函数，则往　往具有较大的全局敏感度．以求中位数函数为例，设　函数为厂（Ｄ）一ｍｅｄｉａｎ（ｚ１，ｚ２，…，ｚ　），其中Ｘ　（ｉ一　１，…，　）是区间［ｎ，６］中的一个实数．不妨设／－／为奇　数，且数据已被排序，那么函数的返回值即为第　ｍ一（　４－１）／２个数．在某种极端的情况下，设ｚ　一　２一…一ｚ　一＆且ｚ　＿－１一ｚ　＋２一…一３５　一ｂ，那么　从中删除一个数就可能使函数的返回值由ａ变为　ｂ，因此函数的全局敏感度为ｂ—ａ，这可能是一个很　大的值．　当全局敏感度较大时，必须在函数输出中添加　足够大的噪声才能保证隐私安全，导致数据可用性　较差．针对这个问题，Ｎｉｓｓｉｍ等人定义了局部敏感　度以及与其计算相关的其它概念．　定义３＿１引．　局部敏感度．设有函数．，：Ｄ一　，　输入为数据集Ｄ，输出为一ｄ维实数向量．对于给定　数据集Ｄ和它的任意邻近数据集Ｄ　，则　ＬＳ，（Ｄ）一ｍａｘ　ｌ　Ｊ－厂（Ｄ）一ｆ（Ｄ　）ｌ　Ｉ（３）　Ｄ　称为函数厂在Ｄ上的局部敏感度．　局部敏感度由函数厂及给定数据集Ｄ中的具体　数据共同决定．由于利用了数据集的数据分布特征，　局部敏感度通常要比全局敏感度小得多．以前文的求　中位数函数为例，其局部敏感度为ｍａｘ（　一．２Ｃ　一　，　２１２　＋　～ｚ　）．另外，局部敏感度与全局敏感度之间的　关系可以表示为　ＧＳ，一ｍａｘ（ＬＳ，（Ｄ））　（４）　Ｄ　但是，由于局部敏感度在一定程度上体现了数　据集的数据分布特征，如果直接应用局部敏感度来　计算噪声量则会泄露数据集中的敏感信息．因此，局　部敏感度的平滑上界（Ｓｍｏｏｔｈ　Ｕｐｐｅｒ　Ｂｏｕｎｄ）被用　来与局部敏感度一起确定噪声量的大小．　定义４［１。Ｉ．　平滑上界．给定数据集Ｄ及其任　意邻近数据集Ｄ　，函数／　的局部敏感度为ＬＳ，（Ｄ）．　对于ｆｉ＞０，若函数ｓ：Ｄ—Ｒ满足Ｓ（Ｄ）三三＝ＬＳ，（Ｄ）且　Ｓ（Ｄ）　ｅＰＳ（Ｄ　），则称Ｓ为函数＿厂的局部敏感度的　平滑上界．　所有满足这一定义的函数都可被定义为平滑上　界，将局部敏感度代人此函数中则可得到平滑敏感　度（Ｓｍｏｏｔｈ　Ｓｅｎｓｉｔｉｖｉｔｙ），进而用于计算噪声大小．　平滑上界与局部敏感度的关系如图２所示．Ｎｉｓｓｉｍ　在文中给出了一个平滑上界的例子，并以此生成了　平滑敏感度．　图２局部敏感度的平滑上界　定义５ｌ】　．　平滑敏感度．给定数据集Ｄ及Ｄ　，　函数Ｓ＾口（Ｄ）一ｍａｘ（ＬＳ，（Ｄ　）×ｅ－ｐ｛　）称为函数　Ｄ　－厂的　一平滑敏感度，其中ｆｌ＞０．　由于绝大部分关于差分隐私保护的研究均针对　计数查询、求和查询等敏感度较小的函数，因此，若　无特殊说明，本文中敏感度均指全局敏感度．　２．２差分隐私保护算法的组合性质　一个复杂的隐私保护问题通常需要多次应用差　１期　熊平等：差分隐私保护及其应用　１０５　分隐私保护算法才能得以解决．在这种情况下，为了　保证整个过程的隐私保护水平控制在给定的预算ｅ　之内，需要合理地将全部预算分配到整个算法的各　个步骤中．这时可以利用隐私保护算法的两个组合　查响查响　性质，如图３所示．　询应询应　１　ｌ　２　２　（　（　￡　￡　）　）　查询１　响应１（￡　）　查询２　响应２（￡，）　（ａ）∑Ｅ　一差分隐私　（ｂ）ｍａｘ（￡　）一差分隐私　图３差分隐私保护算法的组合性质　性质１ｌ２　．　设有算法Ｍ　，Ｍ　，…，Ｍ　，其隐私　孽　保护预算分别为￡　，　，…，　，那么对于同一数据　集Ｄ，由这些算法构成的组合算法Ｍ（Ｍ　（Ｄ），　Ｍ２（Ｄ），…，　（Ｄ））提供（’∑ｅ　）一差分隐私保护．　该性质表明，一个差分隐私保护算法序列构成　的组合算法，其提供的隐私保护水平为全部预算的　总和．该性质也称为“序列组合性”．　性质２［２　．　设有算法Ｍ　，Ｍ２，…，　，其隐私　保护预算分别为ｅ　，ｅ　，…，ｅ　，那么对于不相交的数　据集Ｄ　，Ｄ。，…，Ｄ　，由这些算法构成的组合算法　Ｍ（Ｍｌ（Ｄ１），Ｍ２（Ｄ２），…，Ｍ　（Ｄ　））提供（ｍａｘ￡　）一　差分隐私保护．　该性质表明，如果一个差分隐私保护算法序列　中所有算法处理的数据集彼此不相交，那么该算法　序列构成的组合算法提供的隐私保护水平取决于算　法序列中的保护水平最差者，即预算最大者．该性质　也称为“并行组合性”．　２．３实现机制　在实践中为了使一个算法满足差分隐私保护的　要求，对不同的问题有不同的实现方法，这些实现方法　称为“机制”．Ｌａｐｌａｃｅ机制＿２　（Ｌａｐｌａｃｅ　Ｍｅｃｈａｎｉｓｍ）　与指数机制　。　（Ｅｘｐｏｎｅｎｔｉａｌ　Ｍｅｃｈａｎｉｓｍ）是两种最　基础的差分隐私保护实现机制．其中，Ｌａｐｌａｃｅ机制　适用于对数值型结果的保护，指数机制则适用于非　数值型结果．　２．３．１　Ｌａｐｌａｃｅ机制　Ｌａｐｌａｃｅ机制通过向确切的查询结果中加入服　从Ｌａｐｌａｃｅ分布的随机噪声来实现ｅ一差分隐私保　护．记位置参数为０、尺度参数为ｂ的Ｌａｐｌａｃｅ分布　为Ｌａｐ（ｂ），那么其概率密度函数为　ｐ（ｘ）＝１ｅｘｐ（一　）　（５）　定义６［　．Ｌａｐｌａｃｅ机制．给定数据集Ｄ，设　有函数－厂：Ｄ—Ｒ　，其敏感度为ａｆ，那么随机算法　Ｍ（Ｄ）一厂（Ｄ）＋ｙ提供￡一差分隐私保护，其中ｙ～　Ｌａｐ（Ａｆ／ｅ）为随机噪声，服从尺度参数为ａｆ／ｅ的　Ｌａｐｌａｃｅ分布．　从不同参数的Ｌａｐｌａｃｅ分布（如图４）可以看出，　￡越小，引入的噪声越大．　图４　Ｌａｐｌａｃｅ概率密度函数　２．３．２指数机制　由于Ｌａｐｌａｃｅ机制仅适用于数值型查询结果，　而在许多实际应用中，查询结果为实体对象（例如一　种方案或一种选择）．对此，ＭｃＳｈｅｒｒｙ等人提出了指　数机制．　设查询函数的输出域为Ｒａｎｇｅ，域中的每个　值ｒｆｆＲａｎｇｅ为一实体对象．在指数机制下，函数　ｑ（Ｄ，ｒ）一Ｒ称为输出值ｒ的可用性函数，用来评估　输出值ｒ的优劣程度．　定义７＿２　．　指数机制．设随机算法Ｍ输入为　数据集Ｄ，输出为一实体对象ｒＥＲａｎｇｅ，ｑ（Ｄ，ｒ）为　可用性函数，Ａｑ为函数ｑ（Ｄ，ｒ）的敏感度．若算法Ｍ　以正比于　ｘｐ（　、△ｑ　）的概率从Ｒ。　ｇ　中选择并　输出ｒ，那么算法Ｍ提供￡一差分隐私保护．　以下是一个指数机制的应用实例．假如拟举办　一场体育比赛，可供选择的项目来自集合｛足球，排　中确定一个项目，并保证整个决策过程满足ｅ一差分　隐私保护要求．以得票数量为可用性函数，显然　△ｑ一１．那么按照指数机制，在给定的隐私保护预算ｅ　下，可以计算出各种项目的输出概率，如表２所示．　表２指数机制应用示例　项目　—　｝—　球，篮球，网球），参与者们为此进行了投票，现要从　１Ｏ６　计　算　机　学　报　可以看出，在￡较大时（如ｅ一１），可用性最好的　选项被输出的概率被放大．当ｅ较小时，各选项在可　用性上的差异则被平抑，其被输出的概率也随着ｅ　的减小而趋于相等．　２．４主要研究方向　由于理论上的可证明性和应用上的通用性，差　分隐私保护方法得到了业内学者们的认可．近年来　的一系列研究　。。。使其在理论上不断成熟．目前差　分隐私保护的理论与应用研究主要集中在两个方　向，即隐私保护数据发布与隐私保护数据挖掘．　２．４．１　隐私保护数据发布　隐私保护数据发布研究的问题是如何在满足差　分隐私的条件下保证发布数据或查询结果的精确　性，研究内容主要集中在发布机制和算法复杂度的　调整上，研究方法主要是基于计算理论和学习理论　的定量分析．　差分隐私保护数据发布根据实现环境不同可分　为两种，即交互式数据发布和非交互式数据发　布ｌ２　，如图５所示．　曰一０　查查询２１ｉ　原始数据集　隐私保护信任边界有限个查询　（ａ）交互式数据发布　日一　国…据集　黧篥的　原始数据集　隐私保护信任边界　（ｂ）非交互式数据发布　图５　ＰＰＩ）Ｒ的实现环境　在交互式环境下，用户向数据管理者提出查询　请求，数据管理者根据查询请求对数据集进行操作　并将结果进行必要的干扰后反馈给用户，用户不能　看到数据集全貌，从而保护数据集中的个体隐私．　在非交互式环境下，数据管理者针对所有可能　的查询，在满足差分隐私的条件下一次性发布所有　查询的结果．或者，数据管理者发布一个原始数据集　的“净化”版本，这是一个不精确的数据集，用户可对　该版本的数据集自行进行所需的查询操作．　２．４．２隐私保护数据挖掘　隐私保护数据挖掘研究的问题是如何在保证数　据集隐私安全的前提下获取性能最优的数据挖掘模　型．其研究通常面向数据挖掘领域的具体算法，通过　对已有算法的调整和对挖掘结果的性能评估，来寻　求数据安全性和模型可用性的平衡．　差分隐私保护数据挖掘有两种实现模式，即接　口（Ｉｎｔｅｒｆａｃｅ）模式和完全访问（Ｆｕｌｌｙ　Ａｃｃｅｓｓ）模　式　ｎ】，如图６所示．　原始数据集　曰一０＋　—　信任边界数据挖掘　模型　（ａ）接口模式　曰一镪＋　原始数据集　数据挖掘　信任边界　模型　（ｂ）完全访问模式　图６　ＰＰＤＭ的实现模式　在接口模式下，数据挖掘者被视为不可信的．数　据管理者不会发布原始数据集，而只是对外提供访　问接口，并在接口上实施差分隐私保护．数据挖掘者　只能通过接口获取进行数据挖掘所需的统计类信　息，其查询数目受隐私保护预算的限制．在这种模式　下，隐私保护的功能完全由接口来提供，数据挖掘者　无需关心任何隐私保护需求，也无需掌握任何有关　隐私保护的知识，其进行数据挖掘所采用的各种算　法也无需因隐私保护做任何修改．　在完全访问模式下，数据挖掘者被认为是可信　的，能够直接访问数据集并执行挖掘算法．但他们必　须具备隐私保护的领域知识以对传统的数据挖掘算　法进行必要的修改，使得这些算法能够满足差分隐　私保护的要求，从而保证最终发布的模型不会泄露　数据集中的隐私信息．完全访问模式对查询数量没　有限制，因此数据挖掘者在设计算法时具有更大的　灵活性．　３基于差分隐私保护的数据发布　基于差分隐私保护的数据发布是差分隐私研究　中的核心内容．本节针对交互式和非交互式两种不　同的实现环境，介绍差分隐私在数据发布中的应用　方法．　３．１交互式数据发布　交互式数据发布问题可表述为：给定数据集Ｄ　和查询集合Ｆ，需寻求一种数据发布机制，使其能够　在满足差分隐私保护的条件下逐个回答Ｆ中的查　询，直到耗尽全部隐私保护预算．发布机制的性能通　常由精确度来衡量．交互式数据发布即是要在满足　一定精确度的条件下，以给定的隐私保护预算回答　尽可能多的查询．　对于Ｆ中任意查询厂，设定一个足够小的实数　１期　熊　平等：差分隐私保护及其应用　１０７　＜１，查询结果的精确度ａ应满足　Ｐｒ，∈Ｆｌ　ｌ厂（Ｄ）一Ｍ（厂（Ｄ））【三三ａ　ｌ三三１一　（６）　能够在给定的隐私保护预算下，回答更多的查询．具　体方式为，ＰＭＷ把数据集在数据域上的分布视作　一其中－厂（Ｄ）为查询厂在Ｄ上的结果，Ｍ（－厂（Ｄ））为随　机算法Ｍ对ｆ（Ｄ）的干扰结果．　越小，精确度越　高　。　．　个直方图，首先将每个频数设为相同，然后等待查　询，每个查询的结果加上Ｌａｐｌａｃｅ噪声后会和上一　次查询结果相比较，若差异小于设定的阈值，则发布　为了达到这个精确度所需的样本量为样本复杂　上一次查询结果的值，此步骤不耗费隐私保护预算．　只有当差异大于此阈值时，才会发布新的查询结果，　并调整直方图中相应频数的值．由于很多查询并不　耗费隐私保护预算，所以这个机制能比普通Ｌａｐｌａｃｅ　度．精确度与样本复杂度之间的关系有两种不同的　表达方式．（１）给定样本量ｎ，则发布机制的精确度　为ａ（　），当ｎ一。。时，ａ（ｎ）趋于０；（２）给定ａ，达到这　一精确度所需的样本量为ｎ。（ａ），则发布机制在　，ｚ三三＝ｎ。（ａ）时保证了精确度ａ，其中当ａ一０时ｎ。（　）　趋于无穷大．交互式数据发布采用精确度和相应的　样本复杂度来评估发布机制的性能．　交互式隐私保护数据发布的研究主要集中在发　布机制和基于直方图的发布方法上．两者的区别在　于，前者直接对数据集进行操作来响应查询，而后者　先根据数据集建立直方图分布，然后根据直方图分　布来响应查询．　３．１．１　交互式发布机制研究　最早用于交互式数据发布的差分隐私保护机制　是Ｄｗｏｒｋ等人提出的Ｌａｐｌａｃｅ机制．在该机制下，　根据查询函数的敏感度和隐私保护预算ｅ产生服从　Ｌａｐｌａｃｅ分布的噪声，并添加到每个查询结果中．这　种简单的机制能够处理各种类型的查询，但缺点是　查询的数量有限，与数据集记录数为次线性关系．另　外，在干扰针对连续属性的查询结果时会产生较大　的噪声．　之后，Ｒｏｔｈ和Ｒｏｕｇｈｇａｒｄｅｎ［３　提出了中位数机　制（Ｍｅｄｉａｎ）．相对于Ｌａｐｌａｃｅ机制，中位数机制能够　在相同预算下提供更多数量的查询．在该机制下，查询　被分为“难查询”和“易查询”两类．其中，“易查询”的结　果可以根据“难查询”的结果来确定，因此“易查询”就　无需消耗任何预算．他们的研究证明，给定域Ｚ和ｋ　个查询，“难查询”的数量级为０（（１ｏｇｚｋ）（１ｏｇ。ｉＺ１）），　其它均为“易查询”．“难查询”的结果通过独立的　Ｌａｐｌａｃｅ噪声进行干扰，而“易查询”的结果则用之前　查询结果的中位数来确定．中位数机制的缺点则在　于其算法的时间复杂度会随着数据集容量的增长呈　指数增长，同时，其样本复杂度也是超多项式的．　Ｈａｒｄｔ等人ｌ３　提出了另一种有效的机制，即　ＰＭＷ（Ｐｒｉｖａｔｅ　Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ　Ｗｅｉｇｈｔｓ）．该机制的　理论来源是机器学习中的加权多数算法（Ｗｅｉｇｈｔｅｄ　Ｍａｊｏｒｉｔｙ　Ａｌｇｏｒｉｔｈｍ），该算法用于通过投票机制来　构建一个复合算法．与之相似，ＰＭＷ也采用了一种　投票机制来减少隐私保护预算的消耗，使得该机制　机制回答更多的查询．在精确度方面，对于ｋ个查询，　每个结果的误差为０（￣／（１ｏｇｋ）／ｎ）．此方法在提高　查询数量的基础上较好地保证了精确性，但缺点是只　能处理计数类型的查询．因此，针对复合线性查询的　噪声复杂度问题，Ｈａｒｄｔ等人口副又提出了Ｋ＿ｎｏｒｍ机　制，将差分隐私保护的噪声复杂度作为高维凸体的　几何属性来研究．结果表明，该机制下每次查询的噪　声量为　Ｏ（ｍｉｎ｛ｋ／ｅ，￣／尼ｌｏｇ（ｎ／ｋ）／ｅ｝）　（７）　在ｋ《　时小于Ｌａｐｌａｃｅ机制下的噪声量为Ｏ（ｍｉｎ｛忌／　ｅ，　／ｅ））．但由于该机制包含在高维凸体上的随机　采样操作，导致了较高的计算复杂度．　Ｇｕｐｔａ等人　提出一种更为通用的迭代数据　集生成架构（ＩＤＣ　Ｆｒａｍｅｗｏｒｋ），并进一步证明之前　的Ｍｅｄｉａｎ和ＰＭＷ机制都是此架构的特例．在该　架构下，对于一个查询集合Ｆ，首先在定义域空间中　任意选择一个数据集，作为初始数据集假设，然后用　此数据集来回答所有的查询，若发现有某个查询结　果和真实结果之间的差别大于预定义的阈值时，则　根据此查询结果来更新数据集假设，使更新后的数　据集能在阈值范围内回答此查询．这个迭代过程循　环进行，直到所有的查询结果和真实结果的差异不　再大于阂值．由于迭代次数会少于总查询数量，所以　耗费的隐私保护预算会比普通机制更少，从而降低　噪声总量．　以上几种交互式发布机制的比较如表３所示．　表３交互式发布机制比较　ｌ０８　计　算　机　学　报　另外，还有一些针对特殊查询的发布机制，如　布尔连接查询（Ｂｏｏｌｅａｎ　Ｃｏｎｊｕｎｃｔｉｏｎ　Ｑｕｅｒｙ）、半空　间范围查询（Ｈａｌｆｓｐａｃｅ　Ｒａｎｇｅ　Ｑｕｅｒｙ）等．　Ｑｕｅｒｙ）的结果因累积噪声过大而失效．例如，图７　（ａ）中显示了一个按照年龄段对人数进行统计的直　方图，如果为每个频数加入噪声ｙ，则总体噪声为　Ｇｕｐｔａ等人口　研究了在数据集只提供统计查　７ｙ．为了降低噪声，一种有效的方法是将所有数据　询的前提下，回答布尔连接查询集合Ｆ所需的样本　复杂度问题．他们证明这种查询所需的样本复杂度　等于不可知学习的复杂度，进而把查询集合Ｆ转化　为使用次模（Ｓｕｂｍｏｄｕｌａｒ）函数描述的问题，并给出　了此机制下布尔连接查询的样本复杂度为　１　一二ｄ０（１ｏｇ‘　／ａ）／。　’　（８）　￡　其中ｄ为数据集维度．　半空间区域查询实际上是一种高维空间里的范　围查询．它用于回答“当定义好一个超平面时，有多少　个点会落在超平面上方的空间里”．Ｍｕｔｈｕｋｒｉｓｈｎａｎ　等人＿３　对半空间查询的发布机制进行了研究，他们　将高维空间的范围查询分解成多个范围，并应用差　异理论（Ｄｉｓｃｒｅｐａｎｃｙ　Ｔｈｅｏｒｙ）来确定范围的个数和　每个范围的大小，然后分别对这些范围添加Ｌａｐｌａｃｅ　噪声来保证差分隐私，并达到最优的隐私性和可用　性平衡．在该机制下，半空间查询的均方误差下界为　ｎ（ｎ卜　／　）．　交互式发布机制的研究方法是应用计算理论来　分析各种发布机制在保证差分隐私的前提下查询结　果的精确度，这些研究的结论是差分隐私在数据挖　掘、机器学习等领域应用研究的理论基础．　３．１．２基于直方图的发布　直方图是一种直观的数据分布表示形式，其结　果可作为其它统计查询或线性查询的依据．在差分　隐私保护条件下，删除数据集的一条记录只会影响　直方图中一个数据格（Ｂｉｎ）的结果，因此计算计数查　询以及其他相关查询的敏感度是比较容易的，这使　得根据直方图来为各种查询提供差分隐私保护的响　应是可行的．　在形成直方图时，需要根据属性（或属性组合）　的Ｗ个不同等级将数据集划分为Ｗ个数据格，然后　分别统计每个数据格的频数．为了提供差分隐私保　护，一种简单的方法是向叫个数据格的频数分别添　加独立的Ｌａｐｌａｃｅ噪声，也称为基于数据格的方法．　因为频数统计函数的敏感度仅为１，所以这种方法　对于Ｗ较小时（例如二维直方图）是有效的．但对于　多维直方图而言，多个变量的组合可以形成大量的数　据格，这时会使一些范围计数查询（Ｒａｎｇｅ　Ｃｏｕｎｔｉｎｇ　格合并为若干个分区（Ｐａｒｔｉｔｉｏｎ），每个分区的频数　为其中全部频数的平均值，如图７（ｂ）所示，然后为　每个分区频数加入噪声，总体噪声为３Ｙ．但是，分区　后数据格的频数相对于分区前的频数产生了一定的　误差．因此，如何结合数据分布的特征寻求合理的分　区方案，在减小Ｗ的同时尽可能降低频数误差，成　为直方图发布的主要研究内容．　５　４　３　＜２　２　２　ｌ　１　ｌ　１　Ｏ　７－１　年龄　年龄　（ａ）原始直方图　（ｂ）分区直方图　图７　直方图分区方案示例　显然，如果一个分区方案能够将直方图划分为　尽可能少的分区且每个分区中数据格频数彼此接　近，就能降低噪声并减少查询结果的误差．因此，　Ｘｉａｏ等人［∞　提出了一种基于ｋ－ｄ树的直方图发布　算法．算法首先根据给定的数据集及其ｋ个属性产　生原始直方图，得到所有数据格及其频数，用ｅ／２的　预算为所有频数加入Ｌａｐｌａｃｅ噪声．然后以这些干　扰后的频数作为ｋ维空间的数据点，采用ｋ－ｄ树算　法对空间进行递归划分，在每一次迭代中，首先计算　当前分区Ｐ。中频数分布的紧密程度为　Ｌ（Ｐ。）一∑１　ｃ。ｕｎｔ（ｃｅｌｌ　）一ｎ。Ｉ　（９）　ｃｅｌｌ∈ＤＯ　ｆ其中ｃｅｌｌ　是Ｐ。中的一个数据格，ｃｏｕｎｔ（ｃｅｌｌ　）为其频　数，ａ。是Ｐ。中的所有数据格频数的平均值．如果　Ｌ（Ｐ。）大于预定义的阈值，则将该分区划分为两个　子分区。ｋ－ｄ树算法最终将空间划分为若干个分　区，这个划分的结果实际上代表了一种分区方案．　最后，以这个分区方案对原始直方图进行分区，并　以￡／２的预算向所有分区的实际频数加入噪声并发　布．在Ｘｉａｏ等人的后续研究里，这一算法被命名为　ＤＰＣｕｂｅ［４　．与基于数据格的方法相比，当参数（频　数分布紧密度阈值、空间分割次数）的取值适当时，　ＤＰＣｕｂｅ算法在查询数量和查询误差等方面具有更　好的性能．　计　算　机　学　报　是否能在定义域Ｚ中搜索到满足条件的净化数据　集Ｄ．　的概念类别，如果不考虑计算复杂度，利用指数机　制遍历整个数据域，最终寻找出满足差分隐私保　护的数据集是可行的，且用此数据集能以指定的　精确度回答所有关于这个概念类别的查询．同时，　首先，Ｋａｓｉｖｉｓｗａｎａｔｈａｎ等人　结合差分隐私　保护与学习理论，提出了隐私保护学习（Ｐｒｉｖａｔｅ　Ｌｅａｒｎｉｎｇ）的概念，从计算学习理论的角度对差分隐　私保护条件下学习的可行性进行了必要的分析，即　在差分隐私保护条件下，成功地运行一个学习算法　他们给出了满足精确度ａ时数据集的最小样本复　杂度为　需要多少样本复杂度和计算复杂度．他们在概率近　０ｆ＼　＋　１（１５）　似正确（ＰＡＣ）框架　胡下对差分隐私保护下的ＰＡＣ　学习进行了定义．　定义８＿６　．　差分隐私ＰＡｃ学习．设概念类别　ｃ定义在实例集合Ｘ上，如果存在一个满足ｅ一差分　隐私保护的算法Ａ，使用假设空间Ｈ，对所有概念　ｃ∈Ｃ和所有ｘ上的分布　以及精确度和可用性参　数ａ，　∈（Ｏ，１／２），算法Ａ输出假设ｈ∈Ｈ，使得　Ｐｒ￣ｅｒｒ（ｈ）　ａ］　１－－８　（１１）　成立，ｅｒｒ（ｈ）为ｈ对分布　上的样例的分类错误率，　则称ｃ在差分隐私保护条件下是可ＰＡＣ学习的，　其所需样本数量是１／ｅ、１／　和ｌｏｇ（１／３）的多项式函　数，计算时间则是１／ａ和ｌｏｇ（１／３）的多项式函数．　对于ＰＡＣ扩展后的不可知学习＿６副则在相同条　件下输出ｈ的概率满足　Ｐｒ［ｅｒｒ（ｈ）　０ＰＴ＋ｄ］　１－－８　（１２）　其中ＯＰＴ＝ｍｉｎ｛ｅｒｒ（ｃ））为Ｃ中概念的最小分类错　ｆ∈Ｃ　误率．在以上定义的基础上，一个通用的基于差分隐　私保护的不可知学习器Ａ　（　）被提出．函数Ａ：（　）　采用指数机制以正比于ｅｘｐ（ｅｑ（ｚ，ｈ）／２）的概率输　出（　∈Ｈ），其中ｑ（ｚ，ｈ）一一ｍ　为可用性函数，　为　ｈ对数据集ｚ的误分类样例数．可以证明，Ａ：（ｚ）是　满足差分隐私保护要求的．同时，概念类别Ｃ使用　假设空间Ｈ—Ｃ和学习器Ａ：（ｚ）是不可知学习的，　其样本复杂度为　０（（Ｉｎ｛ＨＩ＋ｌｎ（１／　））・ｍａｘ｛１／（￡ｄ），ａ　｝）（１３）　对于无限假设空间，则样本复杂度为　Ｏ（（ＶＣ（Ｃ）・Ｉｎｌ　Ｘｌ＋ｌｎ（１／ａ））・ｍａｘ｛１／（ｅａ），Ｏｔ２｝）　（１４）　其中ＶＣ（Ｃ）为Ｃ的ＶＣ维．　Ｋａｓｉｖｉｓｗａｎａｔｈａｎ的结论表明，如果一个概念类　别在无隐私保护要求和多项式样本复杂度下是可学　习的，那么它在差分隐私保护条件下也是可学习的．　这个结论验证了在学习理论中引入差分隐私的可行　性，使之能被应用于更广泛的领域．　另一方面，Ｂｌｕｍ等人ｌ＿６　的研究证明，给定一个　由离散属性构成的域，对于任意具有多项式ＶＣ维　￡　￡　／　其中，ｄ为数据集维度，　为可用性参数．　这两个研究为净化数据集的发布提供了理论依　据和相关实现方法．但是这一方法具有较高的计算　复杂度，为数据域大小Ｉ　ＺＩ和【Ｃｌ的超多项式函数，　在实际中很难应用．围绕这个问题，学者们提出了一　些解决方法．例如，Ｄｗｏｒｋ等人【　将所有概念类别　划分为若干子集，然后采用一种递归的方式来为各　个子集构建发布数据集，最终形成町发布的总数据　集．类似的研究还包括Ｈａｒｄｔ等人　提出的基于阈　值学习的隐私数据发布算法、Ｄｗｏｒｋ等人　提出的　Ｂｏｏｓｔｉｎｇ算法等．　总之，学习理论拓展了非交互式发布的研究领　域，证明了在保证精确度的情况下发布针对某类查　询的净化数据集是可行的．但研究的难点在于如何　降低计算复杂度，如何处理数值型数据以及如何提　供更广泛的查询类型等问题上．　３．３　ＰＰＤＲ小结　数据发布一直是差分隐私研究的核心内容，其　研究进展直接影响到差分隐私在其它相关领域的应　用．本节对基于差分隐私保护的数据发布方法进行　分类并分析了各自的特点（如表５所示）．可以看出，　虽然目前差分隐私在数据发布上获取了很大进展，　但仍然有些关键问题需要进一步解决：　（１）高敏感度查询问题．差分隐私针对低敏感　度查询的效果较好，例如敏感度为１的计数查询，其　噪声方差仅为２／ｅ　．但实际应用中，会遇到很多高敏　感度查询，例如查询最大值，其敏感度可能远远大于　１．这时加入的噪声往往会覆盖原有数据，造成数据　可用性急剧下降．　（２）计算复杂度问题．大部分数据发布机制的　计算复杂度都是非高效（Ｉｎｅｆｆｉｃｉｅｎｔ）的，超过　的多　项式阶，甚至达到指数阶．高复杂度限制了差分隐私　在实际应用中的效率，成为目前需要解决的问题　之一．　１期　熊平等：差分隐私保护及其应用　１１３　组合性，提高隐私保护预算的利用率．　４基于差分隐私保护的数据挖掘　基于差分隐私保护的数据挖掘是差分隐私研究　的另一个重要方向，本节根据差分隐私在ＰＰＤＭ中　的不同应用模式，分别介绍接口模式和完全访问模　式下的各种差分隐私保护数据挖掘算法，并对其性　能进行分析和比较．　４．１接口模式下的数据挖掘　在接口模式下的数据挖掘研究中，有两个被广　４．１．１接口模式下的分类算法　分类算法［　旨在根据训练数据集建立分类器　模型，用以推测新记录的类标识．ＩＤ３ｌ＿７。　是最经典的　分类算法之一，它以信息增益为标准对训练数据集　进行迭代划分，从而建立一棵决策树．ＳｕＬＱ框架提　出了实现差分隐私保护的ＳｕＬＱ—ｂａｓｅｄ　ＩＤ３算　法ｌ７　．其基本思想是在每次计算属性的信息增益　时，使用加入噪声的计数值，最终生成相应的决策　树．此方法虽然可以保证差分隐私，但缺点是噪声过　大．从文献Ｅ３Ｕ中对模拟数据集的实验结果来看，在　隐私保护预算小于１的情况下，ＳｕＬＱ—ｂａｓｅｄ　ＩＤ３算　法相对于无隐私保护功能的ＩＤ３算法，其预测准确　率大约降低了３０　．　Ｆｒｉｅｄｍａｎ和Ｓｃｈｕｓｔｅｒ基于ＰＩＮＱ平台对　ＳｕＬＱ－ｂａｓｅｄ　ＩＤ３算法进行了改进Ｌ３　，利用其中的　Ｐａｒｔｉｔｉｏｎ算子将数据集分割成不相交的子集，然后　泛应用的接口框架，即ＳｕＬＱ和ＰＩＮＱ，两者都采用　了Ｌａｐｌａｃｅ机制作为实现差分隐私的主要方式．　ＳｕＬＱ框架由Ｂｌｕｍ等人ｌ７。。提出．首先，他们将最简　单的单属性布尔查询定义为查询原语（Ｐｒｉｍｉｔｉｖｅ）　，　然后以查询原语为基本操作来组合查询集合，可以　实现更加复杂的查询函数，只要查询的数量是记录　数量的次线性函数，即可以较小的噪声实现足够的　隐私保护．在此基础上，Ｂｌｕｍ等对ＳｕＬＱ原语做了　两个方面的扩展后形成了ＳｕＬＱ框架：（１）将处理　的数据类型从布尔型数据扩展到连续型数据；　再实现ＩＤ３算法．虽然在计算信息增益的过程中应　用Ｐａｒｔｉｔｉｏｎ算子避免了不必要的预算消耗，但由于　为计算信息增益而进行的计数查询必须为每个属性　单独执行，因此整个预算必须事先分配给每一次计　数查询，这导致每个查询的预算相对很小，所以无法　显著降低ＳｕＩ　Ｑ－ｂａｓｅｄ　ＩＤ３所引入的噪声．　针对这个问题，Ｆｒｉｅｄｍａｎ和Ｓｃｈｕｓｔｅｒ进一步在　（２）以ＳｕＬＱ原语为基本算子，设计提供隐私保护　功能的复杂算法，如是一ｍｅａｎｓ算法、ＩＤ３分类器以及　统计查询学习模型等．　ＰＩＮＱ　。。是由ＭｃＳｈｅｒｒｙ等人开发的一套为数　据提供差分隐私保护的框架，它基于ＬＩＮＱ查询语　ＩＤ３算法中应用了指数机制来实现差分隐私保护，　提出了ＤｉｆｆＰＩＤ３算法＿３　．由于在指数机制下，只需　一言并提供一系列便于二次开发的应用程序接口，其　中定义的Ｐａｒｔｉｔｉｏｎ算子允许在查询中对数据集进　行分割．由于Ｐａｒｔｉｔｉｏｎ算子可将数据集分割成不相　交的子集，因此可以利用差分隐私保护算法的并行　个查询即可实现一次对全部属性的评估，决策树　的一次分裂只需消耗一次预算，因此每个查询所分　配的预算较大，有效降低了噪声．另外，通过将离散　计　算　机　学　报　属性的处理扩展到连续属性，Ｆｒｉｅｄｍａｎ和Ｓｃｈｕｓｔｅｒ　还提出了ＤｉｆｆＰ—Ｃ４．５算法　．在实际数据集上的测　试表明，ＤｉｆｆＰＩＤ３算法和ＤｉｆｆＰ—Ｃ４．５算法的分类准　确率较ＳｕＩ　Ｑ—ｂａｓｅｄ　ＩＤａ算法有极大的提高，在样　本量足够大和￡等于１的条件下均能获得大于８０　的分类准确率．但是，ＤｉｆｆＰ　Ｃ４．５算法的缺点在于，　在每一次迭代中必须先用指数机制对所有连续属性　选择分裂点，然后将所得结果与全部离散属性一起　再次通过指数机制选择最终的分裂方案，由于每次　迭代需要两次调用指数机制，因此消耗了过多的隐　私保护预算．　对以上几种算法的归纳如表６所示．可以看出，　直接采用Ｌａｐ｜ａｃｅ机制需要较大的噪声干扰．在算　法中应用指数机制则可以提高隐私保护预算的利用　率，有效降低噪声．　表６基于接口的分类算法　４．１．２接口模式下的聚类算法　作为一种无监督学习方法，聚类算法将无类标　识的记录划分到若干个簇中，使得簇内记录相似度　高，而簇间相似度低．设聚类算法的输人为一数据　集，输出为忌个聚类，基于差分隐私保护的聚类算法　的目标则是在从数据集中删除任一记录时，保证每　个聚类的质心以及记录数量所发生的改变不泄露隐　私信息．　在ＳｕＬＱ框架里，Ｂｌｕｍ等人给出了提供差分隐　私保护的忌一ｍｅａｎｓ算法．由于在计算每个记录与质　心的距离时会泄露隐私，因此在ＳｕＬＱ框架下通过　发布聚类质心和记录数量的估计值来满足隐私保护　的要求．但根据全局敏感度的定义，查询聚类质心的　函数敏感度为聚类的最大直径，而以此敏感度计算　出的噪声量较大，降低了聚类结果的可用性．　为了解决这个问题，Ｎｉｓｓｉｍ等人¨ｌ　认为，在一　个给定的聚类中移动一个或者几个点不会显著改变　质心的位置，所以可以使用局部敏感度来有效降低　噪声．为了计算一个复杂函数，的局部敏感度和相　应的平滑边界，他们提出了一种抽样一聚合框架　（Ｓａｍｐｌｅ—ａｇｇｒｅｇａｔｅ　Ｆｒａｍｅｗｏｒｋ）．首先从原始数据　集Ｄ中随机抽样产生ｍ个子集，分别代人函数＿厂得　到　个中间结果．然后选择一个局部敏感度较低并　且容易计算的聚合函数ｇ，对ｍ个中问结果进行聚　合运算，得到一个关于厂（Ｄ）的期望值　厂（Ｄ），最后　根据函数ｇ的平滑敏感度向ｆ（Ｄ）中添加噪声，得　到最终的发布数据．　但是基于抽样聚合框架的算法在应用中存在　一定的局限性，即对所有随机抽样生成的数据集进　行聚类且输出的结果具有某种程度上的一致性时，　算法才可能输出令人满意的结果．因此，Ｆｅｌｄｍａｎ等　人　提出了一种基于核心集（Ｃｏｒｅｓｅｔ）的方法，可用　于基于差分隐私保护的是一ｍｅｄｉａｎ和是ｍｅａｎｓ聚类　分析．给定一个ｄ维空间里的点集Ｇ，样本容量为　ｎ，可以计算出一个带权重且容量为０（１ｅａ一　ｌｏｇｎ）的　点集ｓ　Ｇ，使得用Ｓ。替代Ｇ来做ｋ－ｍｅｄｉａｎ／　ｍｅａｎｓ聚类分析能够得到一个（１＋ａ）一近似结　果　］，Ｓ　称为Ｇ的核心集．Ｆｅｌｄｍａｎ等人给出了一　个满足ｅ一差分隐私保护要求的算法Ａ，能够以至少　１一　的概率输出核心集Ｓ。一Ａ（Ｇ）．给定对集合Ｇ　的走一ｍｅｄｉａｎ／ｍｅａｎｓ聚类分析查询集合Ｆ，对于任意　查询厂∈Ｆ，可使　（１－－ａ）ｆ（Ｇ）一　＿厂（Ｓｃ、）　（１＋ｃＤｆ（Ｇ）＋　（１６）　成立．其中口为预定义的边界值，ｓ　称为Ｇ的Ｐｒｉｖａｔｅ　核心集．由于Ｓ　是满足差分隐私保护要求的，因此　基于Ｓ　的聚类分析查询也是满足差分隐私保护的，　且能够满足预定义的聚类分析准确性．　另外，Ｄｗｏｒｋｌ１　从预算分配的角度对差分隐私　保护ｋ－ｍｅａｎｓ算法进行了完善，针对两种不同的情　形给出了分配预算的方法．设数据集维度为ｄ，则查　询函数的敏感度为ｄ＋１．若算法迭代次数指定为　“，则每次迭代的预算为ｅ／“，添加的噪声服从　Ｌａｐ（（　＋１）ｕ／ｓ）分布；若算法迭代次数不定，则第　一次分配的预算为ｓ／２，之后每次迭代的预算为上　一次迭代预算的１／２．　４．２完全访问模式下的数据挖掘　４．２．１　完全访问模式下的分类算法　Ｊａｇａｎｎａｔｈａｎ等人应用随机决策树算法　，提　出了完全访问模式下的差分隐私保护随机决策树分　类器构建方法　］．与传统决策树的构建方法不同，　随机决策树首先通过随机选择分类属性来构建一个　决策树架构，这个过程与数据集中的记录完全无关．　然后再把数据集的记录输入这个决策树并分配到相　应叶节点中，最后统计各叶节点中的记录数量，并将　不符合预定义规则的叶节点剪枝．一个随机决策树　分类器由多个这样的决策树构成，它们共同评估一　个记录的分类结果．显然，删除数据集中的一个记录　１期　熊平等：差分隐私保护及其应用　ｌ１５　会使决策树的某个叶节点发生改变，甚至在剪枝过　程中使得一个子树被删除．为了使随机决策树模型　满足差分隐私保护的要求，首先去掉构建模型过程　中的剪枝步骤，然后取出全部叶节点中所有可能的　类标签的计数值，形成向量Ｖ，它由Ｎ×Ｔ个整数构　成，其中Ｎ为叶节点数量，Ｔ为类标签值的数量．由　于向量Ｖ的全局敏感度为１，因此向Ｖ中加入　Ｌａｐ（１／ｅ）噪声即可达到差分隐私保护的要求（如果　分类器包含ｋ棵树，则构建每棵数所分配的预算为　ｅ／ｌｅ），有效降低了噪声量．该算法在３个实际数据集　（ＵＣＩ中的Ｎｕｒｓｅｒｙ、Ｃｏｎｇｒｅｓｓｉｏｎａｌ　Ｖｏｔｉｎｇ　Ｒｅｃｏｒｄｓ　和Ｍｕｓｈｒｏｏｍ）上的测试表明，在不同预算条件下　（￡一０．５，０．７５，１），所构建的决策树平均分类准确率　均超过了８５　．　另外Ｃｈａｕｄｈｕｒｉ等人　提出了一种满足差分　隐私保护的ｌｏｇｉｓｔｉｃ回归算法．首先，他们证明了如　果直接利用Ｌａｐｌａｃｅ机制，在输出的回归模型上加　入噪声，其分类准确度会随着正则化参数的减小而　降低．所以他们提出了一个新的算法，先将噪声加在　目标函数的参数中，然后通过标准的ｌｏｇｉｓｔｉｃ回归　算法进行参数估计来获取模型．此模型相对于直接　利用Ｌａｐｌａｃｅ机制，具有更高的分类准确率．由此可　以发现，正则化参数和隐私保护之间存在着联系，当　正则化参数增大时，回归函数的敏感度降低，所需噪　声随之减少．　４．２．２　完全访问模式下的频繁项集挖掘　频繁项集挖掘是数据挖掘领域的一项重要技　术，可用于关联规则挖掘、用户行为预测以及相关性　分析．给定数据集Ｄ，其中的每个记录称为一个事　务，每个事务由一些项（Ｉｔｅｍ）构成，这些项来自于项　空间工．项集由若干个项组成，是　的子集．如果一　个事务中包含了某项集Ｊ。，则称该事务支持项集　Ｉ。．支持项集Ｊ。的事务数量占全部事务的比例称作　项集　。的支持度，支持度大于预定义阈值的项集称　作频繁项集．频繁项集挖掘算法的输出结果即为所　有的频繁项集以及它们的支持度．　为了使频繁项集挖掘算法能够应用于包含隐私　信息的数据集，Ｂｈａｓｋａｒ等人口　对传统算法进行了　改进，提出了两个基于“截断支持度”的频繁项集挖　掘算法：基于指数机制的ＦＩＭ算法和基于Ｌａｐｌａｃｅ　机制的ＦＩＭ算法，用于根据给定数据集寻求长度为　ｚ的最频繁的Ｋ个项集．　首先，两个算法具有相同的预处理过程．利用传　统挖掘算法得到所有ｚ一项集，根据它们的真实支持度　ｓ计算出各自的“截断支持度”ｊ＝＝＝ｍａｘ（Ｓ，ｓ　一ｙ）．其　中ｓ　为第Ｋ大的支持度，ｙ为用以控制结果可用性　的预定义阈值．算法中采用“截断支持度”的主要目　的是为了避免遍历所有项集，降低算法的计算复　杂度．　之后，基于指数机制的ＦＩＭ算法以；为可用　性函数Ｋ次调用指数机制，从预处理结果中不重　复地选出Ｋ个项集；而基于Ｌａｐｌａｃｅ机制的ＦＩＭ　算法则对预处理结果中的每个；值添加Ｌａｐｌａｃｅ噪　声，然后从所得结果中选择支持度最大的Ｋ个　项集．　最后，两个算法采用相同的方法，对所选定的　Ｋ个项集，为它们的真实支持度添加Ｌａｐｌａｃｅ噪声　后，将项集及干扰后的支持度一同输出．　对算法的隐私性和可用性分析表明，两种算法　均能提供ｅ一差分隐私保护，也能以１一１０的概率实现　两个可用性要求（．０为预定义的阈值），即所有真实　支持度大于Ｓ　＋７的项集都能被输出，且所有被输　出的项集的真实支持度都不小于ｓ　—ｙ．　但这些算法也存在一些缺点．首先，算法在执行　前必须预定义输出项集的长度ｚ，而不能根据中间　结果自适应的确定ｚ的值；另外，频繁项集挖掘的难　点之一在于数据集的高维度导致的计算复杂度，所　以以上算法仅适用于Ｋ值较小的场合．当Ｋ较大　（例如Ｋ＞１００），尤其在项空间ｌ　Ｉｌ也较大时，算法的　计算性能及输出的准确性均会显著下降．　针对这些问题，Ｌｉ等人　。。提出了用于高维数据　集的频繁项集挖掘方法——ＰｒｉｖＢａｓｉｓ，能够在保证　计算性能的前提下实现差分隐私保护．ＰｒｉｖＢａｓｉｓ方　法实际上是利用了频繁项集的一个重要性质来实现　降维处理，即一个频繁项集的所有子集也都是频繁　的．为了找到最频繁的Ｋ个项集，ＰｒｉｖＢａｓｉｓ方法希　望能够找到一个项集Ｉ　，使得最频繁的Ｋ个项集均　是　的子集，然后通过计算并利用工　中ｌ＿项集和　２一项集的支持度，可以重构Ｊ　中所有子集的支持　度，并添加相应的噪声．这种方法可以避免遍历所有　可能的项集，降低计算代价．但是当Ｋ很大时，　也　必将很大，导致遍历　的子集的计算代价也增大．　对此，ＰｒｉｖＢａｓｉｓ将，　拆解为若干子集，提出了０一基　集（　一Ｂａｓｉｓ　Ｓｅｔ）的概念．一个０一基集表示为　一　｛Ｉ　，，Ｊ　，…，，　），其中　（ｉ一１，２，…，ｃＵ）称为一个　基（Ｂａｓｉｓ）．任何一个支持度大于０的项集（即一个　候选的频繁项集）都是某个　的子集．也就是说　的子集涵盖了所有支持度大于　的项集．显然，　的　计　算　机　学　报　值越小，且每个Ｉ　的长度ｌ　ｒ　ｌ越小（１　ｌ表示　中项的数量），遍历　所有子集的计算代价就越小．　ＰｒｉｖＢａｓｉｓ方法中提出了根据频繁ｌ＿项集和２一项集　ＰＰＤＭ中各种算法的有效性不但依赖于算法本身，　也受到所采用的差分隐私保护机制的精确度的影　响．所以ＰＰＤＲ中面临的高敏感度查询和计算复杂　来构建　基集　的算法．于是可以得到候选项集　Ⅲ．．　度等问题在ＰＰＤＭ中依旧存在．除此之外，ＰＰＤＭ　需要解决的问题还包括：　（１）对于许多数据挖掘算法，在接口模式下采　用现有的差分隐私保护机制来实现ＰＰＤＭ往往需　要较大的噪声．为这些算法设计新的机制以降低噪　声是目前需要解决的问题之一．　（２）在完全访问模式下，为执行不同的数据挖　Ｃ（ＪＢ）一Ｕ｛　ｌ　Ｊｘ　ＩＢ｝　ｌ　（１７）　其中　为Ｉ　的任意子集．最后为候选项集的支持　度加入Ｌａｐｌａｃｅ噪声，并选择支持度最大的Ｋ个项　集对外发布．通过对５个实际数据集的实验表明，　ＰｒｉｖＢａｓｉｓ方法在频繁项集漏报率以及支持度误差　两个方面都低于基于“截断支持度”的方法．　４．３　ＰＰＤＭ小结　掘任务，必须将各种传统算法改造为满足差分隐私　保护要求的算法，如何在一个标准的框架系统内实　现对各种算法的差分隐私化，是ＰＰＤＭ需要解决的　另一个问题．　差分隐私在数据挖掘中的应用研究与差分隐私　的理论发展密切相关．本节对基于差分隐私保护的　数据挖掘方法进行了归纳和分析，如表７所示．　表７基于差分隐私保护的数据挖掘方法分类比较　子分解方法．　５　其它应用　从应用领域来看，差分隐私保护方法还被普遍　应用于许多其它场合，例如推荐系统、网络数据分　析、搜索日志发布等．　Ｍａｃｈａｎａｖａｊｊｈａｌａ等人ｌ＿８　在基于社交网络数据　的推荐系统中使用了差分隐私保护方法．社交网　络模型通常用图来表示，图中的节点表示用户，边　则表示用户之间的关系并被视为敏感信息．为了　使构建图的过程满足差分隐私保护要求，他们以　节点的邻居数为可用性函数并采用指数机制来　随机地构造图中的边，最终实现对图中所有边的　（１）差分隐私在推荐系统中的应用．　推荐系统帮助用户从大量数据中寻找可能需要　的信息．在许多电子商务网站中，推荐系统用于发现　商品项目之问的关系，并向顾客推荐可能消费的项　Ｅｔ．由于推荐系统需要利用大量用户数据进行协同　保护．　Ｚｈｕ等人　。　针对Ｋ最近邻算法所面临的隐私　泄露问题提出了一种基于差分隐私保护的邻居协同　过滤算法．该算法通过隐私邻居选择和定义推荐敏　感度两个关键的隐私保护步骤，来确保从用户的推　荐选择中无法推断出用户的历史记录．由于在计算　噪声的过程中采用了局部敏感度，使得最终的推荐　过滤（Ｃｏｌｌａｂｏｒａｔｉｖｅ　Ｆｉｈ：ｅｒｉｎｇ），所以数据的隐私保　护问题很早就受到人们的关注．Ｍｃｓｈｅｒｒｙ等人＿８　最先将差分隐私保护方法引入到推荐系统．他们假　定推荐系统是不可信的，攻击者可以通过分析推荐　系统的历史数据来推测用户的隐私信息，因此必须　对推荐系统的输入进行干扰．在分析项目之间的关　系时，他们先建立项目相似度协方差矩阵，并向矩阵　结果保持了较好的可用性，是一种实用的隐私保护　推荐算法．另外，针对基于标签的推荐系统，Ｚｈｕ等　人　提出了一种对用户轮廓（Ｕｓｅｒ　Ｐｒｏｆｉｌｅ）进行修　改并发布的差分隐私保护算法，能够在一定的精度　损失范围内进行标签推荐并保护用户隐私．　中加入Ｌａｐｌａｃｅ噪声实施干扰，然后再提交给推荐　系统实施常规推荐算法，例如Ｋ最近邻算法或者因　１期　熊平等：差分隐私保护及其应用　１１７　（２）差分隐私在网络踪迹分析中的应用．　网络踪迹分析是通过测量和分析网络流量来获　取有用的信息．网络数据和流量记录往往由一些企　业或研究机构共享以供研究分析之用．但由于这类　分析有可能泄露隐私，所以这些网络数据在共享前　的隐私保护预算下，发布查询结果的精确性，以及保　证此精确性所需要的样本复杂度，其实现方法除了　加噪发布外，还有小波分析、域空间搜索、递归发布　等等．差分隐私保护数据挖掘关注的则是在实现隐　私保护的前提下，所得挖掘模型的分类／预测准确　性，其实现方法主要是将噪声机制或指数机制嵌入　需要经过净化．早期的净化方法主要为匿名处理．但　Ｍｃｓｈｅｒｒｙ等人［。　认为匿名化方法不足以保证网络　数据的隐私性，所以将差分隐私的概念引入，并在　ＰＩＮＱ平台上实现了网络数据统计分析的差分隐私　到数据挖掘算法中，使得数据挖掘的过程满足差分　隐私保护的要求．　当然，差分隐私保护还是一个相对年轻的研究　保护方法．其基本思想是发布网络数据的各项统计　数据时，根据每项统计的敏感度，在结果中加入　Ｌａｐｌａｃｅ噪声，使网络数据中的单独个体对统计结果　不会有影响．相对于早期的匿名化方法，此方法较好　地保证了网络数据的大部分统计特性．　（３）差分隐私在运输信息保护中的应用．　Ｃｈｅｎ等人　将差分隐私用于对运输信息的保　护．这里的运输信息是指公共交通系统中乘客的各　种乘车及换乘信息，对这些信息的分析可以促进零　售业和交通系统内的知识发现．但由于其中包含了　乘客的个人信息，所以在发布和共享之前，需要进行　隐私保护处理．分析运输信息的目的是寻找最频繁　的乘车路线，因此本质上这是一个频繁序列挖掘问　题．Ｃｈｅｎ等人根据数据的特征，采用前缀树（Ｐｒｅｆｉｘ　Ｔｒｅｅ）来表示运输信息数据集．树中每个节点表示一　个序列以及数据集对该序列的支持计数．由于这些　支持计数中加入了Ｌａｐｌａｃｅ噪声，从而保证了挖掘　结果满足了差分隐私保护的要求．　（４）差分隐私在搜索日志保护中的应用．　文献Ｅｇｏ］提出了一种搜索日志（Ｓｅａｒｃｈ　Ｌｏｇ）发　布算法，用于搜索引擎公司在差分隐私保护条件下　对外发布高频关键词、查询和点击记录等信息．　已有的应用研究表明，差分隐私作为一种严格　的隐私定义，能够为解决现实中的隐私保护问题提　供有效的解决方法，具有良好的应用前景．　６总结与展望　差分隐私是一种严格的和可证明的安全模型．　近年来的研究使得其在理论上不断发展和完善，并　在统计学、机器学习、数据挖掘、社交网络等领域得　到了初步应用．　本文介绍了差分隐私保护的基础理论，并着重　对基于差分隐私保护的数据发布和数据挖掘方法进　行了综述．差分隐私保护数据发布关注的是在给定　领域，在理论和应用上都还存在一些难点以及新的　方向需要进一步深入研究，包括：　（１）复杂数据的差分隐私保护．　在实际应用中存在许多复杂的数据集，其中的　记录之间往往存在某种联系．然而目前的差分隐私　保护方法并未考虑数据之间的联系，因此无法有效　地处理这类数据集ｌ＿９　．例如在社交网络数据中，每　个用户都会和许多其他用户产生联系，因此即便从　数据集中删除了某个用户，仍可能从与其他用户的　联系中推断出该用户的信息．在这种情况下，如果　采用传统的差分隐私保护方法，同时考虑数据之　间的联系，则查询敏感度会很高，从而引入过多　噪声．　（２）连续数据发布的隐私保护．　已有差分隐私研究大多针对静态数据发布问　题，但在实际应用中，很多数据集都是动态更新的．　例如在线零售数据、推荐系统信息等．　连续数据发布的差分隐私保护问题主要有两个　研究难点：其一是隐私保护预算的分配问题．现有的　机制需要预先定义发布的次数，然后分配隐私保护　预算．当数据持续更新超出这个次数时，预算被耗　尽，发布机制失效．第二个难点是噪声大．由于每次　更新后的数据发布必须包含之前发布时的噪声，因　此随着发布次数的增长，累积噪声会迅速增大，导致　发布结果的可用性极低．对此，Ｃｈａｎ等人　幻提出了　Ｐ—ｓｕｍ方法．该方法实质上是对实时数据进行重新　划分，只有在实时数据累积增加到阈值Ｐ的时候，　才加上噪声重新发布新的结果．但该方法并没有解　决隐私保护预算耗尽后的机制失效问题以及累积噪　声随发布次数迅速增大的问题．　连续数据发布中的隐私保护问题还需要进一步　的深入研究．我们认为，采用动态的局部敏感度是一　种可行的发布方式，即数据更新后的查询敏感度可　根据更新前的发布结果重新计算，这样可以通过降　低查询敏感度来降低噪声．　计　算　机　学　报　（３）差分隐私保护框架系统．　差分隐私保护框架系统是实现隐私保护的基础　设施．在其基础上，研究人员可以自行设计更加复杂　的差分隐私保护算法，例如在ＰＩＮＱ或ＳｕＩ　Ｑ的基　础上设计满足差分隐私的数据挖掘算法．但此类框　架系统的研究难点在于如何实现查询敏感度的自动　计算和发布机制的自动优化．查询敏感度的自动计　算是一个十分复杂的问题，可能的解决方案是为一　类查询提供一个噪声上界，但此方法可能会增加不　必要的噪声．发布机制的自动优化也同样具有挑战　性，对于复杂的查询，直接使用Ｌａｐｌａｃｅ机制和指数　机制效果并不理想，如何根据发布任务让差分隐私　保护框架自动选择优化机制还需要更深入的研究．　从目前的研究来看，复杂的差分隐私保护算法还只　能由领域专家提出并证明其差分隐私保护的性能．　（４）分布式差分隐私计算．　分布式隐私保护是隐私保护领域的一个重要分　支，它研究互不信任的多个实体如何对信息进行共　享而不泄露自己的隐私信息＿ｓ引．在具体实现中，各　实体将自己的数据集输入一个安全函数，并共享函　数输出结果．该方向的研究难点在于两点：（１）如何　选择安全函数，使之满足差分隐私的要求；（２）如何　设计协议以兼顾差分隐私性和计算复杂度ｌ９　．对这　两个问题，目前的研究还只是从理论上提出了可行　性以及相应计算的误差界限，具体的实现方法还需　要进一步的研究．　（５）差分隐私定义的延伸．　差分隐私是一种严格的定义，它假定攻击者具　有尽可能多的背景知识．因此，为了满足差分隐私保　护的要求，必须在发布结果中引入足够大的噪声，但　噪声过大可能导致数据完全失去意义．针对这个问　题，一些研究者试图通过降低差分隐私的要求，在适　当降低隐私性的情况下，提高结果的可用性．例如文　献［５６］提出的“安全ｋ一匿名”模型以及文献［９５］提　出的Ｃｒｏｗｄ—Ｂｌｅｎｄｉｎｇ隐私定义等，但这些定义在实　现上都比较困难．尽管如此，我们认为在差分隐私的　基础上提出新的隐私定义是对差分隐私定义的完善　与延伸，对于扩展差分隐私的应用领域具有重要的　意义．　总之，差分隐私保护是目前信息安全领域的研　究热点之一，也取得了丰富的研究成果．但从实际应　用的角度来看，还有许多内容需要继续深入研究．本　文从理论和应用的角度对差分隐私保护目前的研究　状况进行综述，希望能够为该领域的研究者提供有　价值的参考信息．　参　考　文　献　［１］Ｓａｍａｒａｔｉ　Ｐ．Ｐｒｏｔｅｃｔｉｎｇ　ｒｅｓｐｏｎｄｅｎｔｓ’ｉｄｅｎｔｉｔｉｅｓ　ｉｎ　ｍｉｃｒｏｄａｔａ　ｒｅｌｅａｓｅ．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００１，１３（６）：１０１０－１０２７　［２］Ｎａｒａｙａｎａｎ　Ａ。Ｓｈｍａｔｉｋｏｖ　Ｖ．Ｒｏｂｕｓｔ　ｄｅ—ａｎｏｎｙｍｉｚａｔｉｏｎ　ｏｆ　ｌａｒｇｅ　ｓｐａｒｓｅ　ｄａｔａｓｅｔｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００８　ＩＥＥＥ　Ｓｙｍｐｏ—　ｓｌｕｍ　ｏｎ　Ｓｅｃｕｒｉｔｙ　ａｎｄ　Ｐｒｉｖａｃｙ．Ｏａｋｌａｎｄ，ＵＳＡ，２００８：１　１　１—　１２５　［３］Ｓｒｉｖａｔｓａ　Ｍ，Ｈｉｃｋｓ　Ｍ．Ｄｅａｎｏｎｙｍｉｚｉｎｇ　ｍｏｂｉｌｉｔｙ　ｔｒａｃｅｓ：Ｕｓｉｎｇ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ａｓ　ａ　ｓｉｄｅ—ｃｈａｎｎｅｌ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１２　ＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｅｃｕｒｉｔｙ．　Ｒａｌｅｉｇｈ，ＵＳＡ，２０１２：６２８—６３７　［４］Ｂｌｏｎｄ　Ｓ　Ｌ，Ｚｈａｎｇ　Ｃ，Ｌｅｇｏｕｔ　Ａ，ｅｔ　ａ１．１　ｋｎｏｗ　ｗｈｅｒｅ　ｙｏｕ　ａｒｅ　ａｎｄ　ｗｈａｔ　ｙｏｕ　ａｒｅ　ｓｈａｒｉｎｇ：Ｅｘｐｌｏｉｔｉｎｇ　Ｐ２Ｐ　ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｔｏ　ｉｎｖａｄｅ　ｕｓｅｒｓ’　ｐｒｉｖａｃｙ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１　１　ＡＣＭ　ＳＩＧＣ（）ＭＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｎｔｅｒｎｅｔ　Ｍｅａｓｕｒｅｍｅｎｔ　Ｃｏｎｆｅｒｅｎｃｅ．　Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ，２０１１：４５—６０　［ｓｌ　Ｄａｌｅｎｉｕｓ　Ｔ．Ｔｏｗａｒｄｓ　ａ　ｍｅｔｈｏｄｏｌｏｇｙ　ｆｏｒ　ｓｔａｔｉｓｔｉｃａｌ　ｄｉｓｃｌｏｓｕｒｅ　ｃｏｎｔｒｏ１．Ｓｔａｔｉｓｔｉｋ　Ｔｉｄｓｋｒｉｆｔ，ｌ９７７，１５（２）：４２９—４４４　［６］Ｓｗｅｅｎｅｙ　Ｉ　．ｋ　ａｎｏｎｙｍｉｔｙ：Ａ　ｍｏｄｅｌ　ｆｏｒ　ｐｒｏｔｅｃｔｉｎｇ　ｐｒｉｖａｃｙ．　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｕｎｃｅｒｔａｉｎｔｙ，Ｆｕｚｚｉｎｅｓｓ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ—　Ｂａｓｅｄ　Ｓｙｓｔｅｍｓ，２００２，１０（５）：５５７　５７０　［７］Ｍａｃｈａｎａｖａｊｊｈａｌａ　Ａ，Ｋｉｆｅｒ　Ｄ，Ｇｅｈｒｋｅ　Ｊ，Ｖｅｎｋｉｔａｓｕｂｒａｍａｎｉａｍ　Ｍ．１－ｄｉｖｅｒｓｉｔｙ：Ｐｒｉｖａｃｙ　ｂｅｙｏｎｄ　ｋ　ａｎｏｎｙｍｉｔｙ．ＡＣＭ　Ｔｒａｎｓａｃ—　ｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｆｒｏｍ　Ｄａｔａ（ＴＫＤＤ），２００７，　１（１）：３　［８］Ｌｉ　Ｎ，Ｌｉ　Ｔ，Ｖｅｎｋａｔａｓｕｈｒａｍａｎｉａｎ　Ｓ．ｔ—ｃｌｏｓｅｎｅｓｓ：Ｐｒｉｖａｃｙ　ｂｅｙｏｎｄ　矗一ａｎｏｎｙｍｉｔｙ　ａｎｄ　１一ｄｉｖｅｒｓｉｔｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ（ＩＣＤＥ）．　Ｉｓｔａｎｂｕｌ，Ｔｕｒｋｅｙ，２００７：１０６—１　１５　［９］Ｗｏｎｇ　Ｒ　Ｃ—Ｗ，Ｌｉ　Ｊ，Ｆｕ　Ａ　Ｗ—Ｃ，Ｗａｎｇ　Ｋ．（口，ｋ）一ａｎｏｎｙｍｉｔｙ：　Ａｎ　ｅｎｈａｎｃｅｄ　ｋ—ａｎｏｎｙｍｉｔｙ　ｍｏｄｅｌ　ｆｏｒ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｐｕｂｌｉｓｈｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ｌ２ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａ—　ｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．　Ｐｈｉｌａｄｅｌｐｈｉａ，ＵＳＡ，２００６：７５４—７５９　［１　Ｏ］Ｘｉａｏ　Ｘ，Ｔａｏ　Ｙ．Ｍ—ｉｎｖａｒｉａｎｃｅ：Ｔｏｗａｒｄｓ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｒｅ　ｐｕｂｌｉｃａｔｉｏｎ　ｏｆ　ｄｙｎａｍｉｃ　ｄａｔａｓｅｔｓ／／Ｐｒ。ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００７　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，２００７：６８９—７００　［１１］Ｗｏｎｇ　Ｒ　ｗ，Ｆｕ　Ａ　Ｗ—Ｃ，Ｗａｎｇ　Ｋ，Ｐｅｉ　Ｊ．Ｍｉｎｉｍａｌｉｔｙ　ａｔｔａｃｋ　ｉｎ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｐｕｂｌｉｓｈｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｄａｔａ　Ｂａｓｅｓ．　Ｖｉｅｎｎａ，Ａｕｓｔｒｉａ，２００７：５４３—５５４　［１　２］Ｇａｎｔａ　Ｓ　Ｒ，Ｋａｓｉｖｉｓｗａｎａｔｈａｎ　Ｓ　Ｐ，Ｓｍｉｔｈ　Ａ．Ｃｏｍｐｏｓｉｔｉｏｎ　ａｔｔａｃｋｓ　ａｎｄ　ａｕｘｉｌｉａｒｙ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｎ　ｄａｔａ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄ—　ｉｎｇｓ　ｏｆ　ｔｈｅ　１４ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｌａｓ　Ｖｅｇａｓ，ＵＳＡ，　２００８：２６５－２７３　１期　熊　平等：差分隐私保护及其应用　ｌ１９　［１３］　Ｗｏｎｇ　Ｒ　Ｃ—Ｗ，Ｆｕ　Ａ　Ｗ—Ｃ，Ｗａｎｇ　Ｋ，ｅｔ　ａ１．Ｃａｎ　ｔｈｅ　ｕｔｉｌｉｔｙ　ｏｆ　ａｎｏｎｙｍｉｚｅｄ　ｄａｔａ　ｂｅ　ｕｓｅｄ　ｆｏｒ　ｐｒｉｖａｃｙ　ｂｒｅａｃｈｅｓ？ＡＣＭ　Ｔｒａｎｓ—　ａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｆｒｏｍ　Ｄａｔａ（ＴＫＤＤ），２０１１，　５（３）：１－２４　［１４］　Ｋｉｆｅｒ　Ｄ．Ａｔｔａｃｋｓ　ｏｎ　ｐｒｉｖａｃｙ　ａｎｄ　ｄｅＦｉｎｅｔｔｉ’ｓ　ｔｈｅｏｒｅｍ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００９　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｐｒｏｖｉｄｅｎｃｅ，Ｒｈｏｄｅ　Ｉｓｌａｎｄ，ＵＳＡ，２００９：ｌ２７—１３８　［１５］　Ｄｗｏｒｋ　Ｃ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐ　ｒｊｖａｃｙ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｌｌｏｑｕｉｕｍ　ｏｎ　Ａｕｔｏｍａｔａ，Ｌａｎｇｕａｇｅｓ　ａｎｄ　Ｐｒｏｇｒａｍｍｉｎｇ．Ｖｅｎｉｃｅ，Ｉｔａｌｙ，２００６：１－１２　［１６］　Ｄｗｏｒｋ　Ｃ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ：Ａ　ｓｕｒｖｅｙ　ｏｆ　ｒｅｓｕｌｔｓ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｈｅｏｒｙ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ｍｏｄｅｌｓ　ｏｆ　Ｃｏｍｐｕｔａｔｉｏｎ．Ｘｉ’ａｎ，Ｃｈｉｎａ，　２００８：卜１９　［１７］　Ｄｗｏｒｋ　Ｃ．Ａ　ｆｉｒｍ　ｆｏｕｎｄａｔｉｏｎ　ｆｏｒ　ｐｒｉｖａｔｅ　ｄａｔａ　ａｎａｌｙｓｉｓ．　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，２０１１，５４（１）：８６—９５　［１８］　Ｈａｅｂｅｒｌｅｎ　Ａ，Ｐｉｅｒｃｅ　Ｂ　Ｃ，Ｎａｒａｙａｎ　Ａ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｕｎｄｅｒ　ｆｉｒｅ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０ｔｈ　ＵＳＥＮＩＸ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｓｅｃｕｒｉｔｙ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＵＳＡ，２０１１：３３—３３　［１９］　Ｎｉｓｓｉｍ　Ｋ。Ｒａｓｋｈ０ｄｎｉｋｏｖａ　Ｓ，Ｓｍｉｔｈ　Ａ．　Ｓｍｏｏｔｈ　ｓｅｎｓｉｔｉｖｉｔｙ　ａｎｄ　ｓａｍｐｌｉｎｇ　ｉｎ　ｐｒｉｖａｔｅ　ｄａｔａ　ａｎａｌｙｓｉｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３９ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｓａｎ　Ｄｉｅｇｏ，ＵＳＡ，２００７：７５—８４　［２Ｏ］　ＭｃＳｈｅｒｒｙ　Ｆ．Ｐｒｉｖａｃｙ　ｉｎｔｅｇｒａｔｅｄ　ｑｕｅｒｉｅｓ：Ａｎ　ｅｘｔｅｎｓｉｂｌｅ　ｐｌａｔ—　ｆｏｒｍ　ｆｏｒ　ｐｒｉｖａｃｙ－ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ａｎａｌｙｓｉｓ．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，２０１０，５３（９）：８９—９７　［２Ｉ］　Ｄｗｏｒｋ　Ｃ，ＭｃＳｈｅｒｒｙ　Ｆ，Ｎｉｓｓｉｍ　Ｋ，Ｓｍｉｔｈ　Ａ．Ｃａｌｉｂｒａｔｉｎｇ　ｎｏｉｓｅ　ｔｏ　ｓｅｎｓｉｔｉｖｉｔｙ　ｉｎ　ｐｒｉｖａｔｅ　ｄａｔａ　ａｎａｌｙｓｉｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｒｙｐｔｏｇｒａｐｈｙ．Ｎｅｗ　Ｙｏｒｋ，　ＵＳＡ，２００６：２６５－２８４　［２２］　ＭｃＳｈｅｒｒｙ　Ｆ，Ｔａｌｗａｒ　Ｋ．Ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ　ｖｉａ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４８ｔｈ　Ａｎｎｕａｌ　ＩＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ．Ｐｒｏｖｉｄｅｎｃｅ，Ｒｈｏｄｅ　Ｉｓｌａｎｄ，ＵＳＡ，２００７：９４—１Ｏ３　［２３］　Ｄｗｏｒｋ　Ｃ，Ｋｅｎｔｈａｐａｄｉ　Ｋ，ＭｃＳｈｅｒｒｙ　Ｆ，ｅｔ　ａ１．Ｏｕｒ　ｄａｔａ，　ｏｕｒｓｅｌｖｅｓ：Ｐｒｉｖａｃｙ　ｖｉａ　ｄｉｓｔｒｉｂｕｔｅｄ　ｎｏｉｓｅ　ｇｅｎｅｒａｔｉｏｎ／／Ｐｒｏｃｅｅｄ—　ｉｎｇｓ　ｏｆ　ｔｈｅ　２４ｔｈ　Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｔｈｅ　Ｔｈｅｏｒｙ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ｃｒｙｐｔｏｇｒａｐｈｉｃ　Ｔｅｃｈｎｉｑｕｅｓ．Ｓｔ．　Ｐｅｔｅｒｓｂｕｒｇ，Ｒｕｓｓｉａ，２００６：４８６—５０３　［２４］　Ｄｗｏｒｋ　Ｃ，ＭｃＳｈｅｒｒｙ　Ｆ，Ｔａｌｗａｒ　Ｋ．Ｔｈｅ　ｐｒｉｃｅ　ｏｆ　ｐｒｉｖａｃｙ　ａｎｄ　ｔｈｅ　ｌｉｍｉｔｓ　ｏｆ　ＬＰ　ｄｅｃｏｄｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇ８　ｏｆ　ｔｈｅ　３９ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｓａｎ　Ｄｉｅｇｏ，　ＵＳＡ，２００７：８５—９４　［２５］　Ｄｗｏｒｋ　Ｃ，Ｎａｏｒ　Ｍ，Ｐｉｔａｓｓｉ　Ｔ，Ｒｏｔｈｂｌｕｍ　Ｇ　Ｎ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｕｎｄｅｒ　ｃｏｎｔｉｎｕａｌ　０ｂｓｅｒｖａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４２ｎｄ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｃａｍｂｒｉｄｇｅ，　ＵＳＡ，２Ｏｌ０：７１５－７２４　［２６］　Ｄｗｏｒｋ　Ｃ，Ｎａｏｒ　Ｍ．Ｏｎ　ｔｈｅ　ｄｉｆｆｉｃｕｌｔｉｅｓ　ｏｆ　ｄｉｓｃｌｏｓｕｒｅ　ｐｒｅｖｅｎ－　ｔｉｏｎ　ｉｎ　ｓｔａｔｉｓｔｉｃａｌ　ｄａｔａｂａｓｅｓ　ｏｒ　ｔｈｅ　ｃａｓｅ　ｆｏｒ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ．　Ｊｏｕｒｎａｌ　ｏｆ　Ｐｒｉｖａｃｙ　ａｎｄ　Ｃｏｎｆｉｄｅｎｔｉａｌｉｔｙ，２００８，２（１）：８　［２７３　Ｄｗｏｒｋ　Ｃ．Ｔｈｅ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｆｒｏｎｔｉｅｒ（ｅｘｔｅｎｄｅｄ　ａｂｓｔｒａｃｔ）／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　６ｔｈ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｒｙｐｔｏｇｒａｐｈｙ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｒｙｐｔ０ｇｒａｐｈｙ．　Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，　２００９：４９６—５０２　［２８］　Ｄｗｏｒｋ　Ｃ，Ｎａｏｒ　Ｍ，Ｒｅｉｎｇｏｌｄ　Ｏ，ｅｔ　ａ１．Ｏｎ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｅ：Ｅｆｆｉｃｉｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｈａｒｄｎｅｓｓ　ｒｅｓｕｌｔｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４　１　ｓｔ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｂｅｔｈｅｓｄａ，ＵＳＡ。　２００９：３８卜３９０　［２９］　Ｄｗｏｒｋ　Ｃ，Ｌｅｉ　Ｊ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ａｎｄ　ｒｏｂｕｓｔ　ｓｔａｔｉｓｔｉｃｓ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４１ｓｔ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｂｅｔｈｅｓｄａ，ＵＳＡ，２００９：３７卜３８０　［３ｏ］　Ｄｗｏｒｋ　Ｃ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｉｎ　ｎｅｗ　ｓｅｔｔｉｎｇｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２１ｓｔ　Ａｎｎｕａｌ　ＡＣＭ—ＳＩＡＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｄｉｓｃｒｅｔｅ　Ａｌｇｏｒｉｔｈｍｓ．Ａｕｓｔｉｎ，Ｔｅｘａｓ，２０１０：１７４　１８３　［３１］　Ｆｒｉｅｄｍａｎ　Ａ，Ｓｃｈｕｓｔｅｒ　Ａ．Ｄａｔａ　ｍｉｎｉｎｇ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ／／Ｐｒｏｅｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　６ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．　Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，２０１０：４９３—５０２　［３２］　Ｒｏｔｈ　Ａ．Ｎｅｗ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｐｒｅｓｅｒｖｉｎｇ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　［Ｐｈ．Ｄ．ｄｉｓｓｅｒｔａｔｉｏｎ］．Ｃａｒｎｅｇｉｅ　Ｍｅｌｌｏｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｐｉｔｔｓｂｕｒｇｈ，　ＵＳＡ，２Ｏ１０　［３３］　Ｒｏｔｈ　Ａ，Ｒｏｕｇｈｇａｒｄｅｎ　Ｔ．Ｉｎｔｅｒａｃｔｉｖｅ　ｐｒｉｖａｃｙ　ｖｉａ　ｔｈｅ　ｍｅｄｉａｎ　ｍｅｃｈａｎｉｓｍ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４２ｎｄ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｃａｍｂｒｉｄｇｅ，ＵＳＡ，２０１０：７６５—７７４　［３４］　Ｈａｒｄｔ　Ｍ，Ｒｏｔｈｂｌｕｍ　Ｇ　Ｎ．Ａ　ｍｕｈｉｐｌｉｃａｔｉｖｅ　ｗｅｉｇｈｔｓ　ｍｅｃｈａｎｉｓｍ　ｆｏｒ　ｐｒｉｖａｃｙ—ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ａｎａ１ｙｓｉｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１０　ＩＥＥＥ　５　１　ｓｔ　Ａｎｎｕａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ．２Ｏ１０：６１—７０　［３５］　Ｈａｒｄｔ　Ｍ，Ｔａｌｗａｒ　Ｋ．Ｏｎ　ｔｈｅ　ｇｅｏｍｅｔｒｙ　ｏｆ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４２ｎｄ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍ—　ｐｕｔｉｎｇ．Ｃａｍｂｒｉｄｇｅ，ＵＳＡ，２Ｏ１０：７０５—７１４　［３６］　Ｇｕｐｔａ　Ａ，Ｒｏｔｈ　Ａ，Ｕｌｌｍａｎ　Ｊ．Ｉｔｅｒａｔｉｖｅ　ｃｏｎｓｔｒｕｃｔｉｏｎｓ　ａｎｄ　ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｅ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　９ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｒｙｐｔｏｇｒａｐｈｙ．Ｓｉｃｉｌｙ，Ｉｔａｌｙ，２０１２：　３３９—３５６　［３７］　Ｇｕｐｔａ　Ａ，Ｈａｒｄｔ　Ｍ，Ｒｏｔｈ　Ａ，Ｕｌｌｍａｎ　Ｊ．Ｐｒｉｖａｔｅｌｙ　ｒｅｌｅａｓｉｎｇ　ｃｏｎｊｕｎｃｔｉｏｎｓ　ａｎｄ　ｔｈｅ　ｓｔａｔｉｓｔｉｃａｌ　ｑｕｅｒｙ　ｂａ　ｅｒ／／Ｐｒｏｃｅｅｄ｜ｎｇｓ　ｏｆ　ｔｈｅ　４３ｒｄ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．　Ｓａｎ　Ｊｏｓｅ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，２０１１：８０３—８１２　［３８］　Ｍｕｔｈｕｋｒｉｓｈｎａｎ　Ｓ，　Ｎｉｋｏｌｏｖ　Ａ．　Ｏｐｔｉｍａｌ　ｐｒｉｖａｔｅ　ｈａｌｆｓｐａｃｅ　ｃｏｕｎｔｉｎｇ　ｖｉａ　ｄｉｓｃｒｅｐａｎｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４４ｔｈ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｎｅｗ　Ｙｏｒｋ，ＵＳＡ，２０１２：１２８５一　ｌ２９２　［３９］　Ｘｉａｏ　Ｙ，Ｘｉｏｎｇ　Ｌ，Ｙｕａｎ　Ｃ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｅ　ｔｈｒｏｕｇｈ　ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ　ｐａｒｔｉｔｉｏｎｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　ＶＬＤＢ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｓｅｃｕｒｅ　Ｄａｔａ　Ｍａｎａｇｅｍｅｎｔ．Ｓｉｎｇａｐｏｒｅ，　２Ｏ１Ｏ：１５Ｏ一１６８　［４Ｏ］　Ｘｉａｏ　Ｙ，Ｇａｒｄｎｅｒ　Ｊ，Ｘｉｏｎｇ　Ｌ．ＤＰＣｕｂｅ：Ｒｅｌｅａｓｉｎｇ　ｄｉｆｆｅｒｅｎｔｉ—　ａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　ｃｕｂｅｓ　ｆｏｒ　ｈｅａｌｔｈ　ｉｎｆｏｒｍａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１２　ＩＥＥＥ　２８ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，２０１２：１３０５—１３０８　１２０　计　算　机　学　报　２０１４年　［４１］　Ｘｕ　Ｊ，Ｚｈａｎｇ　Ｚ，Ｘｉａｏ　Ｘ，ｅｔ　ａ１．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｈｉｓｔｏｇｒａｍ　ｐｕｂ１ｉｃａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１２　ＩＥＥＥ　２８ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，　ＵＳＡ，２Ｏ１２：３２—４３　［４２］　Ｈａｙ　Ｍ，Ｒａｓｔｏｇｉ　Ｖ，Ｍｉｋｌａｕ　Ｇ，Ｓｕｅｉｕ　Ｄ．Ｂｏｏｓｔｉｎｇ　ｔｈｅ　ａｃｃｕ　ｒａｃｙ　ｏｆ　ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｈｉｓｔｏｇｒａｍｓ　ｔｈｒｏｕｇｈ　ｃｏｎｓｉｓｔｅｎｃｙ．　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２０１０，３（１－２）：１０２１—　１０３２　［４３］　Ｄｉｎｕｒ　Ｉ，Ｎｉｓｓｉｍ　Ｋ．Ｒｅｖｅａｌｉｎｇ　ｉｎｆｏｒｍａｔｉｏｎ　ｗｈｉｌｅ　ｐｒｅｓｅｒｖｉｎｇ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅ　ｄｉｎｇｓ　ｏｔ　ｔｈｅ　２２ｎｄ　ＡＣＭ　ＳＩＧＭＯＤ　ＳＩＧＡＣＴ　ＳＩＧＡＲＴ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ．Ｓａｎ　Ｄｉｅｇｏ，ＵＳＡ，２００３：２０　２－２１０　［４４］　Ｘｉａｏ　Ｘ，Ｗａｎｇ　Ｇ，Ｇｅｈ　ｘｋｅ　Ｊ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｖｉａ　ｗａｖｅｌｅｔ　ｔｒａｎｓｆｏｒｍｓ．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１１，２３（８）：１　２００　１２１４　［４５２　Ｌｉ　Ｃ，Ｈａｙ　Ｍ，Ｒａｓｔｏｇｉ　Ｖ，ｅｔ　ａ１．Ｏｐｔｉｍｉｚｉｎｇ　ｌｉｎｅａｒ　ｃｏｕｎｔｉｎｇ　ｑｕｅｒｉｅｓ　ｕｎｄｅｒ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２９ｔｈ　ＡＣＭ　ＳＩＧＭＯＤ—ＳＩＧＡＣＴ－ＳＩＧＡＲＴ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ．Ｉｎｄｉａｎａｐｏｌｉｓ，ＵＳＡ，２０１０：１２３　１３４　［４６］　Ｃｏｒｍｏｄｅ　Ｇ，Ｓｒｉｖａｓｔａｖａ　Ｄ，Ｓｈｅｎ　Ｅ，Ｙｕ　Ｔ．Ａｇｇｒｅｇａｔｅ　ｑｕｅｒｙ　ａｎｓｗｅｒｉｎｇ　ｏｎ　ｐｏｓｓｉｂｉｌｉｓｌ　ｉｅ　ｄａｔａ　ｗｉｔｈ　ｃａｒｄｉｎａｌｉｔｙ　ｃｏｎｓｔｒａｉｎｔｓ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２Ｏ１２　ＩＥＥＥ　２８ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，２０１２：２５８—２６９　［４７］　Ｂａｒａｋ　Ｂ，Ｃｈａｕｄｈｕｒｉ　Ｋ，Ｄｗｏｒｋ　Ｃ，ｅｔ　ａ１．Ｐｒｉｖａｃｙ，ａｃｃｕｒａｃｙ，　ａｎｄ　ｃｏｎｓｉｓｔｅｎｃｙ　ｔＯＯ：Ａ　ｈｏｌｉｓｔｉｃ　ｓｏｌｕｔｉｏｎ　ｔｏ　ｃｏｎｔｉｎｇｅｎｃｙ　ｔａｂｌｅ　ｒｅ１ｅａｓｅ／／Ｐｒ。ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２６ｔｈ　ＡＣＭ　ＳＩＧＭＯＤ—ＳＩＧＡＣＴ—　ＳＩＧＡＲＴ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ．　Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，２００７：２７３—２８２　［４８］　Ｄｏｂｒａ　Ａ，Ｆｉｅｎｂｅｒｇ　Ｓ．Ｂｏｕｎｄｉｎｇ　ｅｎｔｒｉｅｓ　ｉｎ　ｍｕｌｔｉ—ｗａｙ　ｃｏｎｔｉｎ　ｇｅｎｃｙ　ｔａｂｌｅｓ　ｇｉｖｅｎ　ａ　ｓｅｔ　ｏｆ　ｍａｒｇｉｎａｌ　ｔｏｔａｌｓ／／Ｈａｉｔｏｖｓｋｙ　Ｙ，　Ｒｉｔｏｖ　Ｙ，Ｌｅｒｃｈｅ　Ｈ　ｅｄｓ．Ｆｏｕｎｄａｔｉ０ｎｓ　ｏｆ　Ｓｔａｔｉｓｔｉｃａｌ　Ｉｎｆｅｒｅｎｃｅ．　Ｈｅｉｄｅｌｂｅｒｇ，Ｇｅｒｍａｎ：Ｉ　ｈｙｓｉｃａ　Ｖｅｒｌａｇ　ＨＤ，２００３：３－１６　［４９］　Ｄｅ　Ｌｏｅｒａ　Ｊ，Ｏｎｎ　Ｓ．　Ａｌｌ　ｒａｔｉｏｎａｌ　ｐｏｌｙｔｏｐｅｓ　ａｒｅ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｐｏｌｙｔｏｐｅｓ　ａｎｄ　ａｌｌ　ｐｏｌｙｔｏｐａｌ　ｉｎｔｅｇｅｒ　ｓｅｔｓ　ａｒｅ　ｃｏｎｔｉｎｇｅｎｃｙ　ｔａｂｋｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　１０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　ＩＰＣＯ　Ｃｏｎｆｅｒｅｎｃｅ．　Ｎｅｗ　Ｙｏｒｋ，ＵＳＡ，２００４：３３８—３５１　［５０］　Ｄｅ　Ｌｏｅｒａ　Ｊ，Ｏｎｎ　Ｓ．Ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｒｅｅ—ｗａｙ　ｓｔａｔｉｓｔｉｃａｌ　ｔａｂｌｅｓ．ＳＩＡＭ　Ｊｏｕｒｎａｌ（ｉｎ　Ｃｏｍｐｕｔｉｎｇ，２００４，３３（４）：８１９－８３６　［５１］　Ｄｅ　Ｌｏｅｒａ　Ｊ，Ｏｎｎ　Ｓ．Ｍａｒｋｏｖ　ｂａｓｅｓ　ｏｆ　ｔｈｒｅｅ—ｗａｙ　ｔａｂｌｅｓ　ａｒｅ　ａｒｂｉｔｒａｒｉｌｙ　ｃｏｍｐｌｉｃａｔｅｄ．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｙｍｂｏｌｉｃ　Ｃｏｍｐｕｔａｔｉｏｎ，　２００６，４１（２）：１７３—１８１　［５２］　Ｋａｓｉｖｉｓｗａｎａｔｈａｎ　Ｓ　Ｐ，ｌ￣ｕｄｅｌｓｏｎ　Ｍ，Ｓｍｉｔｈ　Ａ，Ｕｌｌｍａｎ　Ｊ．Ｔｈｅ　ｐｒｉｃｅ　ｏｆ　ｐｒｉｖａｔｅｌｙ　ｒｅｌｅａｓｉｎｇ　ｃｏｎｔｉｎｇｅｎｃｙ　ｔａｂｌｅｓ　ａｎｄ　ｔｈｅ　ｓｐｅｃｔｒａ　ｏｆ　ｒａｎｄｏｍ　ｍａｔｒｉｃｅｓ　ｗｉｔｈ　ｃｏｒｒｅｌａｔｅｄ　ｒｏｗｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４２ｎｄ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｃａｍｂｒｉｄｇｅ。　ＵＳＡ，２０１０：７７５－７８４　［５３］　Ｆｉｅｎｂｅｒｇ　Ｓ　Ｅ，Ｒｉｎａｌｄｏ　Ａ，Ｙａｎｇ　Ｘ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ａｎｄ　ｔｈｅ　ｒｉｓｋ——ｕｔｉｌｉｔｙ　ｔｒａｄｅｏｆｆ　ｆｏｒ　ｍｕｌｔｉ—－ｄｉｍｅｎｓｉｏｎａｌ　ｃｏｎｔｉｎｇｅｎｃｙ　ｔａｂｌｅｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１０　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐｒｉｖａｃｙ　ｉｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ｄａｔａｂａｓｅｓ．Ｃｏｒｆｕ，Ｇｒｅｅｃｅ，２０１０：１８７一　】９９　［５４］　Ｙａｎｇ　Ｘ，Ｆｉｅｎｂｅｒｇ　Ｓ　Ｅ，Ｒｉｎａｌｄｏ　Ｒ．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｆｏｒ　ｐｒｏｔｅｃｔｉｎｇ　ｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎａｌ　ｃｏｎｔｉｎｇｅｎｃｙ　ｔａｂｌｅ　ｄａｔａ：Ｅｘｔｅｎ—　ｓｉｏｎｓ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎｓ．Ｊｏｕｒｎａｌ　ｏｆ　Ｐｒｉｖａｃｙ　ａｎｄ　Ｃｏｎｆｉｄｅｎｔｉａｌｉｔｙ，　２Ｏ１２，４（１）：１０卜１２５　［５５］　Ｍａｃｈａｎａｖａｊｊｈａ１ａ　Ａ，Ｏｅｈｒｋｅ　Ｊ，ＧＯｔｚ　Ｍ．Ｄａｔａ　ｐｕｂｌｉｓｈｉｎｇ　ａｇａｉｎｓｔ　ｒｅａｌｉｓｔｉｃ　ａｄｖｅｒｓａｒｉｅｓ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＩ　ＤＢ　Ｅｎｄｏｗｍｅｎｔ，２００９，２（１）：７９０　８Ｏ１　［５６］　Ｉ　ｉ　Ｎ，Ｑａｒｄａｊｉ　Ｗ，Ｓｕ　Ｄ．Ｏｎ　ｓａｍｐｌｉｎｇ，ａｎｏｎｙｍｉｚａｔｉｏｎ，ａｎｄ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｏｒ，ｋ—ａｎｏｎｙｍｉｚａｔｉｏｎ　ｍｅｅｔｓ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｎｆｏｒ　ｍａｔｉｏｎ，Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｅｃｕｒｉｔｙ．Ｓｅｏｕｌ，　Ｋｏｒｅａ，２０ｌ２：３２—３３　［５７］　Ｍｏｈａｍｍｅｄ　Ｎ，Ｃｈｅｎ　Ｒ，Ｆｕｎｇ　Ｂ　Ｃ　Ｍ，Ｙｕ　Ｐ　Ｓ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｅ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　７ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｓａｎ　Ｄｉｅｇｏ，ＵＳＡ，２０１１：４９３　５Ｏ１　［５８］　Ｚｈｕ　Ｔ，Ｘｉｏｎｇ　Ｐ，Ｘｉａｎｇ　Ｙ，Ｚｈｏｕ　Ｗ．Ａｎ　ｅｆｆｅｃｔｉｖｅ　ｄｉｆｆｅｒｅｎｔｉ—　ａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　ｌｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｒｕｓｔ，Ｓｅｃｕｒｉｔｙ　ａｎｄ　Ｐｒｉｖａｃｙ　ｉｎ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｃｏｍｍｕｎｉｃａ—　ｔｉｏｎｓ．Ｍｅｌｂｏｕｒｎｅ，Ａｕｓｔｒａｌｉａ，２０１３：３８８—３９５　［５９］　Ａｎｔｈｏｎｙ　Ｍ，Ｂａｒｔｌｅｔｔ　Ｐ　Ｉ　．　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ　Ｉ　ｅａｒｎｉｎｇ：　Ｔｈｅｏｒｅｔｉｃａｌ　Ｆｏｕｎｄａｔｉｏｎｓ．　Ｃａｍｂｒｉｄｇｅ，　ＵＫ：　Ｃａｍｂｒｉｄｇｅ　Ｕｎｉｖｅｒｓｉｔｙ　Ｐｒｅｓｓ，２００９　［６０］　Ｋａｓｉｖｉｓｗａｎａｔｈａｎ　Ｓ　Ｐ，Ｌｅｅ　Ｈ　Ｋ，Ｎｉｓｓｉｍ　Ｋ，ｅｔ　ａ１．Ｗｈａｔ　ｃａｎ　ｗｅ　ｌｅａｒｎ　ｐｒｉｖａｔｅｌｙ？ＳＩＡＭ　Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｐｕｔｉｎｇ，２Ｏｌ　１，　４０（３）：７９３　８２６　［６１］　Ｂｌｕｍ　Ａ，Ｌｉｇｅｔｔ　Ｋ，Ｒｏｔｈ　Ａ．Ａ　ｌｅａｒｎｉｎｇ　ｔｈｅｏｒｙ　ａｐｐｒｏａｃｈ　ｔｏ　ｎｏｎ—ｉｎｔｅｒａｃｔｉｖｅ　ｄａｔａｂａｓｅ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４０ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｖｉｃｔｏｒｉａ，　Ｃａｎａｄａ，２００８：６０９—６１８　［６２］　Ｖａｌｉａｎｔ　Ｌ　Ｇ．Ａ　ｔｈｅｏｒｙ　ｏｆ　ｔｈｅ　ｌｅａｒｎａｂｌｅ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　６ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．　Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，１９８４：４３６　４４５　［６３］　Ｋｅａｒｎｓ　Ｍ　Ｊ，Ｓｃｈａｐｉｒｅ　Ｒ　Ｅ，Ｓｅｌｌｉｅ　Ｉ　Ｍ．Ｔｏｗａｒｄ　ｅｆｆｉｃｉｅｎｔ　ａｇｎｏｓｔｉｃ　ｌｅａｒｎｉｎｇ．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９４，１７（２　３）：ｌ１　５　１４１　［６４］　Ｈａｒｄｔ　Ｍ，Ｒｏｔｈｂｌｕｍ　Ｇ　Ｎ，Ｓｅｒｖｅｄｉｏ　Ｒ　Ａ．Ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｅ　ｖｉａ　ｌｅａｒｎｉｎｇ　ｔｈｒｅｓｈｏ１ｄｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２３ｒｄ　Ａｎｎｕａｌ　ＡＣＭ—ＳＩＡＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｄｉｓｃｒｅｔｅ　Ａｌｇｏｒｉｔｈｍｓ．Ｋｙｏｔｏ，　Ｊａｐａｎ，２０１２：１６８—１８７　［６５］　Ｄｗｏｒｋ　Ｃ，Ｒｏｔｈｂｌｕｍ　Ｇ　Ｎ，Ｖａｄｈａｎ　Ｓ．Ｂｏｏｓｔｉｎｇ　ａｎｄ　ｄｉｆｆｅｒｅｎ—　ｔｉａｌ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１０　ＩＥＥＥ　５ｌｓｔ　Ａｎｎｕａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ．Ｉ　ａｓ　Ｖｅｇａｓ，　ＵＳＡ，２０１０：５１　６０　［６６］　Ａｃｓ　Ｇ，Ｃａｓｔｅｌｌｕｃｃｉａ　Ｃ，Ｃｈｅｎ　Ｒ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｈｉｓｔｏ　ｇｒａｍ　ｐｕｂｌｉｓｈｉｎｇ　ｔｈｒｏｕｇｈ　ｌｏｓｓｙ　ｃｏｍｐｒｅｓｓｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１２　ＩＥＥＥ　１２ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｂｒｕｓｓｅｌｓ，Ｂｅｌｇｉｕｍ，２０１　２：卜１　０　［６７］　Ｙｕａｎ　Ｇ，Ｚｈａｎｇ　Ｚ，Ｗｉｎｓｌｅｔｔ　Ｍ，ｅｔ　ａ１．Ｌｏｗ－ｒａｎｋ　ｍｅｃｈａｎｉｓｍ：　Ｏｐｔｉｍｉｚｉｎｇ　ｂａｔｃｈ　ｑｕｅｒｉｅｓ　ｕｎｄｅｒ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ．Ｐｒｏｃｅｅｄ—　ｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＩ　ＤＢ　Ｅｎｄｏｗｍｅｎｔ，２０１２，５（１１）：ｌ３５２—１３６３　１期　熊　平等：差分隐私保护及其应用　ｌ２１　［６８］　Ｌｉ　ｃ，Ｍｉｋｌａｕ　Ｇ．Ａｎ　ａｄａｐｔｉｖｅ　ｍｅｃｈａｎｉｓｍ　ｆｏｒ　ａｃｃｕｒａｔｅ　ｑｕｅｒｙ　ａｎｓｗｅｒｉｎｇ　ｕｎｄｅｒ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２０１２，５（６）：５１４　５２５　Ｅ６９］　Ｙａｒｏｓｌａｖｔｓｅｖ　Ｇ，Ｐｒｏｃｏｐｉｕｃ　Ｃ　Ｍ，Ｃｏｒｍｏｄｅ　Ｇ，Ｓｒｉｖａｓｔａｖａ　Ｄ．　Ａｃｃｕｒａｔｅ　ａｎｄ　ｅｆｆｉｃｉｅｎｔ　ｐｒｉｖａｔｅ　ｒｅｌｅａｓｅ　ｏｆ　ｄａｔａｃｕｂｅｓ　ａｎｄ　ｃｏｎｔｉｎ—　ｇｅｎｃｙ　ｔａｂｌｅｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１３　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ（ＩＣＤＥ　２０１３）．Ｂｒｉｓｂａｎｅ，　Ａｕｓｔｒａｌｉａ，２０１３：７４５—７５６　［７Ｏ］　Ｂｌｕｍ　Ａ，Ｄｗｏｒｋ　Ｃ，ＭｃＳｈｅｒｒｙ　Ｆ，Ｎｉｓｓｉｍ　Ｋ．Ｐｒａｃｔｉｃａｌ　ｐｒｉｖａｃｙ：　Ｔｈｅ　ＳｕＬＱ　ｆｒａｍｅｗｏｒｋ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２４ｔｈ　ＡＣＭ　ＳＩＧＭ０Ｄ—ＳＩＧＡＣＴ—ＳＩＧＡＲＴ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ．Ｂａｌｔｉｍｏｒｅ，ＵＳＡ，２００５：１２８—１３８　［７１］　Ｄｗｏｒｋ　Ｃ，Ｎｉｓｓｉｍ　Ｋ．Ｐｒｉｖａｃｙ－ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａｍｉｎｉｎｇ　ｏｎ　ｖｅｒｔｉ—　ｃａｌｌｙ　ｐａｒｔｉｔｉｏｎｅｄ　ｄａｔａｂａｓｅｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２４ｔｈ　Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｒｙｐｔｏｌｏｇｙ　Ｃｏｎｆｅｒｅｎｃｅ．Ｓａｎｔａ　Ｂａｒｂａｒａ，ＵＳＡ，　２００４：５２８—５４４　［７２］　Ｈａｎ　Ｊ，Ｋａｍｂｅｒ　Ｍ，Ｐｅｉ　Ｊ．Ｄａｔａ　Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＣＡ，ＵＳＡ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ　Ｉｎｃ．，２０１　１　［７３］　Ｑｕｉｎｌａｎ　Ｊ　Ｒ．Ｉｎｄｕｃｔｉｏｎ　ｏｆ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅｓ／／Ｂｒｕｃｅ　Ｇ　Ｂ，Ｄａｖｉｄ　Ｃ　Ｗ．Ｒｅａｄｉｎｇｓ　ｉｎ　ｋｎｏｗｌｅｄｇｅ　ａｃｑｕｉｓｉｔｉｏｎ　ａｎｄ　ｌｅａｒｎｉｎｇ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＣＡ，ＵＳＡ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ　Ｉｎｃ．，　１９９３：３４９—３６１　［７４３　Ｆｅｌｄｍａｎ　Ｄ，Ｆｉａｔ　Ａ，Ｋａｐｌａｎ　Ｈ，Ｎｉｓｓｉｍ　Ｋ．Ｐｒｉｖａｔｅ　ｃｏｒｅｓｅｔｓ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４１ｓｔ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｂｅｔｈｅｓｄａ，ＵＳＡ，２００９：３６１—３７０　［７５］　Ｈａｒ－Ｐｅｌｅｄ　Ｓ，Ｍａｚｕｍｄａｒ　Ｓ．Ｏｎ　ｃｏｒｅｓｅｔｓ　ｆｏｒ　ｋ—ｍｅａｎｓ　ａｎｄ　ｋ—ｍｅｄｉａｎ　ｃｌｕｓｔｅ　ｒｉｎｇ／／Ｐｒ０ｃｅｅ　ｄｉｎｇｓ　ｏｆ　ｔｈｅ　３６ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ．Ｃｈｉｃａｇｏ，ＵＳＡ，２００４：　２９Ｉ－３００　［７６］　Ｆａｎ　Ｗ。Ｗａｎｇ　Ｈ。Ｙｕ　Ｐ　Ｓ，Ｍａ　Ｓ．Ｉｓ　ｒａｎｄｏｍ　ｍｏｄｅｌ　ｂｅｔｔｅｒ？　Ｏｎ　ｉｔｓ　ａｃｃｕｒａｃｙ　ａｎｄ　ｅｆｆｉｃｉｅｎｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｍｅｌｂｏｕｒｎｅ，ＵＳＡ，　２００３：５１　［７７３　Ｊａｇａｎｎａｔｈａｎ　Ｇ，Ｐｉｌｌａｉｐａｋｋａｍｎａｔｔ　Ｋ，Ｗｒｉｇｈｔ　Ｒ　Ｎ．Ａ　ｐｒａｃｔｉｃａｌ　ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｒａｎｄｏｍ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ｃｌａｓｓｉｆｉｅｒ．Ｔｒａｎｓａｃ—　ｔｉｏｎｓ　ｏｎ　Ｄａｔａ　Ｐｒｉｖａｃｙ，２０１２，５（１）：２７３—２９５　［７８］　Ｃｈａｕｄｈｕｒｉ　Ｋ，Ｍｏｎｔｅｌｅｏｎｉ　Ｃ．Ｐｒｉｖａｃｙ－ｐｒｅｓｅｒｖｉｎｇ　ｌｏｇｉｓｔｉｃ　ｒｅｇｒｅｓｓｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２２ｎｄ　Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｕｒａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｓｙｓｔｅｍｓ（ＮＩＰＳ’２００８）．　Ｖａｎｃｏｕｖｅｒ，Ｃａｎａｄａ，２００８：２８９—２９６　［７９］　Ｂｈａｓｋａｒ　Ｒ，Ｌａｘｍａｎ　Ｓ，Ｓｍｉｔｈ　Ａ，Ｔｈａｋｕｒｔａ　Ａ．Ｄｉｓｃｏｖｅｒｉｎｇ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎｓ　ｉｎ　ｓｅｎｓｉｔｉｖｅ　ｄａｔａ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　６ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，２０１０：５０３—　５１２　［８Ｏ］　Ｌｉ　Ｎ，Ｑａｒｄａｊｉ　Ｗ。Ｓｕ　Ｄ，Ｃａｏ　Ｊ．ＰｒｉｖＢａｓｉｓ：Ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔ　ｍｉｎｉｎｇ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２０１２，５（１１）：１３４０—１３５１　［８１］　Ｃｈａｕｄｈｕｒｉ　Ｋ，Ｍｏｎｔｅｌｅｏｎｉ　Ｃ，Ｓａｒｗａｔｅ　Ａ　Ｄ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｅｍｐｉｒｉｃａｌ　ｒｉｓｋ　ｍｉｎｉｍｉｚａｔｉｏｎ．Ｔｈｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｒｅｓｅａｒｃｈ，２０１１，１２：１０６９一ｌ１０９　［８２３　Ｚｅｎｇ　Ｃ，Ｎａｕｇｈｔｏｎ　Ｊ　Ｆ，Ｃａｉ　Ｊ－Ｙ．Ｏｎ　ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔ　ｍｉｎｉｎｇ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗ—　ｍｅｎｔ，２Ｏｌ２，６（１）：２５—３６　［８３３　Ｓｈｅｎ　Ｅ，Ｙｕ　Ｔ．Ｍｉｎｉｎｇ　ｆｒｅｑｕｅｎｔ　ｇｒａｐｈ　ｐａｔｔｅｒｎｓ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎ—　ｔｉａｌ　ｐ　ｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　９ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａ—　ｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．　Ｃｈｉｃａｇｏ，ＵＳＡ，２０１３：５４５—５５３　［８４］　ＭｃＳｈｅｒｒｙ　Ｆ，Ｍｉｒｏｎｏｖ　Ｉ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ：ｂｕｉｌｄｉｎｇ　ｐｒｉｖａｃｙ　ｉｎｔｏ　ｔｈｅ　ｎｅｔ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　５ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｐａｒｉｓ，Ｆｒａｎｃｅ，２００９：６２７—６３６　［８６３　Ｍａｃｈａｎａｖ　ａｊｊｈａｌａ　Ａ，Ｋｏｒｏｌｏｖａ　Ａ，Ｓａｒｍａ　Ａ　Ｄ．Ｐｅｒｓｏｎａｌｉｚｅｄ　ｓｏｃｉａｌ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎｓ：ａｃｃｕｒａｔｅ　ｏｒ　ｐｒｉｖａｔｅ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２Ｏ１ｌ，４（７）：４４０　４５０　［８６３　Ｚｈｕ　Ｔ，Ｌｉ　Ｇ，Ｒｅｎ　Ｙ，ｅｔ　ａ１．Ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ　ｆｏｒ　ｎｅｉｇｈｂｏｒ—　ｈｏｏｄ—ｂａｓｅｄ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｊＩｔｅｒｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１３　ＩＥＥＥ／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋｓ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍｉｎｉｎｇ（ＡＳＯＮＡＭ）．Ｎｉａｇａｒａ　Ｆａｌｌｓ，　Ｃａｎａｄａ，２Ｏ１３：７５２—７５９　［８７］　Ｚｈｕ　Ｔ，Ｌｉ　Ｇ，Ｒｅｎ　Ｙ，ｅｔ　ａ１．Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｆｏｒ　ｔａｇｇｉｎｇ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１３　ＩＥＥＥ／ＷＩＣ／　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｅｂ　Ｉｎｔｅｌｌｉｇｅｎｃｅ．Ａｔｌａｎｔａ，　ＵＳＡ，２０１３（ｔｏ　ｂｅ　ａｐｐｅａｒｅｄ）　［８８］　ＭｃＳｈｅｒｒｙ　Ｆ，Ｍａｈａｊａｎ　Ｒ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｎｅｔｗｏｒｋ　ｔｒａｃｅ　ａｎａ１ｙｓｉｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ　ＳＩＧＣＯＭＭ　２０１０　Ｃｏｎｆｅｒ　ｅｎｃｅ．Ｎｅｗ　Ｄｅｌｈｉ，Ｉｎｄｉａ，２０１０：１２３—１３４　［８９］　Ｃｈｅｎ　Ｒ，Ｆｕｎｇ　Ｂ　Ｃ　Ｍ，Ｄｅｓａｉ　Ｂ　Ｃ，Ｓｏｓｓｏｕ　Ｎ　Ｍ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｔｒａｎｓｉｔ　ｄａｔａ　ｐｕｂｌｉｃａｔｉｏｎ：Ａ　ｃａｓｅ　ｓｔｕｄｙ　ｏｎ　ｔｈｅ　ｍｏｎｔｒｅａｌ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｓｙｓｔｅｍ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１８ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，２０１２：２１３－２２１　［９０］　Ｇｏｔｚ　Ｍ，Ｍａｃｈａｎａｖａｊｊｈａｌａ　Ａ，Ｗａｎｇ　Ｇ，ｅｔ　ａ１．Ｐｕｂｌｉｓｈｉｎｇ　ｓｅａｒｃｈ　Ｌｏｇｓ—————Ａ　ｃｏｍｐａｒａｔｉｖｅ　ｓｔｕｄｙ　ｏｆ　ｐｒｉｖａｃｙ　ｇｕａｒａｎｔｅｅｓ．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，　２０１２，２４（３）：５２０—５３２　［９１］　Ｋｉｆｅｒ　Ｄ，Ｍａｃｈａｎａｖ　ａｊｊｈａｌａ　Ａ．Ｎｏ　ｆｒｅｅ　ｌｕｎｃｈ　ｉｎ　ｄａｔａ　ｐｒｉｖａｃｙ／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１　１　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ａｔｈｅｎｓ，Ｇｒｅｅｃｅ，２０　１　１：　１９３—２０４　［９２３　Ｃｈａｎ　Ｔ＿Ｈ　Ｈ，Ｓｈｉ　Ｅ，Ｓｏｎｇ　Ｄ．Ｐｒｉｖａｔｅ　ａｎｄ　ｃｏｎｔｉｎｕａｌ　ｒｅｌｅａｓｅ　ｏｆ　ｓｔａｔｉｓｔｉｃｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｌｌｏｑｕｉｕｍ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｕｔｏｍａｔａ，Ｌａｎｇｕａｇｅｓ　ａｎｄ　Ｐｒｏｇｒａｍｍｉｎｇ．　Ｂｏｒｄｅａｕｘ，Ｆｒａｎｃｅ，２Ｏ１０：４０５—４１７　［９３］　ＭｃＧｒｅｇｏｒ　Ａ，Ｍｉｒｏｎｏｖ　Ｉ，Ｐｉｔａｓｓｉ　Ｔ，ｅｔ　ａ１．Ｔｈｅ　ｌｉｍｉｔｓ　ｏｆ　ｔｗｏ－ｐａｒｔｙ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｉｖａｃｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２０１０　ＩＥＥＥ　５１ｓｔ　Ａｎｎｕａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ．Ｌａｓ　Ｖｅｇａｓ，ＵＳＡ，２０１０：８卜９Ｏ　［９４３　Ｂｅｉｍｅｌ　Ａ，Ｎｉｓｓｉｍ　Ｋ，Ｏｍｒｉ　Ｅ．Ｄｉｓｔｒｉｂｕｔｅｄ　ｐｒｉｖａｔｅ　ｄａｔａ　ａｎａｌｙｓｉｓ：　Ｓｉｍｕｌｔａｎｅｏｕｓｌｙ　ｓｏｌｖｉｎｇ　ｈｏｗ　ａｎｄ　ｗｈａｔ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２８ｔｈ　Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｒｙｐｔｏｌｏｇｙ：　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ．Ｓａｎｔａ　Ｂａｒｂａｒａ，ＵＳＡ，２００８：４５１—４６８　［９５］　Ｇｅｈｒｋｅ　Ｊ，Ｈａｙ　Ｍ，Ｉ　ｕｉ　Ｅ，Ｐａｓｓ　Ｒ．Ｃｒｏｗｄ－ｂｌｅｎｄｉｎｇ　ｐｒｉｖａｃｙ／／　Ｓａｆａｖｉ—Ｎａｉｎｉ　Ｒ，Ｃａｎｅｔｔｉ　Ｒ　ｅｄｓ．Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ－　ＣＲＹＰＴＯ　２０１２．Ｈｅｉｄｅｌｂｅｒｇ，Ｇｅｒｍａｎ：Ｓｐｒｉｎｇｅｒ，２０１２：４７９—　４９６