大数据隐私保护算法前沿 – 作者:mcvoodoo-安全小百科

一、背景

为了保护大数据隐私，这些年来已经开发出各种各样的方法。从数据生命周期来讲，在各阶段都有了一些方法沉淀。数据生成阶段，有使用访问限制和伪造数据技术。数据存储阶段主要基于加密技术，又分为基于身份的加密（IBE），基于属性的加密（ABE）和存储路径加密。此外为了保护敏感信息，也会使用混合云，敏感信息保存在私有云上。在数据处理阶段，包括隐私保护数据发布（PPDP）和聚合分析。在PPDP中，利用泛化和抑制等匿名技术来保护数据的隐私，可以进一步分为聚类，基于分类和关联规则挖掘的技术。虽然聚类和分类把输入数据分成不同的组，但基于关联规则挖掘可以在输入数据中找到有价值的数据。

二、隐私和安全

隐私是对如何收集和使用个人隐私信息有一定控制权的特权。安全是通过使用技术和流程来保护信息资产的保密性、完整性和可用性。

隐私关注于个人数据的使用和管理，确保个人信息以适当的方式被收集，共享和使用。安全更多地集中在保护数据免受恶意攻击、滥用和数据被盗。虽然安全性是保护数据的基础，但解决隐私问题还不够。

	隐私	安全
1	适当使用用户的信息	数据的机密性，完整性和可用性
2	决定个人信息去哪里的能力	确保安全策略被执行
3	通常适用于消费者保护信息的权利	提供保密性，安全系统的总体目标是保护企业或机构
4	隐私保护不佳，但安全还不错	没有良好的数据安全能力，隐私也好不了
5	用户网购的地址信息属于隐私，未取得用户同意则不能交给快递公司	使用加密、防火墙防止数据受到漏洞的影响

2.1、数据生成阶段

数据生成可以分为主动数据生成和被动数据生成。主动数据生成是数据所有者将数据提供给第三方，而被动数据生成是指数据所有者的在线操作（例如浏览），或数据拥有者可能不知道的数据收集。可以通过限制访问或伪造数据来最小化数据生成过程中的隐私风险。

1、访问限制：如果数据拥有者认为不应该共享，可以拒绝提供这些数据，例如在手机上对GPS的授权。如果数据所有者被动地提供数据，则可采取一些措施来确保隐私，如反跟踪扩展插件，脚本拦截，加密工具。

2、伪造数据：在有的场景下，完全拒绝敏感数据的访问是不现实的。在这种情况下可以伪造数据。以前有个例子，如果我在新浪注册账号，用户名就是张新浪，如果在网易注册，就叫王网易，这样一旦泄漏，就知道是谁出了问题。除此之外还可以利用以下技术来伪造数据：

Socketpuppet：隐藏个人在线身份，使用多个Socketpuppets，采集方不具备足够的知识把不同的信息与一个人联系起来，常见的场景比如利用马甲刷好评。可以参考https://en.wikipedia.org/wiki/Sockpuppet_(Internet)。

Mask Me：Chrome的插件，用户不需要通过键盘的完整输入，即可把一些敏感的字符快速地输入到表单，可以保护用户的隐私安全。

2.2、数据存储阶段

如果数据存储系统遭到攻击，个人信息可能会泄漏，而在分布式环境中，应用可能需要来自多个数据集，因此面临隐私保护的挑战。

传统的保护数据的安全机制可以分为四类：文件级、数据库级、介质级和应用级。为了提高扩展性，出现了存储虚拟化，可以把多个网络存储设备组合在一起，看起来像是单一存储设备。

1、云端隐私存储保护

当数据存储在云中时，机密性，完整性与数据隐私直接相关，大数据存储系统的基本要求是保护个人的隐私。主要方法包括：

–基于属性的加密访问控制。

–同态加密，可以部署在IBE或ABE中。

–存储路径加密，可以保护云端大数据的存储。

–混合云：内部部署，私有云和公共云服务结合在一起。

2、数据存储的完整性

由于云不能完全信任，为了确保数据安全，需要验证存储在云上的数据是完整的。传统系统中数据存储的完整性可以通过RS编码、校验和、单向陷门函数、消息认证码（MAC）和数字签名等多种方式进行验证。而要验证云中的数据的完整性，直接的方法是从云中检索所有数据，当所有数据完好无损时，才能算云提供了数据完整性。

2.3、数据处理

大数据处理过程大致包括batch, stream, graph，和机器学习。这里可分两步，第一步是保护信息不被泄漏，因为收集的数据可能包含敏感信息。第二步是从数据中提取有意义信息，而且同时不违反隐私要求。

三、传统大数据隐私保护方法

传统上也有一些大数据隐私保护方法，但其实都有不同的缺陷，因此也出现了新的技术。

1、去标识

主要用于数据挖掘的隐私保护。主要方法是泛化和抑制，泛化是降低粒度，比如工资用10-15k来表示。抑制则是删除，例如张**这种表示。但这不够，为了防止重新识别的风险，又出现了K匿名、L多样性、T-closeness。尽管如此，攻击者还可以通过外部信息来识别身份，因此去标识不足以保护大数据隐私。

方法	概念	局限性	计算复杂性
K匿名	发布的数据中，指定标识符（直接标识符或准标识符）属性值相同的每一等价类至少包含K个记录，使攻击者不能判别出个人信息所属的具体个体.	同质性攻击，背景知识	O(k logk)
L多样性	针对属性值差异性不大的数据集提出的一种增强概念。为防止确定性推导，L-多样性要求在K-匿名的基础上，实现每一等价类在每一敏感属性上存在至少L个不同值。	实现困难，不足以防止属性公开	O((n2)/k)
T-接近性	是L-多样性的增强概念，适用于发布数据集的敏感属性分布要尽可能贴近整个数据集的敏感属性分布。针对属性值分布不规则、属性值范围很小或者已被分类的数据集，为防止概率性推导，要求任何等价类中敏感属性的分布与整个数据集中相应属性的分布之间的距离小于阈值T。	要求任何等价类中敏感属性的分布接近整个数据敏感属性的分布。	2O(n)O(m)

2、HybrEx

混合执行模型的缩写，适用于混合云，利用非敏感的公有云，敏感数据和计算则在私有云上进行，在作业之前要考虑数据的敏感度。有四种类别的形式：

a模式：在公共云和私有云中执行MAP阶段，在私有云中执行Reduce。

b模式：Map和reduce在公有云中执行，使用公共数据作为输入，在它们之间混合中间数据并将结果存在公有云。

c模式：仅在公有云处执行Map阶段，而Reduce则在私有云中执行。

d模式：在公共云和私有云上执行map和Reduce,云之间的数据互相传输。

HybridEx也有问题，没有处理密钥的机制，并且只能用于云。

3、隐私聚合保护

隐私聚合保护主要方法是同态加密，给定一个同态公钥加密算法，不同的源可以使用相同的公钥把个人数据加密成密文。这些密文可以被聚合，并且聚合的结果可以通过相应的私钥恢复。但是，聚合只能针对特定目的。隐私聚合保护可以在收集和存储阶段使用，但由于其不灵活，不能运行复杂的数据挖掘。

4、加密数据操作

通过搜索加密数据，可以对加密数据操作，以保护大数据分析中的个人隐私。由于对加密数据的操作大多是复杂的，而且耗时长数据量大，所以在大数据的情况下对加密数据的操作可以被称为低效分析。

四、新兴大数据隐私保护方法

1、差分隐私

差分隐私是对数据发布时数据集中的隐私损失进行量化的数学模型。在数据集中增加了一定数量的“随机噪声”，这个噪声通过概率分布产生，噪声保证对隐私保护的同时，仍然具有分析价值。Apple就是用了差分隐私技术。

分析人员不能直接访问包含个人信息的数据，数据库和分析员之间引入了一个中介软件来保护隐私。首先分析人员通过privacy guard对数据进行查询，Privacy guard进行风险判断，从数据中获取结果。根据风险增加变形，提供给分析人员。

添加到的数据中的噪音和风险成正比，风险低则失真小，从而不会影响数据结果。但如果风险高，则会增加更多的噪声。噪声要精确控制到既不影响数据结果，又能保证隐私，是这里的关键要点。

2、Apriori算法

现有的隐私算法基本上都是通过添加噪声来保护隐私，但仍然可以通过关联的密集程度来发现真实关联关系。而Apriori算法可以用“大海捞针”来形容，意思为检测罕见的数据类。其他算法都要小心翼翼的控制噪声，因为噪声过大会影响结果，而这个算法则反过来，但成本是要增加很多计算量。

原理上是首先把原始数据添加噪声形成数据，随后添加算法代码提交给不可信的外部平台。最终返回的时候再使用算法消除噪声。

3、隐私保护大数据发布

隐私保护模型大致分为两种不同的类型，称为输入和输出隐私。输入隐私主要是指基于概率歪曲变换原始数据，在修改后的数据上进行挖掘，从而保护敏感信息，主要是k-匿名和l-多样性等模型发布匿名数据。输出隐私则在数据挖掘算法的输出时进行干扰或审计，以保护隐私。所以隐私发布的大部分工作其实就是保护隐私的同时，也保护数据的实用价值。解决方法上是将数据分成更小的片段，并且独立的对每个部分进行匿名化。

k-匿名可以防止身份攻击，但不能防止属性泄露攻击，因为等价类中敏感属性缺乏多样性。l多样性模型则要求每个等价类必须至少有l个代表性很好的敏感值。

4、k-匿名和l-多样性隐私模型的改进

MapReduce框架在处理数据时，先把数据分割成同等大小的块，然后发送给单独的mapper，mapper处理并提供Paris输出，具有相同key的转移到reducer。

（1）基于MapReduce的K匿名

由于数据是由MapReduce框架自动分割的，所以k-anonymization算法必须对mapper之间的数据分布不敏感，有点类似于Mondrian算法。为了增加通用性减少迭代成本，每个等价类在每次迭代中被划分为最多q等价类，而不是只有两个。

(2) 基于MapReduce的l多样性

从k-匿名到l-多样性的扩展，需要将敏感值集成到mapper的输出。因此需要对mapper和combiner生成的key进行修改。和k-匿名的mapper不同，在l-多样性中mapper同时接收准标识符和敏感属性作为输入。

5、流式大数据匿名化

流式大数据基本上是实时的，比如传感器数据，呼叫中心记录等、医学影像。所以对延迟、准确性和实时处理的要求比较高。匿名化静态数据的常用方法是k匿名，但这种方法不适用于流数据，有几个原因，首先k匿名是NP-hard问题，其次k-匿名为了减少信息损失，必须在匿名化过程中反复扫描数据，这在流处理中也是不可能的。尤其现在的数据量也越来越大，对匿名化算法的挑战也更大。

为了应对这些挑战，出现了FADS算法用来处理流数据，但也有缺点，这个算法对tuple顺序处理，但tuple超过阈值会被释放。因此在这个基础上产生了FAST算法，FAST支持并行扩展，同时使用主动启发式的循环来解决tuple过期问题。在实验环境下，确实比FADS更快，而且显著的降低了信息损失。

所谓主动启发式，是设立了一个可容忍最大延迟的参数，也就是到期时间参数。FADS则不检查tuple的阈值，所以导致了有些tuple会在到期后发布，既不能够实时而且也增加了计算成本。

6、方法总结

学术界在大数据隐私上近期提出的新方法和论文的比较：

论文题目	优点	局限性
Toward Efficient and Privacy Preserving Computing in Big Data Era	使用了保密余弦相似性计算协议，更高效	对特定数据隐私问题不足
Hiding a needle in a Haystack: privacy preserving Apriori algorithm in map reduce framework	Hadoop隐私挖掘技术，解决隐私问题的同时保证数据有效性	噪声大小影响了速度
Making big data, privacy, and anonymization work together in the enterprise: experiences and issues	结合匿名化，隐私保护和大数据技术分析使用数据并同时保护用户身份时遇到的经验和问题	使用易受相关攻击影响的K匿名方法
Microsoft Differential Privacy for Everyone	讨论并建议现有的差分隐私方法如何适用于大数据	取决于计算管理员的噪音量，如果计算管理员受到影响，整个系统就会失败
A scalable two-phase top-down specialization approach for data anonymization using MapReduce on cloud	提出了一种可扩展的两阶段自顶向下专门化（TDS）方法，利用云上的Map Reduce框架匿名化大规模数据集	使用易受相关攻击影响的匿名技术
HireSome-II: towards privacy-aware cross-cloud service composition for big data applications	基于以前的基本版本HireSome-I提出了一种隐私感知的跨云服务组合方法，名为HireSome-II（也就是基于历史记录的服务优化方法）
Protection of big data privacy	提出了处理大数据应用程序的各种隐私问题	客户细分分析很容易导致基于年龄性别，种族背景，健康状况，社会背景等的歧视
Fast anonymization of big data stream	提出了一种匿名算法（FAST）来加速大数据流的匿名化	设计和实施不完善。必须基于云的框架中实现，需要高计算能力和高可扩展性
Privacy preserving Ciphertext multi-sharing control for big data storage	提出了密文多共享机制	代理人攻击
Privacy-preserving machine learning algorithms for big data systems	隐私保护机器学习，其中训练数据是分布式的，每个共享数据部分都是大容量的	无法实现分布式功能选择
Privacy-preserving big data publishing	使用MapReduce进行隐私保护的数据挖掘方法	泛化不能处理高维数据，会降低数据效用。扰动也会降低数据的效用。
Proximity-aware local-recoding anonymization with map reduce for scalable big data privacy preservation in cloud	大数据局部编码建模为近距离感知聚类问题，并提出一种可伸缩的两阶段聚类方法	还未能和Apache集成
Deduplication on encrypted big data in cloud	通过基于所有权挑战和代理重新加密（PRE）的重复数据删除功能管理云中的加密大数据	融合加密（CE）受限于有安全限制，即离线易感性蛮力字典攻击
Security and privacy for storage and computation in cloud computing	不需要重新加密的安全数据共享，恶意内部人员的访问控制以及前向和后向访问控制	限制加密服务器中的信任级别