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

黄小英

（广西工商职业技术学院，南宁 530003）

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

黄小英

（广西工商职业技术学院，南宁 530003）

0 引言

数据挖掘和数据发布是当前数据库应用的两个重要方面。一方面，数据挖掘与知识发现在各个领域都扮演着非常重要的角色。数据挖掘的目的在于从大量的数据中抽取出潜在的、有价值的知识（模型或规则）。传统的数据挖掘技术在发现知识的同时，也给数据的隐私带来了威胁。另一方面，数据发布是将数据库中的数据直接地展现给用户。而在各种数据发布应用中，如果数据发布者不采取适当的数据保护措施，将可能造成敏感数据的泄漏，从而给数据所有者带来危害。所以，如何在各种数据库应用中保护数据的隐私，成为近年来学术界的研究热点。

1 隐私保护技术的分类与性能评估

1.1 隐私保护技术的分类

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

1）基于数据失真（Distorting）的技术：使敏感数据失真但同时保持某些数据或数据属性不变的方法。例如，采用添加噪声（Adding Noise）、交换（Swapping）等技术对原始数据进行扰动处理，但要求保证处理后的数据仍然可以保持某些统计方面的性质，以便进行数据挖掘等操作。

2）基于数据加密的技术：采用加密技术在数据挖掘过程中隐藏敏感数据的方法。多用于分布式应用环境中，如安全多方计算（Secure Multiparty Computation，以下简称SMC）。

3）基于限制发布的技术：根据具体情况有条件地发布数据。如：不发布数据的某些域值，数据泛化（Generalization）等。

1.2 隐私保护技术的性能评估

隐私保护技术需要在保护隐私的同时，兼顾对应用的价值以及计算开销。通常从以下三方面对隐私保护技术进行度量：

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

2）数据缺损：是对发布数据质量的度量，它反映通过隐私保护技术处理后数据的信息丢失：数据缺损越高，信息丢失越多，数据利用率（Utility）越低。具体的度量有：信息缺损（Information Loss）、重构数据与原始数据的相似度等。

3）算法性能：一般利用时间复杂度对算法性能进行度量。例如，采用抑制（Suppression）实现最小化的k-匿名问题已经证明是NP-hard问题；时间复杂度为O(k)的近似k-匿名算法，显然优于复杂度为O(klogk)的近似算法。均摊代价（Amortized Cost）是一种类似于时间复杂度的度量，它表示算法在一段时间内平均每次操作所花费的时间代价。除此之外，在分布式环境中，通讯开销（Communication Cost）也常常关系到算法性能，常作为衡量分布式算法性能的一个重要指标。

2 基于数据失真的隐私保护技术

数据失真技术通过扰动（Perturbation）原始数据来实现隐私保护。它要使扰动后的数据同时满足：

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

2）失真后的数据仍然保持某些性质不变，即利用失真数据得出的某些信息等同于从原始数据上得出的信息。这就保证了基于失真数据的某些应用的可行性。

2.1 随机化

数据随机化即是对原始数据加入随机噪声，然后发布扰动后数据的方法。需要注意的是，随意对数据进行随机化并不能保证数据和隐私的安全，因为利用概率模型进行分析常常能披露随机化过程的众多性质。随机化技术包括两类：随机扰动（Random Perturbation）和随机化应答（Randomized Response）。

2.2 随机扰动

随机扰动采用随机化过程来修改敏感数据，从而实现对数据隐私的保护。一个简单的随机扰动模型如表1(a)所示。

对外界而言，只可见扰动后的数据，从而实现了对真实数据值的隐藏。但扰动后数据仍然保留着原始数据分布X的信息，通过对扰动后的数据进行重构如表1(b)所示，可以恢复原始数据分布X的信息。但不能重构原始数据的精确值x1,x2,…,xn。

表1 随机扰动与重构过程

随机扰动技术可以在不暴露原始数据的情况下进行多种数据挖掘操作。由于通过扰动数据重构后的数据分布几乎等同于原始数据的分布，因此利用重构数据的分布进行决策树分类器训练后，得到的决策树能很好地对数据进行分类。在关联规则挖掘中，通过往原始数据注入大量伪项（False Item）来对频繁项集进行隐藏，再通过在随机扰动后的数据上估计项集支持度，从而发现关联规则。除此之外，随机扰动技术还可以应用到OLAP上实现对隐私的保护。

2.3 随机化应答

随机化应答的基本思想是：数据所有者对原始数据扰动后发布，使攻击者不能以高于预定阀值的概率得出原始数据是否包含某些真实信息或伪信息。虽然发布的数据不再真实，但在数据量比较大的情况下，统计信息和汇聚（Aggregate）信息仍然可以较为精确地被估算出。随机化应答技术与随机扰动技术的不同之处在于敏感数据是通过一种应答特定问题的方式间接提供给外界的。

随机化应答模型有两种：相关问题模型（Related-Question Model）和非相关问题模型（Unrelated-Question Model）。相关问题模型是通过设计两个关于敏感数据的对立问题，

3 基于数据加密的隐私保护技术

在分布式环境下实现隐私保护要解决的首要问题是通讯的安全性，而加密技术正好满足了这一需求，因此基于数据加密的隐私保护技术多用于分布式应用中，如分布式数据挖掘、分布式安全查询、几何计算、科学计算等。在分布式下，具体应用通常会依赖于数据的存储模式和站点（Site）的可信度及其行为。

分布式应用采用两种模式存储数据：垂直划分（Vertically Partitioned）的数据模式和水平划分（Horizontally Partitioned）的数据模式。垂直划分数据是指分布式环境中每个站点只存储部分属性的数据，所有站点存储的数据不重复；水平划分数据是将数据记录存储到分布式环境中的多个站点，所有站点存储的数据不重复。

对分布式环境下的站点（参与者），根据其行为，可分为：准诚信攻击者（Semihonest Adversary）和恶意攻击者（Malicious Adversary）：准诚信攻击者是遵守相关计算协议但仍试图进行攻击的站点；恶意攻击者是不遵守协议且试图披露隐私的站点。一般地，假设所有站点为准诚信攻击者。

3.1 安全多方计算

众多分布环境下基于隐私保护的数据挖掘应用都可以抽象为无信任第三方（Trusted Third Party）参与的SMC问题，即怎样使两个或多个站点通过某种协议完成计算后，每一方都只知道自己的输入数据和所有数据计算后的最终结果。

可以证明，由于采用了可交换加密技术的顺序无关性，在整个求集合并集的过程中，除了集合交集的大小和最终结果被披露外，没有其它私有信息泄露，所以该计算集合并的方法是安全的。

由于多数SMC基于“准诚信模型”假设之上，因此应用范围有限。SCAMD（Secure Centralized Analysis of Multi-party Data）协议在去除该假设基础上，引入准诚信第三方实现当站点都是恶意时进行安全多方计算；文献[6]提出抛弃传统分布式环境下对站点行为约束的假设，转而根据站点的动机，将站点分为弱恶意攻击者和强恶意攻击者，用可交换加密技术解决在分布环境下的信息共享问题。

当前，关于SMC的主要研究工作集中于降低计算开销、优化分布式计算协议以及以SMC为工具解决问题等。

3.2 分布式匿名化

匿名化即是隐藏数据或数据来源。因为对大多数应用而言，首先需要对原始数据进行处理以保证敏感信息的安全；然后再在此基础上，进行数据挖掘、发布等操作。分布式下的数据匿名化都面临在通讯时，如何既保证站点数据隐私又能收集到足够的信息来实现利用率尽量大的数据匿名。

以在垂直划分的数据环境下实现两方的分布式k-匿名为例。两个站点S1和S2，它们拥有的数据分别为{ID,A11,A12,...,A1n1}，{ID,A21,A22,...,A2n1}。其中Aij为Si拥有数据的第j个属性。利用可交换加密在通讯过程中隐藏原始信息，再构建完整的匿名表判断是否满足k-匿名条件来实现。

4 结论

隐私保护技术在诸多领域都有广泛的应用，是近年来学术界新兴的研究课题。本文侧重数据库应用，对隐私保护技术的研究现状进行综述。首先给出了隐私及其度量的定义，然后在对已有的隐私保护技术进行分类的基础上，介绍了基于失真、加密和匿名化的三大类隐私保护技术，特别是，对当前隐私保护领域的研究热点“基于数据匿名化的隐私技术”进行了比较详尽的阐述与分析。

容易看出，每类隐私保护技术都有不同的特点，在不同应用需求下，它们的适用范围、性能表现等不尽相同。当针对特定数据实现隐私保护且对计算开销要求比较高时，基于数据失真的隐私保护技术更加适合；当更关注于对隐私的保护甚至要求实现完美保护时，则应该考虑基于数据加密的隐私保护技术，但代价是较高的计算开销（在分布式环境下，还会增加通讯开销）。而数据匿名化技术在各方面都比较平衡：能以较低的计算开销和信息缺损实现对隐私保护。

[1]J.Han and M.Kamber.Data Mining:Concepts and Techniques.2nd edition,San Francisco:Morgan Kaufmann Publishers,2006.

[2]D.Agrawal and C.C.Aggarwal.On the Design and Quantification of Privacy Preserving Data Mining Algorithms. In Sym.on Principles of Database Systems (PODS),Santa Barbara, California,USA,2001:247-255.

[3]张鹏,童云海,唐世渭,杨冬青,马秀莉.一种有效的隐私保护关联规则挖掘方法[J].软件学报,2006,17(8):1764-1774.

[4]罗永龙,黄刘生,荆巍巍,姚亦飞,陈国良.一个保护私有信息的布尔关联规则挖掘算法[J].电子学报,2005,33(5):900-903.

The privacy preservation study based on LBS

HUANG Xiao-ying

随着数据挖掘和数据发布等数据库应用的出现与发展，如何保护隐私数据和防止敏感信息泄露成为当前面临的重大挑战。隐私保护技术需要在保护数据隐私的同时不影响数据应用。根据采用技术的不同，出现了数据失真、数据加密、限制发布等隐私保护技术。

隐私保护；随机化；安全计算

黄小英（1976 -），女，广西宁明人，讲师，工程硕士，研究方向为计算机应用。

TP312

A

1009-0134(2011)5(上)-0096-03

10.3969/j.issn.1009-0134.2011.5(上).33

2011-01-05