LBS中非可信用户协作研究范文

《计算机工程与应用杂志》2014年第十四期

1UCA算法系统结构

移动设备的不断发展，使客户端内集成计算模块变得可行。本文提出的UCA匿名算法系统结构如图1所示，包括移动用户，位置服务提供商和证书管理机构CA。移动用户为包含定位设备的移动终端，证书管理机构负责管理合法用户的数字证书，位置服务提供商为用户提供各种基于位置的服务，供用户之间进行身份认证。移动终端可以是手机、笔记本电脑、平板电脑等各种移动设备，通过这些设备，用户可以获得自己的准确位置信息。移动用户支持两种通信方式：P2P通信和无线互联网通信，其中，P2P通信方式用来与其他用户协作构建匿名域，无线互联网通信用来与证书管理机构以及位置服务提供商通信获得证书、发起查询以及接受查询结果集。P2P通信可以采用WLAN或蓝牙的方式实现，无线互联通信通过2G或3G网络实现。证书管理机构CA负责管理用户的数字证书。为了提高证书的安全性及合法性，每个用户的数字证书都与用户的身份一一对应。同时，为了防止证书管理机构被恶意攻击，用户的数字证书被非法窃取，管理机构还会定期更新用户的数字证书，在更新之后自动发放给所有合法用户，实现证书的新鲜性。在协作构建匿名域时，通过数字证书，验证用户身份的合法性，更加有效地保护了用户的位置隐私。位置服务提供商主要负责提供用户所需的各种基于位置的服务。在收到用户的查询内容和匿名域之后，服务商根据匿名域得出一个候选结果集，该集合的大小取决于用户匿名域，匿名域越大，候选结果集越大，相反，匿名域越小，候选结果集也越小。得出候选结果集之后，服务商将该集合返回给用户，由用户进行结果求精，得到真正的最优解。

2UCA安全隐私保护算法

由于实际生活中，用户在采用协作方式开始构建匿名域时，周围的用户相对于该用户都是不可信的，所有用户都是可信的这一假设并不充分。因此，本文在P2P空间匿名算法的基础上提出了一种基于用户协作的安全隐私保护算法UCA。该算法考虑到协作用户中有攻击者的情况，除了构造匿名域之外，还加入了数字证书。通过数字证书，用户之间可以进行身份验证，并且在通信过程中，以加密的形式发送自己的位置信息。此外，算法中还加入了可以容忍的最大等待时间，当用户发现的节点数不满足要求且没有超过最大等待时间时，可以通过等待一段时间重新发送节点请求来寻找更多的节点。通过本算法，可以避免攻击者伪装成合法用户的方式获取其他用户的位置信息，也可以在有多个攻击者合谋时降低用户的位置信息被推算出的概率，有效提高了用户的匿名成功率。

2.1匿名算法步骤1节点发现。用户M发出查询请求。初始时，已发现节点集合U为空集{Æ}已发现节点个数n为|U|即0，跳数h为1，可以容忍的最大等待时间为Tmax隐私需求为M的隐私需求参数k（算法1第1~2行）。当节点个数不满足隐私需求k且没有超过可以容忍的最大等待时间Tmax时，M广播节点发现消息，参数包括消息的ID号，参数h以及M的数字证书。U′为接收到的响应节点的集合，n为收到响应节点的个数。如果n>k-1说明节点个数满足隐私需求，可以不再广播节点发现消息。若n<k-1先比较U′和U两者相等，说明增加跳数也无法发现更多节点，等待一段时间后根据当前跳数重新广播节点发现消息（算法1第11~14行），否则，将跳数增加1，U′置为U继续广播节点发现消息，等待用户响应。若超过Tmaxn依然不能满足用户的隐私需求，说明节点发现失败。

2.2数字签名UCA匿名算法中用户使用的数字证书由CA统一管理，可以定期进行更新。这里证书采用的是RSA签名体制，签名的时候，用户先对自己的合法ID求出散列值，然后用自己的秘密私钥对散列值操作。过程如下：设用户M的公开密钥为ne秘密私钥为d散列值为m。

3实验

实验采取模拟数据集的方式，模拟数据集由ThomasBrinkhoff路网数据生成器生成，以城市Oldenburg的交通路网（面积23.57km×26.92km）作为输入，生成模拟的移动用户数据，以下简称为Oldenburg数据集。算法采用Java实现，实验中的默认参数值如表1所示。

3.1可扩展性分析在可扩展性实验中，使用Oldenburg数据集评估系统中k值由5增大到25时，用户协作平均通信消息量、平均响应时间、候选结果集以及匿名成功率4个参数的变化情况，并与P2P空间匿名算法做了对比。用户协作平均通信消息数量指移动用户从发起邻居发现请求开始到获得所有k-1个节点的消息数量。如图2所示，由于用户隐私需求参数k增大，需要发现的节点数增多，UCA匿名算法和P2P空间匿名算法的用户协作平均通信消息量都有所上升。UCA匿名算法中加入了等待时间这一参数，会在可以容忍的等待时间内重复发送节点发现消息以达到更高的匿名成功率，所以与P2P空间匿名算法相比，增加了一定通信量。响应时间指用户发起邻居发现请求开始到获得所需的k-1个节点所耗费的时间。从平均响应时间来看，随着用户隐私需求参数k的增大，响应时间也不断增大。UCA匿名算法中增加了可以容忍的最大等待时间，通信的响应时间有一定提高，相比于P2P空间匿名算法，稍逊一筹，如图3所示。候选结果集指用户通过匿名域获得的位置服务提供商返回的所有结果。UCA算法和P2P空间匿名算法都定义了最小匿名域，因此在这方面，两个算发法没有太大的差别，如图4所示。匿名成功率指成功匿名的移动用户（指匿名组内用户个数大于或者等于用户的隐私需求参数k）同系统中全部移动用户个数的比率。UCA匿名算法中，在可以容忍的等待时间内，用户在发现节点失败之后，可以等待一段时间重复发送节点发现消息来重新寻找k-1个节点，因此与P2P空间匿名算法相比，可以获得更大的匿名成功率，如图5所示。

3.2安全性分析与P2P空间匿名算法相比，UCA匿名算法中加入了身份认证。在周围用户非完全可信时，通过用户彼此的身份验证，使提出查询请求的用于可以与可信用户协作构建匿名域，实现了位置隐私保护。因此，UCA算法比P2P空间匿名算法更实用。UCA匿名算法中使用了RSA签名体制，其中RSA签名的安全性依赖于RSA公钥加密算法。由证书管理机构对用户的数字证书定期更新，提高了用户数字证书的安全性。所有用户在发送位置信息时都采用加密的方式，保证除了接收方之外，别的节点无法获取自己的位置信息。当匿名域内k个节点中有n个是攻击者时，他们可以合谋知道彼此的位置信息，但是由于其他节点的位置信息是加密的，他们无法知道，因此，他们推算出某个用户的位置信息的概率是1/S(k-n)。攻击者的数量一定时，k越大，用户的位置隐私暴露的可能性就越小。

4结束语

分析了LBS的位置隐私保护的特点后，UCA匿名算法在文献[7]的基础上，考虑到用户非可信的情况，增加了数字签名。周围用户在提供自己的相关信息之前，需要验证请求这些信息的用户的合法性，保证了自己的位置相关信息不会泄露给攻击者。在发送自己的相关信息给提出查询请求的用户之前，用提出查询请求用户的公钥对其中的位置信息进行加密，保证了除了该用户，匿名域内的其他用户无法知道其他用户的位置，可以防止匿名域中的攻击者根据已知的其他用户的位置信息推算出提出查询请求的用户的位置信息。算法还加入了最大容忍时间Tmax使用户可以通过延迟一段时间发送节点发现请求的方式来寻找更多的节点，提高了匿名成功率。但是，UCA匿名算法还存在不足之处，如每个用户的匿名都是独立进行的，当同时有多个用户需要匿名的时候，会带来很大的通信时延和通信开销，希望在以后的研究考虑到这些问题，并提出解决方案。

作者：杨祎綪袁家斌单位：南京航空航天大学计算机科学与技术学院