基于K-匿名的隐私保护模型和算法研究

摘要

为了解决数据发布中存在的隐私泄露问题,Sweeney等人提出了 K-匿名模型。目前的研究中还没有能够对 K-匿名模型的匿名性进行定量分析的方法,本文拓展了信道模型,提出条件通道模型,从而定量分析模型的匿名度。此外,实现 K-匿名模型的算法无论是从效率还是信息损失度方面都还亟待提高,本文提出的子格二分法和过滤K-匿名算法正是从这两个方面入手来改进算法的。
　　针对不同的攻击方式,在K-匿名模型的基础上研究者提出了很多改进模型。我们希望能够对这些模型的匿名性进行定量地分析,以发现模型中存在的漏洞和不足。但是,目前的研究中几乎没有类似的方法来描述和分析 K-匿名模型。本文提出了更具通用性的条件信道模型,将匿名协议建模为信道,用矩阵描述信道,并用信道容量来衡量协议的匿名度。随后,我们利用这个信道模型检测了DC协议和K-匿名协议。验证结果表明,通过信道的容量,达到了定量分析匿名协议的目的,并能够有效地发现协议中存在的问题。
　　全域K-匿名算法通常是基于泛化格(Lattice)结构的,算法需要遍历整个格空间,其最耗时的部分是判断节点是否是 K-匿名节点。为了提高算法的运行效率,必须要减少判断节点的数量,同时还要保证结果是全局最优的。本文提出的子格二分搜索法,借鉴了二分法的思想,不同之处在于,在判断一个节点之后会根据判断的结果迭代遍历子泛化格,从而遍历整个初始泛化格,保证结果是全局最优的。并采用度优先的标准,选取下一个需要判断的节点,利用性质尽可能多地标记节点,达到减少计算 K-匿名节点的数量的目的。通过实验,我们将子格二分法与 Incognito算法进行了对比,事实证明我们的算法的确减少了计算节点的数量,最终提高了算法的运行效率。
　　由于K-匿名算法都存在着过度泛化的问题,文中我们提出一种叫做过滤 K-匿名的方法,沿着从最小泛化节点至最小K-匿名节点的路径,逐次泛化数据表,每次泛化时,只泛化不满足 K-匿名要求的记录,而不是整个数据表,直至所有记录都满足K-匿名要求。实验结果表明,多数情况下,在到达最小K-匿名节点之前,数据表已经满足K-匿名要求了,这种方法能大大降低信息损失量。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究背景及意义

1.2研究现状

1.3研究内容

1.4论文组织结构

第二章 K-匿名研究关键技术

2.1 K-匿名常用概念

2.2 K-匿名模型

2.3 K-匿名算法

2.4信息损失度量

第三章 基于信息理论的信道模型

3.1信息理论的信道模型

3.2信道模型的拓展和分析

3.3基于信息理论的DC协议

3.4基于信息理论的K-匿名协议

3.5本章小结

第四章 K-匿名算法的改进

4.1 K-匿名算法分析

4.2子格二分搜索法

4.3过滤K-匿名算法

4.4本章小结

第五章 K-匿名算法实验结果及分析

5.1实验准备

5.2子格二分法的实验结果及分析

5.3过滤K-匿名的实验结果及分析

5.4扩展性实验

5.5本章小结

第六章 总结和展望

参考文献

发表论文和参加科研情况说明

致谢