一种身份认证下交换查询的轨迹位置保护算法

李 兰，张才宝，奚舒舒，马鸿洋

1(青岛理工大学 信息与控制工程学院，山东 青岛 266525)2(青岛理工大学 理学院，山东 青岛 266033)

E-mail:17864213324@163.com

1 引 言

无线通信和全球定位技术的飞速发展给移动应用程序带来了新的机遇，许多嵌入基于位置服务[1-4](Location-Based-Service,LBS)功能 的APP被开发出来，用户可以在陌生的环境中使用这类APP查询附近的酒店、超市等兴趣点[5](Point of Interest,POI)来满足自身需求，这些应用程序给日常生活提供了诸多便利[6,7].但随着用户安全意识的提高，在享受LBS服务的同时，用户也时刻担心提交给位置服务提供商(Location Service Provider,LSP)(以下LSP与LBS服务器指代同一个对象)的信息被不法分子截取.用户主要考虑两个方面，第一，使用此类APP时需通过手机号获取验证码进行登录，此时，用户的手机号会被LSP获取；第二，使用时用户需要提交查询信息，并将自身位置发送给LSP，此时，用户的查询内容和位置信息会被LSP获取.由于实名制度的实施，手机号码可作为用户的真实身份之一[8]，当恶意攻击者将手机号码与用户提交的查询内容和位置信息链接后，容易推断出用户的兴趣、住址等隐私[9]，因此目前的工作是如何有效解决这两个问题.

2 相关工作

目前，对于连续查询中用户的轨迹隐私保护已经引起广泛关注.Huo等[10]提出对轨迹信息上的敏感点进行匿名化的方法，以保护轨迹隐私.Hwang等[11]提出了一种根据用户隐私档案和环境条件形成隐藏区域的时间模糊技术，使得恶意LBS服务器无法重建用户轨迹.Palanisamy等[12，13]利用混合区提供黑箱空间，截断各子轨迹所反映的相关性，降低攻击者关联整个轨迹的成功概率，之后又提出将用户形成一个隐匿区域，除查询发起者外，该区域还包含其他k-1个用户，这样，对手就无法确定发起者用户.Jiang[14]等提出一种基于查询分片用户协作的位置隐私保护方法，用于解决实际应用环境中协作用户的不可信问题.还有基于原语的密码学方法[15,16]，通过对用户与LBS服务器的交互信息加密实现隐私保护目的，可以提供很好的安全性，但存在用户与LBS服务器通讯中计算开销很大的问题.

身份认证是移动用户使用LBS功能应用程序的基础，手机号码和姓名、住址等一样，代表着用户的真实信息，如果不法分子将用户的网络信息与真实信息关联起来，用户的隐私会遭到泄露.Wang等[17]提出一种通过第三方平台存储个人信息的模型，为用户提供个性化信息推送服务.Gu等[18]提出一种数字签名技术与身份认证方案，该方案结合椭圆曲线密码体制与组合式伪随机数，并使用SVO逻辑对该方案进行形式化分析.Wang等[19]提出基于PTPM(portable TPM)和无证书公钥签名算法的身份认证方案，支持用户利用任意终端设备来完成与云端的双向身份认证过程，以解决目前云环境下用户与云端之间进行身份认证时所存在的安全问题和不足.Zhou等[20]提出可证安全的高效无证书两方认证密钥协商协议.类似于文献[19,20]主要集中在利用公钥证书进行身份认证的研究，而基于短信验证码的身份认证的安全性的研究较少.

本文提出一种身份认证下交换查询的轨迹位置保护算法.用户登录时，利用可信第三方服务器，将数据进行分割，该服务器保存用户的手机号码，LSP保存与用户真实身份无关的数据.当用户进行查询时，根据用户的隐私需求构建候选协同用户区域，利用距离权重计算方法，选择熵最大的一个用户作为最佳协同用户(Best Collaborative User,BCU)，使双方互相交换查询内容.这样既保护了用户的真实身份，又保护了位置隐私，即使LBS服务器被不法分子攻击，也无法对用户进行准确识别，有效保护用户隐私安全.

3 身份认证下交换查询的轨迹位置保护算法

本节首先定义了一些基本概念，然后给出身份认证下交换查询的轨迹保护模型，本文使用的符号汇总在表1中.

表1 符号汇总Table 1 Symbol summary

3.1 相关定义

定义 1.(距离度量)用户ui和uj之间的距离度量(本文使用欧几里得距离)，定义为

(1)

其中x，y分别表示用户所在位置的经度和纬度.

定义 2.(距离权重)用αi表示查询用户ureal的候选协同用户区域内用户ui的距离权重，定义为

(2)

定义 3.(最佳协同用户)k个候选协同用户中权重最大的一个称为最佳协同用户，表示为

(3)

3.2 系统模型

本文系统架构如图1所示，轨迹隐私保护模块由移动用户、第三方服务器及LBS服务器(LSP)组成；身份认证模块由移动用户、可信第三方服务器、LBS服务器(LSP)及短信平台组成.

图1 系统架构Fig.1 System structure

轨迹隐私保护算法中，第三方服务器根据定义2中的距离权重计算αi，并选择BCU辅助用户进行查询，BCU的选择如图2所示.

图2 候选协同用户区域Fig.2 Candidate collaborative user area

3.3 移动用户身份认证

为了防止LBS服务器泄露用户的隐私信息，本文在移动用户与LBS服务器间引入可信第三方服务器，将原来存储在LBS服务器上的手机号码分离出来，存储在第三方服务器上，从而防止由手机号码引起的用户隐私信息的泄露.架构图如图1身份认证模块所示，具体步骤如下：

步骤1.移动用户输入TelePhone,将获取短信验证码的请求发送给可信第三方服务器.

步骤2.可信第三方服务器将TelePhone过滤,并将包含用户ID和本次会话号的请求发送给LBS服务器.

步骤3.LBS服务器通过特定算法生成短信验证码,与购买的短信平台服务权限和用户ID一起发送给可信第三方服务器.

步骤4.可信第三方服务器将TelePhone和短信验证码发给短信平台.

步骤5.短信平台将验证码发往用户端,用户使用验证码登录.

用户端通过验证码登录后，LSP通过用户提交的验证码与自己生成的验证码进行比较，若相同，则验证通过.

因为可信第三方服务器没有购买短信平台服务权限，所以LSP需要将该服务权限发送给第三方服务器，本文通过算法1进行该权限的处理.

算法1.授予访问权限

输入：IDLSP：LSP的ID

输出：授权结果Res

1.LSP通过算法产生一个随机序列Seq；

2.LSP利用私钥将序列Seq加密；

3.Seq～=Private Key{Seq}；

4.LSP将{Seq～,IDLSP}发送给可信第三方服务器；

5.可信第三方服务器将{Seq～,IDLSP}发送给短信平台；

6.短信平台根据LSP的公钥对消息进行验证：

7.Res=Public Key{{Seq～,IDLSP}};

8.returnRes

3.4 基于交换查询的轨迹位置保护算法

第三方服务器根据用户的隐私需求构建候选协同用户区，通过距离权重选择BCU，然后将用户与BCU的ID转换，并发送给LSP进行查询，LSP将查询结果返回给第三方服务器后，再将用户和BCU的ID恢复，并分别将结果发送给用户和BCU.具体步骤如下：

步骤1.用户将查询消息EU2A发送给第三方服务器，其中隐私需求使用第三方服务器公钥加密，查询内容和范围以及对称加密密钥使用LBS服务器公钥加密，第三方服务器使用私钥获得用户的隐私需求，寻找协同用户，并将距离权重最大的一个设为最佳协同用户BCU.EU2A形式如下(4)：

EU2A={PKA(ID,Rmin,Rmax,k),PKS(R,Q,KS)}

(4)

步骤2.找到BCU后，第三方服务器将用户的ID转换成BCU的伪ID(IDBi)，然后将IDBi与用户的查询请求共同组成查询消息，如式(5)所示：

EA2S={PKS(IDBi),PKS(R,Q,KS)}

(5)

第三方服务器将用户的查询消息发送给LBS服务器，值得注意的是，用户的查询内容和范围使用LBS服务器公钥加密，所以第三方服务器无法获得.

步骤3.LBS服务器收到消息EA2S后，进行解密，并根据用户的需求搜索POI并获得结果E，最后它使用对称加密密钥加密E，将其发送给第三方服务器.

ES2A={PKA(IDBi),KS(E)}

(6)

步骤4.第三方服务器收到来自LBS服务器的查询结果后，首先从列表中恢复用户的ID，然后利用用户公钥将提取出来的查询结果KS(E)进行加密，如式(7)所示：

EA2U={PKU(KS(E))}

(7)

最后，第三方服务器将查询结果发送给用户.

步骤5.用户从第三方服务器收到EA2U后，使用私钥和对称加密密钥获得精确结果E.在查询交换过程中，第三方服务器同样为最佳协同用户BCU执行步骤1-步骤4.

寻找最佳协同用户算法伪代码如算法2所示

算法2.寻找最佳协同用户

输入：ID,Rmin,Rmax,k

输出：最佳协同用户BCU

1.初始化队列q，并设置|q|=k；

2.根据用户隐私需求，输入Rmin、Rmax和k，如果用户不输入k值，默认k=6，构建候选协同用户区域；

3.从候选协同用户区域中选择k个用户，并放入队列q中；

4.if协同用户数量小于kthen

5. 协同用户数量不足，k=k-1；

6.else

7.fori=1tokdo

8. 计算距离权重αi；

10.endif

4 安全性分析

本文的安全性分析集中在如何保护用户的真实身份和轨迹隐私，主要针对窃听攻击、不可信LBS服务器及第三方服务器攻击.

4.1 窃听攻击

用户与第三方服务器之间以及第三方服务器与LBS服务器之间的通信过程可以被攻击者通过无线信道窃听.轨迹隐私保护模块中使用对消息加密的方式来处理窃听攻击，在无线信道中传输的所有消息都由非对称和对称密钥加密保护.

当用户向第三方服务器发送查询消息时，隐私需求使用第三方服务器公钥加密为PKA(ID,Rmin,Rmax,k)，查询内容、范围和对称加密密钥使用LBS服务器公钥加密为PKS(R,Q,K_S)，然后将EU2A={PKA(ID,Rmin,Rmax,k),PKS(R,Q,KS)}发送给第三方服务器，在此过程中，攻击者没有第三方服务器和LBS服务器的私钥，即使窃听到消息，也无法得到任何信息.同样，当第三方服务器将ID转换后的查询请求EA2S={PKS(IDBi),PKS(R,Q,KS)}发送给LBS服务器时，攻击者无法获得任何信息，因此用户的敏感信息得到有效保护.

返回查询结果时，ES2A={PKA(IDBi),KS(E)}使用第三方服务器公钥和对称加密密钥加密，EA2U={PKU(KS(E))}使用用户的公钥加密，攻击者没有第三方服务器私钥、对称加密密钥和用户的私钥，因此，他们获取有用信息的概率可以忽略不计.通过以上分析，可以看到我们的方案可以有效抵抗窃听者的攻击，使攻击者无法获得用户的真实身份、查询位置和查询内容.

4.2 不可信LBS服务器

LSP管理用户的所有查询信息，当LSP不是受信任时，可以通过这些数据推断敏感信息，包括用户的真实身份和移动轨迹.

本文的方案中，因为手机号码存储在可信第三方平台，而不是LBS服务器，所以，即使攻击者通过LBS服务器获得了用户信息，也无法和真实信息联系起来，有效保护用户的身份.并且在轨迹隐私保护模块中，第三方服务器在用户和BCU之间交换查询，在这个过程中，用户的身份ID在第i个查询中被BCU的IDBi替换，并且LBS服务器中的查询信息存储记录被链接到BCU的IDBi.由于每个查询点的BCU不同，LSP无法推断他们之间的关系，也无法从任意BCU的IDBi中识别用户的真实轨迹.因此，LSP能够推断用户真实身份或其轨迹的概率可以忽略不计.

4.3 第三方服务器攻击

身份认证模块中，假设Bob通过第三方服务器得到了Alice的信息{TelePhone,ID}.Bob企图使用Alice的“TelePhone+短信验证码”进行登录，由于Bob没有Alice的手机，无法获得短信验证码，因此登录失败；同理，如果Bob用Alice的“ID+PassWord”进行登录，由于Bob无法获知Alice的PassWord，同样登录失败.

轨迹隐私保护模块中，Bob通过第三方服务器得到了Alice的查询消息EU2A={PKA(ID,Rmin,Rmax,k),PKS(R,Q,KS)}，即使Bob使用第三方服务器私钥获得了Alice的ID，但因为缺少LBS服务器私钥SKS，无法解密Alice的查询内容和范围；同样，假设Bob通过第三方服务器得到Alice的查询结果ES2A={PKA(IDBi),KS(E)}，由于Bob没有对称加密密钥KS，无法解密查询结果E，因此Bob无法获得关于Alice的有效信息.

5 实验仿真

5.1 实验环境

实验环境为2.4GHz的双核CPU，8GB内存，操作系统是Windows10.在身份认证模块中，本文在MySQL(线程池中的20个线程)上模拟通信时间；轨迹隐私保护模块中，算法采用Python编程语言实现，在Thomas Brinkhoff[21]上进行仿真实验，在Oldenburg交通路网中取大约4km×4km区域位置数据，其中20个POIs是随机生成的，用户数量由参数控制.

5.2 仿真结果分析

5.2.1 身份认证中时间效率分析

实验时从数据库表中采集了所有用户登录时请求记录数总和n的值，当n分别为600,800,1000,1200时，处理每一次请求所花费的时间(ms)，x轴表示实验重复次数.

由图3可以看出，第一次实验时的请求响应时间比后面7次响应时间大，这是因为系统初始化后需要重新连接数据库.

将图3中n分别为600,800,1000,1200时的8次模拟数据取平均值得到图4.

图3 请求记录数与响应时间关系Fig.3 Relationship between number of request records and response time图4 不同n值下的平均响应时间Fig.4 Average response time at different values of n

由图4可以看出，当请求记录数量达到1200时，系统平均响应时间未达到5000ms，即5s，现在短信平台响应时间普遍在5s以内，所以总响应时间可以保持在10s以内，而短信验证码的有效时间为60s，所以此身份认证方案在实际应用中是可行的，既保护了用户的隐私信息，又能较好的为用户提供服务.

5.2.2 基于交换查询的轨迹隐私保护算法分析

为验证轨迹隐私保护算法的有效性，本文在请求响应时间和用户轨迹位置保护程度两方面与CPP算法[22]进行比较，为增加说服力，两种算法中用户的Rmin与Rmax均相同.

系统响应时间指用户的请求通过某算法进行处理后发送给LSP，并收到从LBS服务器返回的第一个POI的这段时间.

由图5可以看出，两种算法的系统响应时间随k值的增大而增加.当k很小时，用户可以很快寻找到协同用户或者生成匿名区域，但当k值增加到一定程度时，系统响应时间明显增加，这是因为k值越大，用户搜索其他k-1个用户的时间越久.图5中明显看出，本文基于交换查询的轨迹隐私保护算法的响应时间比CPP算法短，因为在找到协同用户后，系统只需要分别计算协同用户的权重即可，而CPP算法需要根据约束条件生成匿名区，增加了响应时长.

图5 系统响应时间与k值的关系Fig.5 Relationship between system response time and k value图6 轨迹位置保护度与k值的关系Fig.6 Relationship between protection degree of track position and k value

在可接受的系统响应时间下，用户轨迹位置保护程度是衡量算法优劣的的重要指标.图6为本文基于交换查询的轨迹隐私保护算法与CPP算法在用户轨迹位置保护程度上的对比.

由图6可以看出，当k值较小时，两种算法由于无法构建良好的辅助区域，在用户轨迹保护程度上接近，随着k值增加，本文基于交换查询的轨迹隐私保护算法明显可以达到更好的保护效果.这是因为k值增加到一定程度时，可以从众多协同用户中选择距离权重最大的一个作为BCU，且最佳协同用户是动态变化的，攻击者无法将用户在各个时刻上的位置联系起来，因此k值越大，本文基于交换查询的轨迹隐私保护算法对用户的轨迹保护程度越高.

6 结束语

为了更好地保护用户的真实身份、位置信息与查询内容，防止恶意攻击者通过LSP将用户的这些信息联系起来，提出一种身份认证下交换查询的轨迹位置保护算法.用户登录时利用第三方服务器将手机号码过滤，使LSP无法获得用户的手机号码；当用户向LSP提交位置信息和查询请求时，利用BCU与用户进行交换查询，使LSP无法关联用户的查询请求与ID.最后通过仿真实验，验证了该算法在保护用户身份与轨迹隐私方面的有效性.从不同方面考虑协同用户的选择是本课题将继续研究的内容.