2. 哈尔滨工程大学 计算机科学与技术学院, 哈尔滨 150001
基于位置服务（LBS）中的隐私保护方法存在如下常见问题：重视用户端隐私保护而容易忽略LBS服务端的数据安全；隐私保护强度高的方法实用效率低；隐私保护方法大多面向欧氏空间提出，无法适用路网环境，查询准确率低.针对上述问题，基于不经意传输提出了一种LBS兴趣点查询服务中的隐私保护方法，在保护用户位置和查询内容隐私的同时确保LBS服务端数据安全，并能确保路网连续查询的效率和准确率.性能分析及实验结果表明，新方法具有较强的安全性和良好的工作效率.
2. School of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
There are three common defects in existing location based service (LBS) privacy-preserving methods:only considering privacy preservation of the user without caring about data security of LBS server. The stronger a privacy-preserving method is, the less practical it is. Privacy-preserving methods are usually proposed based on the Euclidean space without considering actual factors in road network, and the query accuracy declines consequently. To solve the above problems, an LBS privacy-preserving scheme was proposed based on oblivious transfer with special distribution information for points of interest in road network. This scheme ensures data security of LBS server while preserving the user's location privacy and query content privacy, at the same time, it is applicable for continuous query in road network and guarantees the query efficiency and accuracy. Performance analysis and extensive experiments show that this scheme ensures strong security and works efficiently.
基于位置的服务[1]为人们提供方便的同时，需要用户提供一定的隐私数据作为获取服务的代价.用户将个人隐私数据发送给任何实体均存在泄漏的风险.攻击者可以通过掌握的背景知识，关联推断出用户的真实身份、兴趣爱好、生活习惯等隐私信息.在基于位置的查询服务中，位置和查询内容隐私是两项重要的保护内容[2].
匿名框[3-4]和假位置[1, 5-8]是两类经典的位置保护方法.作为假位置的一种，锚点用来代替用户真实位置发起查询，并依据该锚点计算出实际K近邻兴趣点，该方法由Yiu等[5]首次提出，但存在未实现k匿名、锚点选取随机等缺陷.孟小峰[6]及Gong[7]等学者分别提出了改进方案，但这些方法大多面向欧氏空间设计，并且随机选取的查询锚点会带来较多数据库查询操作. Zhou等[8]针对锚点选取方式、查询不均衡等问题提出了解决方法，但未考虑LBS端数据安全.
私有信息检索[1, 10]是保护查询内容隐私的经典方法，能在LBS服务器不知晓查询内容的条件下，为用户提供查询结果.此类技术隐私保护强度高，但存在查询处理速度慢的缺陷[4, 11].周长利等[12]基于伪随机置换提出了一种私有信息检索协议，但仍需要借助可信中间服务器实现，存在安全风险.杨松涛等[13]提出了一种基于不经意传输的私有信息检索协议，但是该方法基于欧氏空间设计，存在查询次数多、通信量大等问题.
另外，LBS服务端存储的兴趣点信息也需要保护.通常，LBS服务器只需根据用户兴趣点查询请求为其返回对应的查询结果，不应额外泄漏其他信息，避免恶意攻击者短时间内获得服务端更多兴趣点的详细信息，并据此伪装LBS服务器收集用户隐私等.
针对上述问题，基于不经意传输提出了适用于路网的连续查询位置和查询内容的隐私保护方法，同时可确保LBS服务端的数据安全.该方法具有较好的实用性.
1 系统架构隐私数据具有私密性和排他性，这决定了用户不应将自身隐私数据交给任何假设可信的中心服务器来实施保护处理.因此，采用“用户—LBS服务器”两方实体系统架构，如图 1所示.
|
图 1 系统架构 |
用户根据LBS服务器公布的分块化兴趣点索引表构造不经意传输查询请求发送给LBS服务器，收到查询的LBS服务器无法确定用户的真实查询请求，进而将处理后的密文查询结果发送给用户，并且LBS服务器不知道用户获取的真实查询结果是哪个.系统架构中存在如下假设：①LBS服务器是半可信实体，为用户提供基于位置服务的同时对用户隐私好奇，希望深入挖掘用户深入隐私信息以满足商业利益等，同时，用户对LBS服务器也不可信，不应向用户泄漏过多数据库中的兴趣点分布等信息；②LBS服务器具有较强的分析处理能力，存在勾结其他参与者关联推断用户隐私的可能，LBS服务器和用户之间互不妥协；③通信信道不安全，存在窃听泄漏隐私的可能.
K近邻查询请求可用Q=〈uk, loc, time, K, C〉表示，其中：uk∈U表示用户身份标识，为了不泄漏真实身份及抵御身份标识关联，通常使用假名u′k替换并在每次查询中更换，假名之间无关联；loc表示用户位置，为了保护用户位置隐私，采用特殊的共用锚点位置locanchor替代，使用该锚点还能提高查询处理速度；time表示查询时间戳；K表示查询近邻兴趣点数量；C表示查询内容，即用户感兴趣的目标兴趣点.为了不让LBS服务器知晓用户的真实查询内容隐私，使用1-out-of-n不经意传输技术处理，提交密文查询请求内容C′.
2 路网兴趣点组织结构用户所处路网环境如图 2所示，兴趣点沿路网分布，用户搜索的K近邻兴趣点集PukK实际是从用户当前位置出发，距离自己路网距离最近的K个兴趣点.该集合包含两部分，PukK=PukX+Pvn(K-X)(X≥0, K>0)，PukX是用户当前位置到所在路段前进方向顶点vn间的X个目标兴趣点集合；Pvn(K-X)是从该顶点出发后的(K-X)个目标兴趣点集合.用户要到达其他路段上的某个目标兴趣点，必须先到达所在路段顶点，然后以该顶点为出发点到达.因此，以路网顶点(锚点)为基本生成元，组织路网兴趣点分布如表 1所示.
|
图 2 路网模型 |
|
表 1 LBS端兴趣点分布表 |
表 1各列依次表示路网顶点坐标、邻接顶点集合、兴趣点类型标号、兴趣点类型名称、Kmax个从该顶点出发按距离递增排序的同类近邻兴趣点集合和对应兴趣点详细描述信息，用户每次发起K近邻查询满足K≤Kmax.索引表由表 1的第1~4列构成，并公布给用户，用户据此构造不经意查询请求.为了提高查询处理速度，不采用集中式数据库，而是采用分布式数据库工作模型.将整个地图划分为若干区域，每个区域内部署一个分布式LBS服务.
在查询过程中，所有LBS用户以所在路段的顶点代替自己的真实位置发起查询，当多个不同路段用户共用同个路网顶点作为锚点发起查询时，可以实现用户位置的k匿名，实现用户位置隐私保护.
多个LBS服务器会适当存储交叉区域兴趣点信息，当用户经过重叠区域时，同样是在进入新路段后只发起1次新查询，获取进入新路段后的最新K近邻查询结果，是用户跨重叠区域后新LBS服务器提供的，之前查询过的兴趣点可能还在此查询结果中，但仍然是距离用户路网距离最近的K个兴趣点，因此查询效率和准确率不受影响.
3 基于不经意传输的隐私保护查询方法 3.1 问题描述用户每次利用所在路段锚点vn发起查询，假设LBS服务器的兴趣点分布表中，以该顶点为起点共有m种类型兴趣点P={P1, P2, …, Pm}和随机生成的m个密钥Key={k1, k2, …, km}.用户希望能够得到某个类型兴趣点Px∈P的相关信息，但不希望LBS服务器知道他对此类兴趣点感兴趣.同时，LBS服务器也不希望用户一次获得其他兴趣点的信息.
3.2 1-out-of-n不经意传输隐私保护查询方法不经意传输可以解决上述问题，但通常情况下不经意传输需要1次处理较多兴趣点信息，并多次通信，且存在路网适用性差的问题.为此，基于上述路网兴趣点组织方式，提出一种满足路网K近邻查询的不经意传输方法，在保护用户位置和查询内容隐私实现秘密检索的同时，进一步提高查询效率.
假设q为大素数，Z为q阶群，a、b为Z的生成元，Zq为q的最小剩余集，(a, b, Z)对用户和LBS服务器公开.查询过程如表 2所示.
|
|
表 2 不经意传输方法 |
LBS服务器公布所负责区域内兴趣点索引信息，用户确定自己所在路段
步骤1 用户希望得到索引表中的某个类型标号为x的兴趣点Px∈P的信息，其生成随机数r∈Zq，计算β=arbxmod q，并将原有的查询请求Q=〈uk, loc, time, K, C〉改造成不经意传输查询请求为Q=〈u′k, vn, time, K, β〉发送给LBS服务器，该查询不直接提供用户真实位置和查询内容，分别以用户所在路网锚点vn和1个依据目标兴趣点Px生成的密文符号β代替，这样就生成了1个用保护户位置和查询内容的查询请求.
步骤2 LBS服务器随机生成的m个密钥Key={k1, k2, …, km}满足ki∈Zq, 1≤i≤n，并计算ST={(s1, t1), (s2, t2), …, (sm, tm)}，其中：
hi∈Zq, 1≤i≤n，si=ahimod q，
ti=ki(β/bi)himod q；
同时LBS服务器使用Key={k1, k2, …, km}加密，以顶点vn为生成元的各类型兴趣点数据Ep={Ek1(P1), Ek2(P2), …, Ekm(Pm)}，最终将{ST, Ep}发送给用户.
步骤3 用户计算密钥kx=(tx/(sx)r)mod q，进而得出目标兴趣点Px=Dkx(Ekx(Px)).
LBS服务器返回给用户额外的密文兴趣点查询结果，用户仅能够对其中的目标兴趣点解密，确保了LBS服务器不过多释放信息.在构造查询请求时，Pi∈P是以vn为出发点的某一类兴趣点信息，这种分布式数据库和以路网顶点为生成元的兴趣点组织结构确保了仅对部分兴趣点处理，避免了不经意传输中需要处理大量额外兴趣点信息的问题.
4 安全性分析从LBS服务器的数据安全和用户隐私两方面做安全性分析.
4.1 LBS服务器数据安全由不经意传输方式可知，LBS服务器每次返回的查询结果中，用户依据式(1)计算得出密钥kx，
| $ {k_x} = \frac{{{t_x}}}{{{{({s_x})}^r}}}{\rm{mod}}\;{q}{\rm{ = }}\frac{{{{k}_{x}}{{({{a}^{r}}{{b}^{x}}{\rm{/}}{{b}^{x}})}^{{h_x}}}}}{{{{({{a}^{{{h}_{x}}}})}^{r}}}}\,\bmod\;{q} $ | (1) |
由于x是用户确定的，而bi中的整数i与其密文查询结果的位置无对应关系，而无法计算出其他密钥ki，用户仅能解密其中一个自己感兴趣的目标兴趣点Ekx(Px).其他兴趣点内容均是经过加密处理的密文结果Eki(Pi)，用户因无法计算出密钥而难以解密，所以每次查询不会泄漏数据库的其他内容.
4.2 用户隐私安全用户每次查询都会选择不同的随机数r∈Zq，所以，连续查询中同类型兴趣点查询也会生成不同的密文查询符号β，这个过程类似一次一密，随机数r的长度选择可以进一步提高破解难度.因此，很难通过猜解密钥方式破解用户的查询内容.
在返回的m个密文查询结果中，由于LBS服务器每个密文结果的生成处理方式相同，所以其确定其中某个兴趣点为用户查询的目标兴趣点的概率为p(x)=1/m，m越大，LBS服务器的不确定性越高.在连续查询中的某个单次查询的信息熵为
| $ H(Q) = \sum\limits_{i = 1} {p(x){\rm{lb}}\frac{1}{{p(x)}} = {\rm{lb}}m} $ | (2) |
用户在连续查询过程中，由于查询请求Q=〈u′k, vn, time, K, β〉中无明显数据关联项，即u′k为每次查询更换的新假名，假名之间无关联；vn代替用户真实位置，多个路段用户共用该锚点可实现位置无关联；β是查询内容的密文替代符号，相互无关联.这样连续查询中的n个单次查询之间相互独立，因此联合信息熵如式(3)所示.此时信息熵值最大，这意味着对于攻击者来说不确定性最高，达到保护用户位置和查询内容隐私的目标.
| $ H({{Q}_{1}}, {{\mathit{Q}}_{2}}, \cdots, {{Q}_{n}})=\sum\limits_{i=1}^{n}{H({{Q}_{i}})=\mathit{n}\rm{lb}\mathit{m}} $ | (3) |
综上，笔者充分考虑了路网兴趣点分布的特点，构造了不经意传输查询请求，既可以保护用户端的位置隐私和查询内容隐私，还能够保护LBS服务器端的数据安全，具有较高的查询效率和准确性.
5 实验实验在Windonws 7云平台上利用JAVA语言实现.地图采用美国国家地质勘探局提供的地理数据集，采用Thomas Brinkhoff路网移动节点数据生成器生成用户位置数据，设置用户向LBS更新位置数据频率f，采用剪枝的办法控制平均路段长度S.通信带宽为3 Mbit/s，每次查询返回单个数据包为1 500 byte，每个兴趣点描述信息设置为300 byte，除去40 byte的包头，包含兴趣点个数约为(1 500－40)/300≈5个, 参数配置如表 3所示.
|
|
表 3 实验默认参数配置 |
查询准确率是指用户获得准确查询结果占全部查询的比率.笔者采用路网兴趣点组织结构，相比欧氏空间查询方法，确保了查询准确性.在查询准确率方面与两种经典方法Cloaking Region[5]、SpaceTwist[6]进行比较的结果如图 3所示.
|
图 3 查询准确率比较(U变化) |
随着用户数量的增长，新方法的查询准确率略有下降但相对稳定，下降的主要原因是用户数量增多带来少量查询请求被丢弃造成的. Cloaking Region方法由于采用了同态加密实现隐私保护查询，服务器处理速度显著下降，造成查询准确率随之下降.而SpaceTwist方法由于返回多余兴趣点较多，在用户数量增长时，查询准确率下降迅速.
5.2 平均处理时间路段长度是本方法中影响查询次数的重要因素之一，如图 4所示，随着用户数量的增长，平均路段长度S增大会使得查询次数减少，使得平均处理时间有所降低.因此可以采用路网图剪枝的方法去掉一些较短路段，提高处理速度.
|
图 4 平均处理时间(U和S变化) |
本文还将本方法与上述经典隐私保护方法在平均处理时间方面进行了比较，如图 5所示.随着用户数量的增加，本方法与SpaceTwist方法的平均处理时间保持稳定，主要是由于处理方法相对简单，而Cloaking Region方法由于采用同态加密技术生成密文查询结果，但处理时间长是其缺陷.
|
图 5 平均处理时间比较(U变化) |
数据通信量主要是来自返回查询兴趣点的描述信息.当移动用户位置不断变化而频繁发起查询时，如图 6所示，Cloaking Region方法处理速度较慢，较多数据包被丢弃，带来了重复数据包量的增加.本方法查询采用固定锚点，用户仅进入新路段时用前方顶点发起一次查询，不因用户位置变化而不断发起连续查询，可保持通信量基本平稳. SpaceTwist方法虽然也采用锚点，但是锚点是随机选取的，重复使用率不高，面对大量用户时存在数据包丢弃率增高问题，进而带来平均数据包量增加.
|
图 6 平均数据包通信量(f变化) |
本文针对用户连续查询中的LBS端数据安全问题和用户端隐私保护问题，基于不经意传输技术，提出了一种能够保证两方数据和隐私安全的K近邻兴趣点查询方法，不仅实现了对两方敏感信息的保护，还提高了查询效率和准确率.实验分析表明，本方法具有较高的查询成功率，平均处理时间相对同态加密处理实现的PIR更为高效，适用于频繁位置变换的路网连续查询.
| [1] |
张学军, 桂小林, 伍忠东. 位置服务隐私保护研究综述[J]. 软件学报, 2015, 9: 2373–2395.
Zhang Xuejun, Gui Xiaolin, Wu Zhongdong. Privacy preservation for location-based services:a survey[J]. Journal of Software, 2015, 9: 2373–2395. |
| [2] | Ni W, Gu M, Chen X. Location privacy-preserving k nearest neighbor query under user's preference[J]. Knowledge-Based Systems, 2016, 103: 19–27. doi: 10.1016/j.knosys.2016.03.016 |
| [3] | Pan X, Xu J, Meng X. Protecting location privacy against location-dependent attacks in mobile services[J]. Knowledge and Data Engineering, IEEE Transactions on, 2012, 24(8): 1506–1519. doi: 10.1109/TKDE.2011.105 |
| [4] | Yi X, Paulet R, Bertino E, et al. Practical approximate k nearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(6): 1546–1559. doi: 10.1109/TKDE.2016.2520473 |
| [5] | Man Lung Yiu, Jensen C S, Xuegang Huang, et al SpaceTwist: Managing the trade-offs among Location Privacy, Query Performance, and Query accuracy in mobile services[C]//2008 IEEE 24th International Conference on Data Engineering. (ICDE 2008). Mexico: IEEE Press, 2008: 366-375. |
| [6] |
黄毅, 霍峥, 孟小峰. CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J]. 计算机学报, 2011, 34(10): 1976–1985.
Hang Yi, Huo Zheng, Meng Xiaofeng. CoPrivacy:A collaborative location privacy-preserving method without cloaking region[J]. Chinese Journal of Computers, 2011, 34(10): 1976–1985. |
| [7] | Gong Z, Sun G Z, Xie X. Protecting privacy in location-based services using k-anonymity without cloaked region[C]//2010 Eleventh International Conference on Mobile Data Management (MDM 2010). Kansas City: IEEE Press, 2010: 366-371. |
| [8] | Niu B, Zhang Z, Li X, et al. Privacy-area aware dummy generation algorithms for Location-Based Services[C]//2014 IEEE International Conference on Communications (ICC 2014). Sydney: IEEE Press, 2014: 957-962. |
| [9] | Zhou C, Ma C, Yang S, et al. A location privacy preserving method based on sensitive diversity for LBS[C]//2014 IFIP International Conference on Network and Parallel Computing (NPC 2014). Berlin Heidelberg: Springer Press, 2014: 409-422. |
| [10] | Ghinita G. Privacy for location-based services[J]. Synthesis Lectures on Information Security, Privacy, & Trust, 2013, 4(1): 1–85. |
| [11] | Yi X, Paulet R, Bertino E, et al. Practical k nearest neighbor queries with location privacy[C]//2008 IEEE 30th International Conference on Data Engineering (ICDE 2014). Chicago: IEEE Press, 2014: 640-651. |
| [12] |
周长利, 田晖, 马春光, 等. 路网环境下基于伪随机置换的LBS隐私保护方法研究[J]. 通信学报, 2017(6): 19–29.
Zhou Changli, Tian Hui, Ma Chunguang. Research on LBS privacy preservation based on pseudorandom permutation in road network[J]. Journal on Communications, 2017(6): 19–29. doi: 10.11959/j.issn.1000-436x.2017120 |
| [13] |
杨松涛, 马春光, 周长利. NCoP:无用户协作的LBS隐私保护方法[J]. 北京邮电大学学报, 2014, 37(6): 86–90.
Yang Songtao, Ma Chunguang, Zhou Changli. NCoP:A non-Cooperative location privacy-preserving method[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(6): 86–90. |