基于位置服务中单向哈希法隐私保护研究

刘林武+张弛

摘 要：基于位置的服务（LBS）正在被越来越多的移动用户使用，用户的身份信息和位置信息也将暴露给服务提供商，从而可能导致用户的隐私被侵犯。提出了单向哈希方法，避免将用户的个人信息直接暴露给服务提供商；使用一种匿名方法，由匿名器将用户的真实位置信息和故意添加的虚假位置信息一齐发送给服务提供商，从而使服务提供商无法得知用户的真实位置，保护了用户的位置隐私。

关键词：隐私保护；LBS；哈希函数

中图分类号：TP391.4 文献标志码：A

Research on the Method of Privacy Preserving

in location-based Service by One-way Hash

LIU Lin-wu，ZHANG Chi

（College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing，Jiangsu 211106，China）

Abstract：Location based services （LBS） are being used by more and more mobile users，and the users identity and location information will also be exposed to the service provider，which may lead to user privacy violations.The one-way hash method is used to avoid the users identity information being directly exposed to the service provider；With an anonymous method，the anonymizer sends the users real location information and the deliberately-added false location information together to the service provider，so that service provider cannot know the true position and the users location privacy is protected.

Key words：privacy preserving；LBS；hash function

0 引 言

隨着移动互联网的快速发展，越来越多基于位置的服务开始出现，极大地方便了人们的生产生活。比如，基于位置服务的车辆调度管理系统[1]。又如，可以应用百度地图搜索附近的银行、饭店、医院；使用滴滴打车软件，可以搜索并召唤附近的出租车。用户首先通过GPS[2]等定位手段获得自己的精确位置信息，然后把位置信息发送给服务提供商，服务提供商根据用户的位置提供相应的服务。但是，一旦用户将位置信息提交给服务提供商后，他将不能删除或修改该位置信息，如果服务提供商是不可信任的，或者数据库遭到非法入侵，用户的隐私也将暴露。设想这样的一个情形，用户A需要搜索附近的治疗乙肝的医院，出于某种原因，他不愿意别人知道自己得了乙肝。如果仅仅保护用户A的姓名不泄露，却对他的位置信息不保密，那么攻击者也有可能获得用户A的身份。假如A使用假ID在自己郊外的家中搜索附近的肝病医院，攻击者获得A的位置信息后，在电子地图上（例如百度地图或者谷歌地图）搜索该位置信息，就可以定位到A的住宅，再通过其它手段，就可以获得A的身份信息。因此，为了在使用基于位置的服务时能保护用户的隐私，需要隐藏用户的位置信息，但服务提供商为了提供服务，又必须知道用户的位置信息。所以，需要寻找一种既然使用服务又能保护用户位置隐私的方法。

另外，某些LBS需要用户提供大量的个人背景信息，如姓名，邮箱号，家庭地址，电话号码等[3]。实际上，用户并不想这些个人信息被服务提供商收集。因此，为了保护隐私，用户希望防止自己的个人信息和用户请求对应起来[4]。

密码学方法也可以用来保护用户的隐私[5]。当对用户请求使用同态加密后，服务提供商无法从用户请求中获取任何有用的知识。但高昂的计算成本和通信开销使得这种方法不太实用。

私人信息检索法（private information retrieval）[6-7]可以使用户向数据库提交请求时不必泄露真实请求，这种方法可以很好地保护用户的隐私。但是该方法需要较高的计算开销，对服务器的计算能力有较高的要求。

1 基于位置的服务的匿名访问

1.1 基于位置的服务

为了使用基于位置的服务（LBS），用户需要首先使用GPS等手段对自己进行定位，然后将位置信息发送给服务提供商。服务提供商根据该位置信息返回相应的结果。假如在地图上有某个用户和多家医院如图1所示。图中黑色圆点表示用户，十字形标志表示医院。

假设用户需要搜索离自己最近的医院，如图2所示，该过程分为四步：

第一步：将自己的位置信息（通过GPS获得）和请求“离自己最近的医院”发送到服务提供商。

第二步：服务提供商在将该位置信息和请求提交到后台数据库。

第三步：后台数据库经过比对用户位置和以前存储的医院位置信息，找到离用户最近的医院4，并将医院4的信息提交给服务提供商。

服务提供商在收集到用户的位置信息后，可以推测出下列信息：

1.用户在特定时间段内经常出现在什么地方。endprint

2.用户的行为模式，也即用户在特定时间段内的移动路线和频率。

3.用户经常去某些地方的频次，比如商场，夜总会，医院。

而这些信息事关用户的隐私，一般是用户不愿意泄露的。因此，用户在使用LBS的时候希望将自己的位置信息隐藏。

1.2 K级空间匿名方法

为了保护用户的个人位置信息，需要为用户提供空间匿名度。与上文中用户将自己的位置信息直接发送给服务提供商不同的是，K级空间匿名方法将用户的真实位置信息La和其它k-1个虚假的位置信息混合在一起，得到一组位置信息L={l1，l2，...lk-1，la}，一齐发送给服务提供商。这样，服务提供商无法知道哪个位置才是真正的用户位置，猜测出用户的位置信息的概率为1/k。K值越大，猜中的概率就越低。服务提供商在得到这k个位置信息后，在数据库搜索，得到k个结果R={r1，r2，...rk-1，ra}。然后将这K个结果返回給用户。用户在这K个结果中很容易找到于位置la对应的结果ra。然而，随着K的值增大，服务器的搜索时间也将增加，用户得到返回结果的等待时间也将延长，因此，需要根据用户所需的匿名程度和等待时间选择恰当的K值。但由用户直接产生虚假位置，将增加用户设备的负担，降低用户体验，而且，如果一个用户产生大量的虚假位置发送给服务提供商，服务提供商会怀疑自己受到了攻击从而拒绝服务[8]。

2 单向哈希函数与匿名器

2.1 单向哈希函数

单向哈希函数，也称做“消息摘要”，是一种广泛应用的加密方法，相当于对要发送的消息添加了“指纹”。一般地，在非安全信道上传输信息时，为了检测在传输过程中信息是否被篡改，可以用哈希函数来确认信息的完整性[9]。本文将单向哈希函数用于用户访问服务时的认证过程。借助哈希函数，得到用户个人信息（或称之为用户凭证）的“消息摘要”（也即指纹）。通过该指纹，可以精准地唯一地确定用户身份。假设C为用户张三的一个属性集，C中包含四条信息：{姓名，用户ID，邮箱号，年龄}。那么可知张三的属性集C为C={张三，1688，zhangsan@test.com，31}。使用单向哈希函数H，对C中的属性进行哈希运算，可得一个消息摘要，也即张三的电子指纹fa。fa为一个固定长度的比特串，可用作张三的身份凭证，但无法通过fa逆向计算出C的内容，从而保护了张三的个人信息。

2.2 匿名器

为了让用户在使用基于位置的服务时用户隐私能保护，需要一个匿名器。该匿名器的作用相当于一个居于用户和服务提供商之间的可信任第三方。用户在匿名器上进行认证，而不是在服务提供商上进行认证。认证通过后，匿名器将来自用户的位置信息和服务请求进行处理并转发给服务提供商，使得服务提供商无法得知用户的隐私信息。

3 匿名访问LBS的框架

随着用户的隐私保护意识越来越强，有时候用户并不信任服务提供商，他们在使用LBS时并不想透露个人信息。但是，为了使用某些服务，必须对用户进行认证，合法的用户才可以使用服务，这就意味着用户必须提供出个人信息以及身份凭证。为了解决这个问题，提出了一个匿名访问框架。该框架由用户、匿名器、服务提供商组成。如图3所示：

图3 匿名访问LBS框架

假设在用户发送服务请求之前，匿名器和服务提供商之间已经建立了可信任连接（比如可信任的SSH连接）。该框架的工作流程如下：

1.用户向匿名器发送一个数据包，如图4所示，该数据包里有用户的ID号，指纹fa，服务请求request，服务ID等。

2.匿名器根据服务ID号确定服务提供商，然后向服务提供商请求所有注册了该服务的用户的ID号，假设所有用户ID的起始范围为[M，N]，显然，张三的ID号在[M，N]范围内。

3.服务提供商返回所有用户ID。

4.匿名器在[M，N]中随机选择k个ID号，当然，张三的ID号必须被选中。但服务提供商不知道哪个ID是张三的，也就不知道谁在请求服务。然后，匿名器请求服务提供商提供这K个ID号对应的指纹。

5.服务提供商向匿名器返回指纹集F。匿名器在收到F后，将fa与F中的元素逐一比对。假设f5和fa相等，那么说明张三的指纹之前已经存储在服务提供商的数据库中，说明张三是合法用户，认证通过。如果fa与F中的所有元素都不相同，说明张三的指纹没有存储在服务提供商的数据库中，也即张三是非法用户，认证没能通过。

6.匿名器向用户和服务器发送认证结果。

也就是说，匿名器作为可信任的第三方，在本框架中替代服务提供商，基于用户的指纹对用户的身份凭证进行认证，可以避免泄露用户的个人信息的细节。

当认证通过后，用户可开始使用LBS。与前文不同的是，这里由匿名器代替用户的移动设备来产生虚假位置信息，这样可以降低用户端移动设备的软硬件要求，减轻用户端移动设备负担，使用户端移动设备运行流畅，改善用户体验。而且，由于服务提供商对匿名器是完全信任的，即使匿名器发送大量服务请求，也不会识以为受到了攻击而拒绝服务。如图5所示，步骤如下：

1.服务请求者向匿名器发送服务请求包，请求包里包括（用户ID，位置信息la，服务ID，其它信息）

2.匿名器寻找请求者附近的离请求者最近的其它k-1个用户，将这k-1个用户的位置作为干扰项，得到匿名化后的位置信息L={l1，l2，...lk-1，la}。

3.匿名器将服务请求包中的用户ID用“anonymous ID”代替，这样服务请求包变为（anonymous ID，L，服务ID，其它信息）。这样，服务提供商只知道是匿名器在请求服务，而不知道是哪个用户在请求服务，也不知道到底有多少用户在请求服务。由于服务提供商是信任匿名器的，因此它会响应匿名器发送的服务请求。endprint

4.匿名器將服务请求包发送到服务提供商。服务提供商根据这k个位置数据l1，l2，...lk-1，la进行搜索计算，返回结果R={r1，r2，...rk-1，ra}，匿名器根据请求者的真实位置信息，过滤掉干扰项，将结果ra返回给用户。

在用户访问服务的过程中，服务提供商都无法得知用户的真实位置，从而保护了用户的隐私。

4 结束语

本文提出的方法借助单向哈希函数和匿名器，在认证过程中保护了用户的隐私，防止用户个人信息被泄露。同时，在使用服务的过程，采用K级空间匿名法，对用户的位置进行模糊化处理，防止用户位置信息被泄露。这样，在整个过程中，用户都保持了很好的匿名性。将来，需要考虑如何使虚假位置的移动轨迹接近于用户真实位置的移动轨迹，防止攻击者利用轨迹追踪确认用户身份，而且要考虑如何量化评价位置信息的匿名度。

参考文献

[1] 胡卉卉，宋丹.基于位置的服务在车联网系统中的应用[J].计算技术与自动化，2013，32（4）：92-95.

[2] GETTING I.The global positioning system[J].In IEEE Spectrum，1993，30（12）：36-47.

[3] KOTZANIKOLAOU P，MAGKOS E，PETRAKOS N，et al.Fair Anonymous Authentication for Location Based Services[M]// Data Privacy Management and Autonomous Spontaneous Security.Springer Berlin Heidelberg，2013：1-14.

[4] NONJUR M，AHAMED S I，HASAN C S.ELALPS： A Framework to Eliminate Location Anonymizer from Location Privacy Systems[C]// IEEE International Computer Software and Applications Conference，COMPSAC 2009，Seattle，Washington，Usa，20-24 July.DBLP，2009：11-20.

[5] GAHI Y，GUENNOUN M，GUENNOUN Z，et al.Privacy Preserving Scheme for Location-Based Services[J].Journal of Information Security，2012，03（2）：105-112.

[6] OLUMOFIN F，TYSOWSKI P K，GOLDBERG I，et al.Achieving Efficient Query Privacy for Location Based Services[C]// Privacy Enhancing Technologies，International Symposium，PETS 2010，Berlin，Germany，July 21-23，2010.Proceedings.DBLP，2010：93-110.

[7] KHOSHGOZARAN A，SHAHABI C.Private Information Retrieval Techniques for Enabling Location Privacy in Location-Based Services[M]// Privacy in Location-Based Applications.Springer-Verlag，2009：59.

[8] CHOW C Y.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]// ACM International Symposium on Geographic Information Systems，Acm-Gis 2006，November 10-11，2006，Arlington，Virginia，Usa，Proceedings.DBLP，2006：171-178.

[9] RAGAB A H M，ISMAIL N A，ALLAH O S F.An efficient message digest algorithm （MD） for data security[C]// IEEE Region 10 International Conference on Electrical and Electronic Technology.IEEE Xplore，2001，1：191-197.endprint