基于K匿名的隐私保护算法研究.doc

基于 K- 匿名的隐私保护算法研究秦晓薇，门爱华，邹妍（赤峰学院 计算机科学与技术系，内蒙古 赤峰 024000）摘 要：随着数据共享的出现与发展，如何合理地保护隐私数据，同时又保证数据的可用性，成为当今信息安全领域面临的重大挑战.K- 匿名是数据发布隐私保护的一种重要方法，它能够有效防止链接攻击所造成的隐私泄露问题. 基于 K- 匿名的隐私保护算法研究 秦晓薇，门爱华，邹 妍 （赤峰学院 计算机科学与技术系，内蒙古 赤峰 024000） 摘 要：随着数据共享的出现与发展，如何合理地保护隐私数据，同时又保证数据的可用性，成为当今信息安全领域面临 的重大挑战.K- 匿名是数据发布隐私保护的一种重要方法，它能够有效防止链接攻击所造成的隐私泄露问题. 本文阐述了 K- 匿名模型的基本思想，给出了模型的概念描述，给出了一些典型的实现算法，并对隐私保护的未来研究方向进行了展望. 关键词：K- 匿名；隐私保护；泛化；数据共享 中图分类号：TP311 文献标识码：A 文章编号：1673- 260X（2010）05- 0014- 03 况.在本例中，可以获得选民 Andre 的疾病情况.这就是一个 简单的链接攻击. 表 1 医疗信息数据表 1 引 言 随着互联网技术的飞速发展，数据共享为人们发布、检 索和使用数据带来了极大地便利，然而与此同时也带来了 隐私泄漏的安全隐患.已发布的数据经常会无意识地泄漏个 人隐私，这将对隐私数据所有者的利益造成严重的损害.因 此，如何在数据发布中对个人隐私数据进行合理的保护，又 保证数据的可用性，成为当今信息安全领域研究的热点. 在现实生活中，为了人口统计、医疗、卫生等研究需要， 一些机构经常要发布相关数据.虽然，在发布的数据中已经 隐匿了个人的标识信息，如姓名、身份证号码等属性，但是， 用户仍然可以通过对发布的数据和其他渠道获得的数据进 行链接处理，推演出隐私数据，从而造成隐私泄露，这就是 链接攻击[1].例如，某些属性具有较强的辨认性（如性别、出生 日期、邮编等），使得链接操作的结果只有一条或者几条，这 样目标信息的范围就会极大地缩小，从而泄露个人隐私.如 果在数据发布之前适当地作一些预处理，那么就可以减少 用户作链接操作时候导致这样信息泄露的可能，或者增加 非法用户猜测的难度. 1998 年，Samarati 和 L.Sweeney 提出了 K- 匿名模型，该 模型能够防止链接攻击所造成的隐私泄露问题，是隐私保 护的有效方法.本文阐述了 K- 匿名模型的基本思想，给出 了模型的概念描述，分析和评价了一些典型的实现算法，并 对 K- 匿名模型实现算法的未来研究方向进行了展望. 2 K-匿 名 模 型 2.1 基本思想 表 1 是某医院发布的医疗信息数据表，其中，不包含姓 名、身份证号码等能够唯一标识某个病人的属性. 如果用户在获得了表 1 的同时，又可以获得选民登记 表，如表 2 所示. 那么，通过两个表在属性{Sex，Birthdate， Zipcode}上的链接，就可以很容易的确定某个选民的疾病情 Birthdate Sex Zipcode Disease 1/21/76 2/28/76 2/28/76 1/21/76 4/13/86 4/13/86 Male Male Male Male Female Female 53715 53706 53703 53703 53725 53736 Flu Hang Nail Bronchitis Broken Arm Hepatitis Sprained Ankle 表 2 选民登记表 Name Birthdate Sex Zipcode Andre Beth Carol Dan Ellen 1/21/76 1/10/81 10/1/44 2/21/84 4/19/72 Male Female Female Male Female 53715 55412 90210 02174 02237 我们将表 1 中的属性分为敏感属性和非敏感属性.敏感 属性指对于相对应的个体来说是不愿意被其他人所知道 的，如 Disease，称为隐私属性.非敏感属性是那些可以与其 他数据表进行链接的属性，如 Birthdate，Sex 和 Zipcode，称为 准标识符. K- 匿名模型的基本思想就是设法切断准标识符与隐 私属性之间的一对一关系来保护隐私属性.数据持有者能够 识别出可以与外部信息相连接的准标识符，并通过检验原 始数据表中在准标识符上相同元组的个数来判断是否会造 成隐私泄漏.即要求所发布的数据表中的每一条记录 r，至少 有 K?1 条记录与 r 在准标识符上的投影值相等,称这样的数 定 义 1（属性 定 义 1（属性） 令 B(A1,…,An)是由有