大数据安全与隐私保护

本书结合作者在大数据安全与隐私保护领域的科研实践，提出大数据安全与隐私保护理论基础和技术体系框架，并对大数据安全与隐私保护面临的主要问题进行系统性阐述。本书重点介绍安全检索技术，隐私保护技术，安全存储与访问控制技术，以及安全处理技术，从技术核心贡献、领域发展综述以及1新研究进展等不同角度进行阐述，有助于感兴趣的读者较为全面地理解和把握这些技术。
本书可作为从事网络空间安全、信息安全和隐私保护研究的科研人员，网络空间安全、信息安全和密码学专业的研究生，以及相关专业的大学高年级本科生的教科书或参考资料。 

本书结合作者在大数据安全与隐私保护领域的科研实践，提出大数据安全与隐私保护理论基础和技术体系框架，并对大数据安全与隐私保护面临的主要问题进行系统性阐述。本书重点介绍安全检索技术、隐私保护技术、安全存储与访问控制技术，以及安全处理技术，从技术核心贡献、领域发展综述和*研究进展等不同角度进行阐述，有助于感兴趣的读者较为全面地理解和把握这些技术。
本书可作为从事网络空间安全、信息安全和隐私保护研究的科研人员，网络空间安全、信息安全和密码学专业的研究生，以及相关专业的大学高年级本科生的教科书或参考资料。

目 录
第1章绪论1
1.1大数据概述1
1.1.1大数据来源1
1.1.2大数据应用2
1.1.3大数据技术框架3
1.2大数据安全与隐私保护需求4
1.2.1大数据安全4
1.2.2大数据隐私保护5
1.2.3大数据安全与大数据隐私保护的区别与联系6
1.3大数据生命周期安全风险分析7
1.3.1数据采集阶段7
1.3.2数据传输阶段7
1.3.3数据存储阶段8
1.3.4数据分析与使用阶段8
1.4大数据安全与隐私保护技术框架8
1.4.1大数据安全技术8
1.4.2大数据隐私保护技术11
1.5大数据服务于信息安全14
1.5.1基于大数据的威胁发现技术14
1.5.2基于大数据的认证技术15
1.5.3基于大数据的数据真实性分析16
1.5.4大数据与“安全即服务”16
1.6基本密码学工具16
1.6.1加密技术16
1.6.2数字签名技术17
1.6.3Hash和MAC技术18
1.6.4密钥交换技术18
1.7本书的架构19
1.8注记与文献19
参考文献19
目 录〖4〗〖1〗第2章安全存储与访问控制技术23
2.1早期访问控制技术23
2.1.1几个基本概念24
2.1.2访问控制模型25
2.1.3局限性分析31
2.2基于数据分析的访问控制技术32
2.2.1角色挖掘技术32
2.2.2风险自适应的访问控制技术38
2.3基于密码学的访问控制技术45
2.3.1基于密钥管理的访问控制技术47
2.3.2基于属性加密的访问控制技术50
2.4注记与文献56
参考文献57
第3章安全检索技术61
3.1基本概念61
3.1.1背景介绍61
3.1.2密文检索概述62
3.1.3密文检索分类63
3.2早期安全检索技术64
3.2.1PIR技术64
3.2.2扩展： PIRK技术以及SPIR技术66
3.2.3ORAM技术66
3.3对称密文检索67
3.3.1概述67
3.3.2基于全文扫描的方案68
3.3.3基于文档关键词索引的方案69
3.3.4基于关键词文档索引的方案71
3.3.5扩展1： 多关键词SSE检索74
3.3.6扩展2： 模糊检索、Topk检索、多用户SSE76
3.3.7扩展3： 前向安全性扩展78
3.3.8小结79
3.4非对称密文检索80
3.4.1概述80
3.4.2BDOPPEKS方案80
3.4.3KRPEKS方案81
3.4.4DSPEKS方案82
3.4.5扩展： 多关键词检索、多对多PEKS83
3.4.6小结84
3.5密文区间检索85
3.5.1早期工作86
3.5.2基于谓词加密的方案87
3.5.3基于矩阵加密的方案90
3.5.4基于等值检索的方案94
3.5.5基于保序加密的区间检索95
3.5.6小结96
3.6注记与文献96
参考文献97
第4章安全处理技术103
4.1同态加密技术103
4.1.1同态加密105
4.1.2自举加密106
4.1.3类同态加密方案109
4.1.4全同态加密方案112
4.2可验证计算技术114
4.2.1几个基本概念115
4.2.2基于承诺的可验证计算119
4.2.3基于同态加密的可验证计算124
4.2.4基于交互的可验证计算131
4.3安全多方计算技术131
4.3.1安全两方计算134
4.3.2两方保密计算功能函数137
4.3.3安全多方计算141
4.4函数加密技术143
4.4.1函数加密的语法定义144
4.4.2函数加密实例145
4.4.3函数加密的语义安全性定义和构造147
4.4.4函数加密的模拟安全性定义和构造148
4.5外包计算技术151
4.5.1具有多个服务器的外包计算方案153
4.5.2具有两个服务器的外包计算方案153
4.5.3具有单一服务器的外包计算方案157
4.6注记与文献158
参考文献160
第5章隐私保护技术172
5.1基本知识172
5.2关系型数据隐私保护176
5.2.1身份匿名177
5.2.2属性匿名180
5.2.3最新进展182
5.3社交图谱中的隐私保护183
5.3.1概述183
5.3.2节点匿名184
5.3.3边匿名187
5.3.4属性匿名192
5.4位置轨迹隐私保护194
5.4.1面向LBS应用的隐私保护194
5.4.2面向数据发布的隐私保护198
5.4.3基于用户活动规律的攻击205
5.5差分隐私219
5.5.1基本差分隐私220
5.5.2本地差分隐私226
5.5.3基于差分隐私的轨迹隐私保护231
5.6注记与文献239
参考文献240

丛 书 序信息安全已成为国家安全的重要组成部分，也是保障信息社会和信息技术可持续发展的核心基础。信息技术的迅猛发展和深度应用必将带来更多难以解决的信息安全问题，只有掌握了信息安全的科学发展规律，才有可能解决人类社会遇到的各种信息安全问题。但科学规律的掌握非一朝一夕之功，治水、训火、利用核能曾经都经历了漫长的岁月。
无数事实证明，人类是有能力发现规律和认识真理的。今天对信息安全的认识，就经历了一个从保密到保护，又发展到保障的趋于真理的发展过程。信息安全是动态发展的，只有相对安全没有绝对安全，任何人都不能宣称自己对信息安全的认识达到终极。国内外学者已出版了大量的信息安全著作，我和我所领导的团队近10年来也出版了一批信息安全著作，目的是不断提升对信息安全的认识水平。我相信有了这些基础和积累，一定能够推出更高质量和更高认识水平的信息安全著作，也必将为推动我国信息安全理论与技术的创新研究做出实质性贡献。
本丛书的目标是推出系列具有特色和创新的信息安全理论与技术著作，我们的原则是成熟一本出版一本，不求数量，只求质量。希望每一本书都能提升读者对相关领域的认识水平，也希望每一本书都能成为经典范本。
我非常感谢清华大学出版社给我们提供了这样一个大舞台，使我们能够实施我们的计划和理想，我也特别感谢清华大学出版社张民老师的支持和帮助。
限于作者的水平，本丛书难免存在不足之处，敬请读者批评指正。

冯登国2009年夏于北京冯登国，中国科学院软件所研究员，博士生导师，教育部高等学校信息安全类专业教学指导委员会副主任委员，国家信息化专家咨询委员会专家，国家863计划信息安全技术主题专家组组长，信息安全国家重点实验室主任，国家计算机网络入侵防范中心主任。

前 言随着信息技术的发展和应用，人类社会所产生的数字信息不断加速并呈现爆炸式增长。作为信息载体的大数据的重要性不断凸显，已成为网络空间中重要的战略性资源。各类数据驱动的应用在金融、交通、能源、电信等国民经济重要行业、重大基础设施运行中发挥了重要作用，标志着人类社会正步入智能化时代。正因为大数据的价值举足轻重，所以在加快推动数据资源开放共享和应用开发的同时，必须构筑大数据安全保障体系，保护公民的隐私权和国家的大数据安全。如何应对大数据时代的数据安全与隐私保护问题，已成为当前的研究热点。
本书系统地介绍了大数据安全与隐私保护的相关概念、定义和技术，阐述了二者之间的联系和区别。本书具有以下特点：
（1） 系统性强。本书构建了大数据安全与隐私保护技术框架，针对大数据环境系统梳理了散见于各种文献中的有关理论与方法，将其归纳为安全存储与访问控制技术、安全检索技术、安全处理（也称安全计算）技术和隐私保护技术四大类，有助于读者建立对大数据安全与隐私保护的宏观认识，适合专业人员快速学习和系统掌握相关基础知识。
（2）  内容全面。本书内容不仅涵盖了大数据安全保护的各项关键技术，如安全存储与访问控制技术、安全检索技术以及同态加密、可验证计算等安全处理技术，还涵盖了用户数据隐私保护技术，如与社交网络大数据、位置轨迹大数据、差分隐私等相关的新型攻击与保护技术。
（3） 易于理解。对于重点介绍的安全存储与访问控制技术、安全检索技术、安全处理技术和隐私保护技术，本书从技术核心贡献、领域发展综述和最新研究进展等不同角度进行阐述，深入浅出，便于读者深入理解。
本书共5章。第1章介绍大数据的基本概念和随之带来的新型安全挑战，以及新的安全技术框架。第2章介绍大数据安全存储与访问控制技术，包括传统的访问控制技术及其发展，以及大数据时代访问控制技术面临的授权管理难度大、访问控制策略难以适用的新问题和解决方案。第3章和第4章针对大数据环境分别介绍数据的安全检索和安全处理技术，包括密文检索、同态加密、可验证计算、安全多方计算、函数加密和外包计算等技术。第5章介绍大数据场景下的隐私保护技术，包括攻击者针对用户身份隐私、社交关系隐私、属性隐私、轨迹隐私等进行的各类攻击和典型保护方法，以及目前引发高度关注的本地差分隐私保护技术。
本书由冯登国研究员规划和统稿。第1章由冯登国研究员执笔，第2章由李昊副研究员执笔，第3章由洪澄副研究员、迟佳琳博士和张敏研究员执笔，第4章由冯登国研究员执笔，第5章由付艳艳博士和张敏研究员执笔。
随着理论和技术的不断发展，社会和研究人员对数据安全和隐私保护的认识也在不断变化。在这种背景下，相关的研究和应用的边界也在飞速扩展，想要在一本书中覆盖大数据安全与隐私保护的整个研究领域的疆界也越来越困难。因此，本书难免存在不足之处，敬请读者多提宝贵意见。
本书得到了国家自然科学基金项目（U1636216） 的支持，得到了大数据安全与隐私保护讨论班的老师和同学们的帮助，也得到了清华大学出版社的大力支持，作者在此一并表示衷心的感谢。

冯登国2018年春节于北京前 言〖4〗〖1〗

第5章隐私保护技术内容提要： 随着计算机、移动互联网等技术的发展和应用，用户的电子医疗档案、互联网搜索历史、社交网络记录、GPS设备记录等信息的收集、发布等过程中涉及的用户隐私泄露问题越来越引起人们的重视。大数据场景下，多个不同来源的数据基于数据相似性和一致性进行链接，产生新的更丰富的数据内容，也给用户隐私保护带来更严峻的挑战。本章介绍围绕用户隐私的典型数据、隐私保护需求、相应的攻击和保护技术，包括传统人口统计数据中的用户身份攻击、社交网络中的用户社交关系和属性推测、位置社交网络中的用户隐私位置推测和活动规律挖掘，以及对应的隐私保护技术等。早期基于典型的数据库表结构数据的研究为新出现的社交网络数据和轨迹数据研究提供了经典模型，后续研究更针对后两者的独特数据特征和保护需求。差分隐私模型提出了目前最严格的隐私定义，并忽略了对数据内容、攻击者能力的假设，但对数据可用性具有一定影响。隐私保护技术需要立足于具体场景的数据构成，综合考虑用户的多种隐私信息间的相关性，结合多种技术，才能提供全面的隐私保护解决方案。
关键词： 身份隐私；社交关系隐私；属性隐私；轨迹隐私；链接攻击；同质攻击；近似攻击；k匿名；l多样化；t贴近；社交关系推测；马尔可夫模型；高斯混合模型；贝叶斯模型；活动建模；时空模型；差分隐私；本地差分隐私；Rappor协议；SH协议。
5.1基本知识
大数据时代，人类活动前所未有地被数据化。移动通信、数字医疗、社交网络、在线视频、位置服务等应用积累并持续不断地产生大量数据。以共享单车为例，截至2017年5月底，国内共享单车累计服务已超过10亿人次，注册用户超过1亿个。面向这些大规模、高速产生、蕴含高价值的大数据的分析挖掘不但为本行业的持续增长做出了贡献，也为跨行业应用提供了强有力的支持。共享单车的骑行路线在交通预测、路线推荐、城市规划方面具有重要意义［1］。
而随着数据披露范围的不断扩大，隐藏在数据背后的主体也面临愈来愈严重的隐私挖掘威胁，例如根据骑行路线推理个人用户的家庭住址、单位地址、出行规律，或者匿名用户被重新识别出来，进而导致“定制化”攻击，等等，为用户带来了极大损失。2017年6月1日起，最高人民法院、最高人民检察院联合发布的《关于办理侵犯公民个人信息刑事案件适用法律若干问题的解释》正式生效，其中对“非法获取、出售或者提供行踪轨迹信息、通信内容、征信信息、财产信息50条以上的”等10种情形明确入罪，体现了国家对个人信息保护的重视。
为满足用户保护个人隐私的需求及相关法律法规的要求，大数据隐私保护技术需确保公开发布的数据不泄露任何用户敏感信息。同时，隐私保护技术还应考虑到发布数据的可用性。因为片面强调数据匿名性，将导致数据过度失真，无法实现数据发布的初衷。因此，数据隐私保护技术的目标在于实现数据可用性和隐私性之间的良好平衡。
1. 数据隐私保护场景
一般来说，一个隐私保护数据发布方案的构建涉及以下4个参与方：
（1） 个人用户： 收集数据的对象。
（2） 数据采集/发布者： 数据采集者与用户签订数据收集、使用协议，获得用户的相关数据。数据采集者通常也负责数据发布(用户本地隐私保护情景除外)。根据数据发布的目的和限制条件,数据发布者对数据进行一定的处理并以在线交互或离线非交互方式提供给数据使用者，在进行数据处理时还须预防潜在的恶意攻击。
第5章隐私保护技术〖4〗〖1〗大数据安全与隐私保护（3） 数据使用者： 任意可获取该公开数据的机构和个人。数据使用者希望获得满足其使用目的的尽可能真实有效的数据。
（4） 攻击者： 可获取该公开数据的恶意使用者。攻击者可能具有额外的信息或者知识等，试图利用该公开数据识别特定用户身份，获取关于某特定用户的敏感信息，进而从中牟取利益。
攻击者的能力可分为两类。一类是背景知识（background knowledge），通常是关于特定用户或数据集的相关信息。如攻击者可能知道Amanda是部门经理，Alice是营业员，Bill的出生日期是1976年12月1日。背景知识的获得完全基于攻击者对具体攻击目标的了解，攻击者可以利用其掌握的背景知识，在公开发布的数据中识别出某个特定用户。另一类是领域知识(domain knowledge)，指关于某个领域内部的基本常识,通常具有一定的专业性。例如，医学专家可能了解不同区域人群中某种疾病的发病率。当攻击者将目标范围缩小到有限的记录集时，攻击目标可能患有的疾病也仅限于记录集中的几种。具有医学知识的攻击者可以根据攻击目标的地域推理出其可能患有的疾病。
图51数据隐私场景示意图在实际场景中，数据采集/发布者隐私保护方案可选择在线模式或离线模式。在线模式又称“查询问答”模式，对用户所访问的数据提供实时隐私保护处理。在在线模式（图51（a））下，通过数据发布者的调控，数据被收集的个人用户和期望获得真实数据的使用者之间应能够就数据的使用目的、范围、限制情况达成一致。但在线模式对算法性能要求较高。离线模式（图51（b））是指在对所有数据统一进行隐私保护处理后批量发布。数据一旦公开发布，数据发布者和数据被收集的个人用户就失去了对数据的监管能力。任意获得该公开数据的第三方，包括恶意攻击者在内，都可以对这些数据进行深入分析。因此，在离线模式下，数据发布者应力求提前预测攻击者的所有可能攻击行为，并采取有针对性的防范措施。即使无法对攻击者的所有行为进行预测，数据发布者也应重点关注个人用户最基本的隐私保护需求，并进行对应的保护方案设计和攻击预防，从而避免对个人用户的隐私造成严重侵害。本章主要讨论离线模式数据发布场景。
2. 隐私保护需求
用户隐私保护需求可分为身份隐私、属性隐私、社交关系隐私、位置与轨迹隐私等几大类。
（1） 身份隐私。它是指数据记录中的用户ID或社交网络中的虚拟节点对应的真实用户身份信息。通常情况下，政府公开部门或服务提供商对外提供匿名处理后的信息。但是一旦分析者将虚拟用户ID或节点和真实的用户身份相关联，即造成用户身份信息泄露（也称为“去匿名化”）。用户身份隐私保护的目标是降低攻击者从数据集中识别出某特定用户的可能性。
（2） 属性隐私。属性数据用来描述个人用户的属性特征，例如结构化数据表中年龄、性别等描述用户的人口统计学特征的字段。宽泛地说，用户购物历史、社交网络上用户主动提供的喜欢的书、音乐等个性化信息都可以作为用户的属性信息。这些属性信息具有丰富的信息量和较高的个性化程度，能够帮助系统建立完整的用户轮廓，提高推荐系统的准确性等。然而，用户往往不希望所有属性信息都对外公开，尤其是敏感程度较高的属性信息。例如，某些视频观看记录被公开会对用户的形象造成不良影响。但是，简单地删除敏感属性是不够的，因为分析者有可能通过对用户其他信息（如社交关系、非敏感属性、活动规律等）进行分析、推测将其还原出来。属性隐私保护的目标是对用户相关属性信息进行有针对性的处理，防止用户敏感属性特征泄露。
（3） 社交关系隐私。用户和用户之间形成的社交关系也是隐私的一种。通常在社交网络图谱中，用户社交关系用边表示。服务提供商基于社交结构可分析出用户的交友倾向并对其进行朋友推荐，以保持社交群体的活跃和黏性。但与此同时，分析者也可以挖掘出用户不愿公开的社交关系、交友群体特征等，导致用户的社交关系隐私甚至属性隐私暴露。社交关系隐私保护要求节点对应的社交关系保持匿名，攻击者无法确认特定用户拥有哪些社交关系。
（4） 位置轨迹隐私。用户位置轨迹数据来源广泛，包括来自城市交通系统、GPS导航、行程规划系统、无线接入点以及各类基于位置服务的APP数据等。用户的实时位置泄露可能会给其带来极大危害，例如被锁定并实施定位攻击。而用户的历史位置轨迹分析也可能暴露用户隐私属性、私密关系、出行规律甚至用户真实身份，为用户带来意想不到的损失。用户位置轨迹隐私保护要求对用户的真实位置进行隐藏或处理，不泄露用户的敏感位置和行动规律给恶意攻击者，从而保护用户安全。
从数据类型角度看，用户隐私数据可表示为结构化数据或非结构化数据。通常，用户的属性信息（如年龄、性别、购物记录等）属于典型的结构化数据，可表示为数据库表；用户位置、轨迹数据一般以点集的形式表示，也属于结构化数据。而用户社交关系数据则表现为相对复杂的网络关系，属于非结构化数据，一般用图结构表示。图52中展示了基本数据类型。为了表达两者之间的关联，后文中将用户隐私表示为“属性图”结构。
图52基本数据类型
除了数据类型不同，用户的关系型表数据、位置轨迹数据、社交结构数据在各自的数据维度上也具有明显不同的特性。数据表中的一条记录通常只代表一个用户，用户间的相关性较弱。记录之间的相关性基本上只与其所处的统计分组有关，属性之间的相关性只与整个表呈现出的数据分布有关。个人的位置轨迹数据通常是一系列长度不定的点集序列，具有明显的时间顺序和周期重复特征，反映了个人运动规律，使得用户的运动轨迹易于被预测，而难以合理、高效地彻底隐藏。社交网络数据中除了属性数据，还具有复杂的边连接。在这种场景中，用户通过边连接进行影响力传播和相似性传递，最终导致“朋友的朋友也是我的朋友”的局部相似性日益凸显，使得用户的属性、社交关系甚至身份容易从局部社区中被推测出来。隐私保护技术必须针对不同数据的特征进行处理，才能实现期望的隐私保护效果。
3. 隐私保护技术分类
前面提到，数据隐私保护的目标在于实现数据可用性和隐私性之间的良好平衡。因此，一个隐私保护方案有明确的隐私保护目标与可用性目标。
当前的隐私保护模型有两大类： 以k匿名为代表的基于等价类的方法和差分隐私方法。前者假设攻击者能力有限，仅能将攻击目标缩小到一定的等价类范围内，而无法唯一地准确识别攻击目标；后者则假设可能存在两个相邻数据集，分别包含或者不包含攻击目标，但攻击者无法通过已知内容推出两个数据集的差异，因此，也无法判断攻击目标是否在真实数据集中。前者的优势在于，在攻击者能力不超过假设的前提下，能够以较小的代价保证同一等价类内记录的不可区分性。而如果攻击者能力超过了假设，攻击者就能够进一步区分等价类内的不同记录，从而实现去匿名化。后者的优势在于，攻击者不可能具有超过假设的攻击能力，因而不可能突破差分隐私方法提供的匿名保护。但是，由于数据集的差异性，差分隐私方法可能会对原始数据造成较大扰动，过度破坏数据可用性。
典型的隐私保护技术手段包括抑制(suppression)、泛化(generalization)、置换(permutation)、扰动(perturbation)、裁剪(anatomy)等。此外，也有人通过密码学手段实现隐私保护。
（1） 抑制是最常见的数据匿名措施，通过将数据置空的方式限制数据发布。
（2） 泛化是指通过降低数据精度来提供匿名的方法。属性泛化即通过制定属性泛化路径，将一个或多个属性的不同取值按照既定泛化路径进行不同深度的泛化，使得多个元组的属性值相同。最深的属性泛化效果通常等同于抑制。社交关系数据的泛化则是将某些节点以及这些节点间的连接进行泛化。位置轨迹数据可进行时间、空间泛化。
（3） 置换方法不对数据内容作更改，但是改变数据的属主。例如，将不同的个人用户的属性值互相交换，将用户a与b之间的边置换为a与c之间的边。
（4） 扰动是在数据发布时添加一定的噪声，包括数据增删、变换等，使攻击者无法区分真实数据和噪声数据，从而对攻击者造成干扰。
（5） 裁剪技术的基本思想是将数据分开发布。例如，对于表结构数据，首先将用户划分为不同的组，赋予同一组的记录相同的组标识符(group id)，对应记录的敏感数据也赋予相同的组标识符，然后将准标识符（如地域、性别等）和敏感数据分别添加组标识符作为两张新表发布。恶意攻击者即使可以确定攻击目标的组标识符，但是无法有效地从具有相同组标识符的敏感数据中判定攻击目标对应的敏感数据。
（6） 密码学手段利用数据加密技术阻止非法用户对数据的未授权访问和滥用。
隐私保护方案需要引入可用性标准。一种通用的机制是度量数据失真程度，并不考虑发布的数据被如何使用。通过定义一系列数据集属性特征，比较真实数据和数据发布版本的特征变化来衡量数据损失程度。例如，对于关系型数据表中的数值型数据，计算其平均值的偏移量。如果数据有明确的应用领域，例如对数据进行统计分析、计算均值、找出Topk对象等，那么可用性指标可以更具体化，表示为计算结果的准确度。
5.2关系型数据隐私保护
2002年，Sweeney［2,3］提出了k匿名模型，这是第一个真正意义上完整的隐私保护模型。这一方案能够杜绝攻击者唯一地识别出数据集中的某个特定用户，使其无法进一步获得该用户的准确信息，能够提供一定程度的用户身份隐私保护。在Sweeney提出的隐私方案中明确了对数据可用性和用户隐私性的保证。此外，人们还关注表结构数据中的用户敏感属性的隐私保护需求。根据敏感属性的分布情况，人们提出了l多样化、t贴近模型。这些方法为后续社交网络隐私保护与位置轨迹隐私保护奠定了基础。
本节主要介绍早期的表结构数据研究中的身份匿名和属性匿名方法、一些常见的攻击方法以及数据连续发布场景中的问题与解决方案。
5.2.1身份匿名〖*2〗1. 链接攻击与身份匿名简单地去标识符匿名化仅仅去除了表中的身份ID等标志性信息，攻击者仍可凭借背景知识，如地域、性别等准标识符信息，迅速确定攻击目标对应的记录。此类攻击称为记录链接(record linkage)攻击，简称链接攻击。如表51所示，原始用户医疗记录表中包含了Name(用户姓名)这一标识符，简单删除标识符列之后可以得到如表52所示的匿名记录表。如果攻击者持有公开的选民记录表作为背景知识（表53），与公开发布的匿名记录表对比，通过Z(邮编)、Age（年龄）等若干项属性信息，攻击者仍可以唯一地识别出某些用户。例如，可推断出第2条记录对应的用户是Bob。表51原始的用户医疗记录表
IdentifierQuasiidentifierSensitive Data#NameZIPAgeNationalityCondition1Kumar1305328IndianHeart Disease2Bob1306729AmericanHeart Disease3Ivan1305335CanadianViral Infection表52匿名后的用户医疗记录表
QuasiidentifierSensitive Data#ZIPAgeNationalityCondition11305328IndianHeart Disease21306729AmericanHeart Disease31305335CanadianViral Infection表53选民记录表
NameZIPAgeSexVoteNatalia1305328FemaleYesBob1306729MaleYesLisa1305335FemaleNoUmeko1306736FemaleYes2. k匿名基本模型
为避免攻击者通过链接攻击从发布的数据中唯一地识别出特定匹配用户，导致用户身份泄露，Samarati和Sweeney最早提出了适用于关系型数据表的k匿名（kanonymity）模型［2,3］。这一方案按照准标识符将数据记录分成不同的分组，且每一分组中至少包含k条记录。这样，每个具有某个准标识符的记录都至少与k-1个其他记录不可区分，从而实现用户身份匿名保护。
定义51（k匿名）令T(A1,A2，…,An)为一张行数有限的表，属性集合为{A1,A2，…，An}。QIT为表中的准标识符QIT={Ai,Ai 1,…,Aj}。表T满足k匿名，当且仅当每一组准标识符的取值序列在T［QI］中出现至少k次。
为了让发布的数据满足k匿名需求，Samarati和Sweeney给出了相应的数据处理方法，提出了一种通过元组泛化实现k匿名的解决方案。
属性A的泛化函数可表示为f:A→B。属性A的持续泛化过程可表示为域泛化层次结构（domain generalization hierarchy）DGHA，通过一组函数fh（h=0,1，…,n-1） 的作用，实现从属性A的所有取值泛化到“任意”或者“”的完整泛化路径： A0f0A1f1…fn-1An。其中A0=A，An|=1。例如，ZIP编码可由具体的02138逐步或直接泛化为不具体的0213、021、02、0、。出生年份可由精确的1965泛化为1960—1970、1950—1970。泛化路径的属性值之间存在偏序关系。对于属性A的两个泛化值vi和vj，若i≤j且fj-1…fivi…=vj，那么vi和vj存在偏序关系，表示为vivj。
显然在泛化层次树中，离树根越近的节点泛化程度越高，对数据的破坏越大。为了在数据处理过程中尽可能保持数据可用性，同时，尽快满足k个相同记录的需求，Sweeney等人提出了k匿名最小泛化的概念。
定义52（k匿名最小泛化）令T1(A1,A2,…,An)和Tm(A1,A2,…,An)分别为两张表，其准标识符均为QIT={Ai,Ai 1,…,Aj}，且T1QITTmQIT。称Tm是表T1的k匿名最小泛化，当且仅当满足以下两个条件：
（1） Tm在定义的准标识符QIT上符合k匿名模型。
（2） Tz： T1≤Tz，TzTm，如果Tz也满足k匿名模型，那么必然有TzQIT=TmQIT。
在存在多种符合k匿名模型的最小泛化的场景中，需要进一步比较泛化过程中的数据扰动来选取最优的泛化方案。为此，Sweeney等人定义了数据准确度Prec来衡量泛化过程中的信息变化以及定义最小扰动的概念。
定义53（数据准确度Prec)令PT为原始数据表。表PT的准标识符由Na个属性{A1，A2,…,ANa}组成，共包含N条记录，tpj为表PT中的第j条记录。RT为PT的一个泛化表，trj为与表PT中tpj对应的泛化后记录。hji为trj中属性Ai的泛化结果trj［Ai］处于该属性的泛化层次结构的路径深度。DGHAi为属性Ai泛化层次结构的高度。RT的数据准确度由下式确定：Prec（RT）=1-∑Nai=1∑Nj=1hji|DGHAi|N·Na定义54（最小扰动）令T1(A1,A2，…,An)和Tm(A1,A2，…,An)分别为两张表，其准标识符均为QIT={Ai,Ai 1,…,Aj}，且T1QITTmQIT。x=i,i 1,…,j，DGHAx是准标识符QIT的域泛化层次结构。称 Tm是表T1符合k匿名模型的最小扰动，当且仅当满足以下两个条件：
（1） Tm在定义的准标识符QIT上符合k匿名模型。
（2） Tz： Prec（T1）≥Prec（Tz），Prec（Tz）≥Prec（Tm），如果Tz也满足k匿名模型，那么必然有TzQIT=TmQIT。
根据定义，若PT中的记录未经过泛化，则任意记录的准标识符属性h=0，Prec(PT)=1。在另一种极端情况下，RT中的准标识符属性均泛化到层次结构的根节点，那么h=|DGH|，Prec(RT)=0。在实际数据隐私处理的过程中，数据发布者希望获得较高的数据准确度，就必须尽可能少地进行数据泛化，也就是说，使得数据泛化的位置尽可能离泛化层次结构的根节点更近，以实现最小扰动。
Sweeney等人设计了一种最小扰动的k匿名泛化算法。该算法包括如下两个步骤：
（1） 判断PT是否符合k匿名模型，如果是，输出PT，否则进入第（2）步。
（2） 执行如下操作：
（2.1） 生成PT的所有可能的泛化表集合，记为allgens。
（2.2） 检测allgens中符合k匿名模型的泛化表，将该集合记为protected。
（2.3） 保存protected中符合最小扰动的泛化表，记为MGT。
（2.4） 根据用户定义的偏好，从MGT中输出唯一的符合用户偏好的最小扰动输出。
在基本k匿名算法的基础上，Lefevre等人［4］提出了一个基于贪心算法的改进方案，重点优化了寻找最小扰动的过程，算法的效率有了很大提高。Bayardo等人［5］给出了基于数据拆分发布和元组抑制的解决方案。
3. k匿名模型的局限性
用户购物历史、观影历史等数据虽然也可以用数据表的形式表示，但是，这类数据中不存在严格的准标识符信息。因为数据发布方无法准确界定哪一条购买记录和用户评价信息是用户的准标识符信息，任何非特定记录都可能被攻击者用来重新识别出用户身份。很显然，基础的k匿名模型的适用范围并不包括这类数据，而是仅限于能准确定义准标识符属性的关系型表结构数据。
2006年Netflix的用户隐私泄露事件就是由于公开的用户观影记录匿名程度不足而导致部分用户的身份泄露。Narayanan等人随后在2008年的S&P会议上公开了他们利用IMDB数据库对Netflix数据进行链接攻击的方法［6］。该文直观地展示了k匿名模型的不足。
首先，该文定义了一个简单的打分比较算法。假设当前攻击者获得了关于某个特定攻击目标的额外信息，需要根据这些信息判定攻击目标与当前待定用户r′的相似度。打分算法就是用来计算当前掌握的关于攻击目标的额外信息aux和待定用户r′的所有属性的相似程度：Score(aux，r′)=mini∈supp(aux)Sim(auxi,r′i)这个算法比较了攻击目标的额外信息aux和待定用户r′的所有属性，并将属性相似性分值最小的记为两者的相似性打分。这里采用的Sim函数求得的是余弦相似性。在这种思想下，如果两个“用户”aux和r′在某个属性上差异特别巨大，那么这两者基本不可能是同一个用户。但如果额外信息aux或者待定用户r′中的某个属性出现错误，就很容易导致两者的相似性打分非常低，所以将相似性打分公式更新为Score(aux，r′)=∑i∈supp（aux）wt(i)Sim(auxi,r′i)其中，wt（i）=1log |supp(i)|，log |supp(i)|为r′所处的数据集中具有属性i的用户数。在这种情况下，越稀有的属性权重越高，两个“用户”的加权相似性最高，那么他们就可能是同一个用户的两个id。
基于这个打分算法，Narayanan等人选取了IMDB数据集中的50个用户和Netflix公开数据集的用户进行了打分匹配。他们利用IMDB数据集中的用户观影打分作为额外信息。实验发现，如果用户在Netflix和IMDB发布的影片评分相同，并且日期相差不远，此类评分越多，用户账户越容易匹配。实验同时还发现，如果用户评分的电影越小众，他也越容易被识别，也符合打分公式中较少的人具有的属性权重较大的设置。在该文中，Narayanan等人指出，在实际的多维数据发布场景中，数据通常很稀疏，攻击者可能只需要掌握很少的属性（5～10个非热门电影），就能识别出大量用户。实际上也就是说，与用户具有相同属性的人越少，用户的唯一性越强，该用户越容易被识别。
Narayanan等人的研究实际上也表明，受限于攻击者掌握的额外信息，只要用户能够和k个其他用户具有相同的观影历史，实际上攻击者是没有办法区分他们的。虽然攻击者无法确定到底哪一个id是他的攻击目标，但是实际上他已经获得了该用户的所有观影历史，也达到了一定的攻击目标，即使其达到的攻击目标与用户身份无关。
除了需要解决k匿名模型本身的缺陷导致数据匿名不足的问题，当前的数据隐私保护方案还需要抗衡数据去匿名算法的攻击。随着大数据技术的不断发展，数据持有者自然地希望获得更多用户数据以综合分析并发掘其中的价值。在这种场景下，首先需要实现多源数据中的用户重识别，进而实现用户数据融合。多源数据融合场景中的用户重识别实际上就是根据异源数据的额外信息确定用户身份的去匿名化攻击过程。根据异源数据的来源和精确程度不同，去匿名化攻击可分为3种： 基于特定模式精确匹配的去匿名、基于种子匹配的去匿名和基于相似度匹配的去匿名。
基于特定模式精确匹配的去匿名算法无法抵抗噪声影响。一旦数据经上述某种匿名化算法引入噪声，就不再有效了。
上文提到的针对Netflix数据的攻击实际上是一种基于种子匹配的去匿名攻击。在这类方案中，攻击者首先需要了解一定数量的用户在两个图之间的节点对应关系（种子匹配）。算法从种子匹配出发，计算不同网络中的连接节点间的相似度，并将相似节点进行匹配，从而实现多网络间用户身份的重识别。
基于相似度匹配是在不具有先验知识（种子数据）的情况下普遍采用的去匿名方法。Cao等人［7］基于MapReduce框架进行异源轨迹数据的用户重识别。数据预处理把轨迹处理为停留点（stay point） 集合，然后对比潜在用户的SIG（signal based similarity）判断这些用户是否为同一个人。在这个模型中，将用户停留点分为核心地点和普通地点，核心地点发出刺激信号，普通地点不发出信号，而是收到随距离衰减的刺激信号。两个用户轨迹中的点的SIG相似性越高，越可能是同一个人在不同数据源留下的轨迹。
综上所述，可以看到，k匿名模型的相关研究实际上陷入了很大的困境。正如上文所述，k匿名模型仅适用于存在明确准标识符的数据，而不适用于当前大数据时代规模庞大的非表结构数据，其使用范围有限。其次，大量的去匿名算法试图通过模糊的种子匹配和相似度匹配算法识别出最相近的用户，从而避免了k匿名算法对精确匹配算法造成的干扰，仍旧泄露了用户的特征，大大削弱了k匿名算法的保护能力。但k匿名模型作为经典的身份隐私保护模型仍在实际隐私保护应用中发挥作用，可为用户提供一定的隐私保护。
5.2.2属性匿名〖*2〗1. 同质攻击在5.2.1节中讨论的k匿名模型能够用来防止链接攻击，避免攻击者唯一地识别出攻击目标。那么，在发布的匿名数据满足k匿名模型的情况下，是不是攻击者就不能从中推测出用户的其他隐私信息？在经过k匿名处理后的数据集中，攻击目标至少对应于k个可能的记录。但这些记录只满足准标识符信息一致的要求，而非准标识符数据和敏感数据保持不变。正如在5.2.1节分析Netflix隐私泄露事件时所讨论的，如果这k个用户的观影记录相同或非常接近，攻击者也能够获得用户的所有观影历史，分析用户的隐私属性。例如，这k个用户都喜欢看海洋纪录片，分析的结果是攻击目标可能是环保主义者。在k匿名的数据记录中，如果记录的敏感数据接近一致或集中于某个属性，攻击者也可以唯一或以极大概率确定数据持有者的属性。这类攻击称为同质攻击。
2. k匿名模型的变体
人们首先在k匿名模型的基础上进行了一系列改进，试图抵抗同质攻击。
Zhang等人［8］提出了(k,e)匿名模型，主要处理数值型敏感属性数据。(k,e)匿名的思想是： 要求每个等价类中元组个数至少是k个，同时等价类中敏感属性取值范围不能小于给定的阈值e，也就是要求等价类中敏感属性的最大值与最小值的差至少是e。
Wang等人［9］提出了（X,Y）匿名的概念。其中，X、Y 为不相交的属性集。在这种方案中，讨论了数据库表中多条记录代表同一个数据持有者的情况。在此类情况下，多条记录的准标识符值相同或者基本相同，很有可能被划分到同一等价类中。简单的k匿名要求难以实现对用户隐私的保护。为此，他们提出，在属性组X中的属性均相同的情况下，每一组X均需对应至少k个不同的敏感属性组Y中的值。这种方案在普通k匿名的基础上增加了对敏感数据的限制条件。因此，能够提供比k匿名更好的保护。
为避免用户敏感属性被推测，在社交网络中出现大量基于k匿名聚类的改进算法。Ford等人［10］提出了psensitive kanonymity方法，要求聚类中节点数大于或等于k，并且不同敏感值属性个数大于或等于p。Sun［11］在此基础上提出了p sensitive kanonymity方法，该方法采用敏感属性值的类别概念，要求敏感属性值的类别至少出现p类。
3. l多样化模型
Machanavajjhala等人 ［12］提出了l多样化（ldiversity）这一新的模型，要求在准标识符相同的等价类中，敏感数据要满足一定的多样化要求。他们通过熵来定义数据的多样化程度，提出了熵l多样化（entropy ldiversity)的概念。
定义55（熵l多样化）如果对每一个泛化的q条记录组，满足-∑s∈Sp(q,s)logp(q,s)≥logl，那么该表满足熵l多样化。
其中p(q,s′)=n(q,s)∑s∈Sn(q,s′)为q记录组中敏感值等于s的记录所占的比例。但是，这一要求过于严格。如果表格中90%的用户敏感属性都是“健康”，q记录组的熵l多样化很可能只有极少数不是“健康”，从而使得该q记录组无法满足熵l多样化的要求。
递归（c,l）多样化（recursive(c,l)diversity)在此基础上降低了多样性的要求，并假设不会影响到用户隐私的属性可以公开，不将其作为敏感值进行保护，例如用户“健康”这一属性值。
定义56（递归(c,l)多样化）将每一个q元组中用户敏感值按照出现的频繁程度降序排列，其出现次数分别为r1,r2，…，rm，如果对每一个q元组，存在r1