基于LBS(位置服务)的隐私保护算法研究 .pdfVIP

基于LBS(位置服务)的隐私保护算法研究

黄小英

【摘要】随着数据挖掘和数据发布等数据库应用的出现与发展,如何保护隐私数据

和防止敏感信息泄露成为当前面临的重大挑战.隐私保护技术需要在保护数据隐私

的同时不影响数据应用.根据采用技术的不同,出现了数据失真、数据加密、限制发

布等隐私保护技术.

【期刊名称】《制造业自动化》

【年(卷),期】2011(033)009

【总页数】3页(P96-98)

【关键词】隐私保护;随机化;安全计算

【作者】黄小英

【作者单位】广西工商职业技术学院,南宁,530003

【正文语种】中文

【中图分类】TP312

数据挖掘和数据发布是当前数据库应用的两个重要方面。一方面，数据挖掘与知识

发现在各个领域都扮演着非常重要的角色。数据挖掘的目的在于从大量的数据中抽

取出潜在的、有价值的知识（模型或规则）。传统的数据挖掘技术在发现知识的同

时，也给数据的隐私带来了威胁。另一方面，数据发布是将数据库中的数据直接地

展现给用户。而在各种数据发布应用中，如果数据发布者不采取适当的数据保护措

施，将可能造成敏感数据的泄漏，从而给数据所有者带来危害。所以，如何在各种

数据库应用中保护数据的隐私，成为近年来学术界的研究热点。

没有任何一种隐私保护技术适用于所有应用。隐私保护技术分为三类：

1）基于数据失真（Distorting）的技术：使敏感数据失真但同时保持某些数据或

数据属性不变的方法。例如，采用添加噪声（AddingNoise）、交换

（Swapping）等技术对原始数据进行扰动处理，但要求保证处理后的数据仍然可

以保持某些统计方面的性质，以便进行数据挖掘等操作。

2）基于数据加密的技术：采用加密技术在数据挖掘过程中隐藏敏感数据的方法。

多用于分布式应用环境中，如安全多方计算（SecureMultipartyComputation，

以下简称SMC）。

3）基于限制发布的技术：根据具体情况有条件地发布数据。如：不发布数据的某

些域值，数据泛化（Generalization）等。

隐私保护技术需要在保护隐私的同时，兼顾对应用的价值以及计算开销。通常从以

下三方面对隐私保护技术进行度量：

1）隐私保护度：通常通过发布数据的披露风险来反映，披露风险越小，隐私保护

度越高。

2）数据缺损：是对发布数据质量的度量，它反映通过隐私保护技术处理后数据的

信息丢失：数据缺损越高，信息丢失越多，数据利用率（Utility）越低。具体的度

量有：信息缺损（InformationLoss）、重构数据与原始数据的相似度等。

3）算法性能：一般利用时间复杂度对算法性能进行度量。例如，采用抑制

（Suppression）实现最小化的k-匿名问题已经证明是NP-hard问题；时间复杂

度为O(k)的近似k-匿名算法，显然优于复杂度为O(klogk)的近似算法。均摊代价

（AmortizedCost）是一种类似于时间复杂度的度量，它表示算法在一段时间内

平均每次操作所花费的时间代价。除此之外，在分布式环境中，通讯开销

（CommunicationCost）也常常关系到算法性能，常作为衡量分布式算法性能

的一个重要指标。

数据失真技术通过扰动（Perturbation）原始数据来实现隐私保护。它要使扰动

后的数据同时满足：

1）攻击者不能发现真实的原始数据，也就是说，攻击者通过发布的失真数据不能

重构出真实的原始数据。

2）失真后的数据仍然保持某些性质不变，即利用失真数据得出的某些信息等同于

从原始数据上得出的信息。这就保证了基于失真数据的某些应用的可行性。

数据随机化即是对原始数据加入随机噪声，然后发布扰动后数据的方法。需要注意

的是，随意对数据进行随机化并不能保证数据和隐私的安全，因为利用概率模型进

行分析常常能披露随机化过程的众多性质。随机化技术包括两类：随机扰动

（RandomPerturbation）和随机化应答（RandomizedResponse）。

随机扰动采用随机化过程来修改敏感数据，从而实现对数据隐私的保护。一个简单

的随机扰动模型如表1(a)所示。

对外界而言，只可见扰动后的数据，从而实现了对真实数据值的隐藏。但扰动后数

据仍然保留着原始数据分布X的信息，通过对扰动后的数据进行重构如表1(b)所

示，可以恢复原始数据分布X的信息。但不能重构原始数据的精确值x1,x2,…,xn。

随机扰动技术可以在不暴露原始数据的情况下进行多种数据挖掘操