2. 佳木斯大学 信息电子技术学院, 黑龙江 佳木斯 154007
位置k-匿名技术假设匿名集内的用户具有相同的安全性, 这与现实情况不符.借鉴安全多方计算理论, 提出了一种分布式结构下的无用户协作位置隐私保护方法.该方法仍然基于时空匿名思想, 利用不经意传输概念设计了隐私感知查询协议.安全性分析和仿真实验结果表明, 该方法不仅满足位置k-匿名和位置模糊的条件, 而且取得了更高的隐私性.
2. College of Information and Electronic Technology, Jiamusi University, Heilongjiang Jiamusi 154007, China
Assume that anonymous participants have the same level of security is inconsistent and often questionable with the actual scenario in location k-anonymity techniques. The article drew from the theory of secure multiparty computation and presented a non-cooperative location privacy-preserving method in the distributed structure. Based on the spatial-temporal cloaking, the method introduced oblivious transferring for design privacy-aware query protocols. Security analysis and simulation show that this method can meet the conditions of the location k-anonymity and location obfuscation, and can achieve greater privacy.
隐私保护是基于位置服务(LBS, location-based services)中的挑战性问题，成为阻碍LBS被广泛接受和应用的主要原因[1-2].在LBS隐私保护技术研究中，中心匿名器结构[3-7]、点对点分布式结构[8-10]和空间k-匿名思想被学术界广泛接受.以上研究均假设参与匿名的各方是可信的，但是，匿名参与者可能直接或间接泄露精确的位置信息.加密技术提供了可靠的隐私保障，将私有信息检索(PIR, privacy information retrieval)理论引入LBS隐私保护领域[11].笔者针对中心匿名器结构中存在的位置匿名器成为系统瓶颈的问题和协作点对点分布式结构中存在的匿名集内用户缺乏相互信任的问题，设计了基于不经意传输概念的隐私感知查询协议，提出无用户协作的LBS隐私保护(NCoP, non-cooperative privacy)方法.该方法将以往的查询请求分为位置查询Q和内容查询Q′，借鉴安全两方计算理论实现安全的LBS查询.
1 系统结构基于无协作点对点分布式结构的隐私保护方法是近几年出现的一种新型的LBS隐私保护方法，这种方法无须用户与中心匿名器以及其他用户之间的交互，仅有用户与LBS服务器之间交互的C/S结构，如图 1所示.
|
图 1 系统结构 |
系统中存在以下几个假设：① 用户和LBS服务器都是半诚实参与主体，LBS服务器希望获悉用户的轨迹，进而挖掘出更多的隐私数据，用户希望通过1次查询获得更多的信息；② 通信信道是不安全的，攻击者有可能窃听二者之间的通信数据；③ LBS服务器的计算能力远远大于用户终端的计算能力；④ LBS服务器有可能勾结其他方参与攻击，但是LBS服务器和用户之间是互不妥协的.
定义1 LBS查询.基于位置查询时，用户u向LBS服务器提供了时空数据Data={U，L，T，C}.其中：U为用户身份标识，L为用户u所在的当前位置，T为当前时间，C为查询内容.
定义2 兴趣点(POIs，points of interest).在LBS系统中，用户感兴趣的信息点称为“兴趣点”，可以形式化表示为P={g，l，f}.其中：g为POIs的类型，l为POIs所在的位置坐标，f为POIs的服务内容信息.给定POIs类型集合G={g1，g2，…，gm}，POIs集合P={p1，p2，…，pn}，有pi. g∈G，1≤i≤n.
定义3 位置查询Q.位置查询Q可以形式化表示为Q={sm，lm，R，Cs，t}.其中：sm为LBS服务器的标识符，lm为位置查询的标识符，R为查询的地理范围，Cs为G的子集合，t为查询的时间.
定义4 内容查询Q′.内容查询Q′可以形式化表示为Q′={sm，cm，lq，t′}.其中：cm为内容查询的标识符，lq为P. l的集合，t′为查询时间.
2 面向LBS的NCoP方法2.1 1-out-of-n不经意传输协议问题描述：假设LBS服务器有n个POIs信息M={M1，M2，…，Mn}和随机生成的n个密钥K={k1，k2，…，kn}.查询用户Alice希望得到Ma(1≤a≤n)，但是不希望LBS服务器知道她得到了哪一个信息.同时，LBS服务器仅为Alice提供Ma，但是不希望Alice获得更多的信息.
笔者使用1-out-of-n不经意传输协议可以解决以上问题[12].假设q为大素数，Z为q阶群，α、β为Z的生成元，Zq为q的最小剩余集，(α，β，Z)对于Alice和LBS服务器是公开的. 1-out-of-n不经意传输协议如图 2所示.
|
图 2 1-out-of-n不经意传输协议 |
步骤1 Alice希望得到Ma(1≤a≤n)，产生随机数r∈Zq，计算y=αrβamod q，并将y发送给LBS服务器.
步骤2 LBS服务器计算ST={(s1，t1)，(s2，t2)，…，(sn，tn)}，其中：
|
并将ST发送给Alice.
步骤3 LBS服务器使用K对M加密，得到的加密数据集合为EM={Ek1(M1), …, Ekn(Mn)}，并将EM发送给Alice.
步骤4 Alice计算ka=(ta/(sa)r)mod q，并计算Ma=Eka(Ma).
2.2 隐私感知查询协议问题描述：移动用户Alice希望获得周边POIs的相关信息. Alice周围有多个POIs，但是她仅关心某一个POIs信息.例如，Alice向LBS服务器发出查询请求“离我最近的商场的折扣信息”. LBS服务器检索数据库，并向用户反馈查询结果.在没有隐私保护机制的情况下，LBS服务器有能力推断出Alice的隐私数据，甚至可能泄露给其他方. Alice既希望获得高质量的服务又不想暴露其位置信息.
在图 3中，Cal()为欧氏距离计算函数，Pick()为随机提取函数，Disorder()为随机扰乱函数，Retrieval()为信息检索函数，Query()为查询函数.
|
图 3 隐私感知查询协议 |
步骤1 Alice向LBS服务器发出位置查询Q，Q. Cs中包含Alice真实查询的POIs类型，记为gi.
步骤2 LBS服务器以Q. Cs内每个元素为关键字检索数据库，找到地理位置在Q. R范围内的所有POIs的位置信息集合A：
|
A也可以表示为
|
其中Aj为以gj为关键字检索到的POIs位置集合.
步骤3 LBS服务器将A发送给Alice.
步骤4 Alice使用当前位置与Ai中每个坐标进行欧氏距离计算，得到距离自己最近的Pi. l.从每个Aj(1≤j≤n)中随机提取一个Pj. l，1≤j≤n且i≠j.最后形成集合lq.
步骤5 Alice扰乱lq的顺序，并向LBS服务器发出内容查询Q′.
步骤6 LBS服务器根据lq依次查询P. f.
步骤7 LBS服务器与Alice之间执行1-out-of-n不经意传输协议.
3 隐私性分析下面从位置不可追踪性、查询内容不可关联性和抗攻击能力3个角度分析k-匿名方法、PIR方法和NCoP方法.
3.1 NCoP对比位置k-匿名1) 位置k-匿名方法.首先，用户或匿名器需要提交一个匿名空间区域给LBS服务器.查询用户一定出现在该区域内，攻击者能根据用户分布、路网限制和移动速度以及方向等背景知识逐步缩小此区域.因此，用户的位置轨迹是可追踪的，精确度取决于攻击者的分析能力.其次，匿名集内的用户不是等概率发出查询，一些用户安全的脆弱性会带来整个匿名集安全性下降.因此，查询内容和用户身份是可关联的，攻击者可以将查询发出者限定为某些特定的用户.
2) NCoP方法.位置查询Q中包含用户选择的查询范围Q. R，它可以是1条街道、1个商场或1个行政区域.用户可以出现在Q. R的内部，也可以出现在外部. Q. R的大小、形状和位置由用户根据所处环境和喜好来指定.首先，内容查询Q′不包含用户的位置信息，从而不会暴露用户位置，攻击者的最小推断区域是整个服务空间.因此，NCoP方法具备位置不可追踪性；其次，Cs的纬度由用户定义，达到了查询内容k-匿名效果.利用不经意传输协议，LBS服务器不知道用户得到了哪个信息，同时用户不会得到任何其他的信息.因此，从攻击者角度分析，用户真实身份和查询POIs是不可关联的.由于协议执行过程中不需要构建匿名框和匿名集，基于位置k-匿名技术的一些常用攻击方式对于NCoP方法是无效的.
3.2 NCoP对比PIR对于用户u和数据库DB，PIR是指u从DB中秘密检索第i条记录，服务器无法确定i的值.换句话说，服务器无法确定u对第i条记录感兴趣.通常PIR协议不限制用户从数据库中获得的POIs信息数量，与不经意传输协议相比，它没有保护LBS服务器资源的安全性. NCoP方法和PIR方法具有同等的隐私安全性，PIR方法更侧重于减少通信量，而NCoP方法更侧重于减少计算量.
4 仿真实验仿真实验在处理器Intel(R) Core(TM) i3-2310M CPU，内存2 GB的平台上实现.通常来说，计算效率是基于加密的位置隐私保护方法面临的主要挑战问题.第1个实验研究1次查询的平均计算时间. NCoP方法的执行效率主要依赖于参数R，假设R的面积与候选POIs数量成正比.
图 4所示为NCoP方法与典型的Casper[4]、PIR[11]方法的比较结果.结果显示，3种方法的平均查询时间都与POIs数量呈线性关系. NCoP方法和PIR方法主要的计算是密集的模指数计算.从计算效率角度分析，模指数计算是最复杂的，其他操作(加法、乘法和除法)是比较容易的.因此，Casper在平均计算时间上优于其他2种方法.由于NCoP方法仅在内容查询阶段进行有限的几个模指数计算(如αr、si、ti)，而PIR方法对每位进行模指数计算，所以NCoP方法在平均计算时间上优于PIR.
|
图 4 计算花费 |
第2个实验关注2个查询阶段的通信花费. 图 5显示通信花费与R呈线性关系.位置查询阶段的通信花费较低，因为主要是LBS服务器传送一些POIs的坐标给客户端.内容查询阶段的通信花费持续增长，如果设定POIs的分类最多为50个，则上限大约为550 kbit.
|
图 5 通信花费 |
第3个实验关注每次查询中用户获得的POIs数量. 图 6显示，为了维护一个适当的POIs候选集，Casper方法需要大量的用户持续地位置更新；不采用k-匿名方式，PIR方法中揭露的POIs数量是固定的；NCoP方法中的候选POIs数量从50到1逐步下降，但是揭露的POIs仅为1个.
|
图 6 候选POIs |
研究了LBS系统中的隐私保护问题，基于无协作点对点分布式结构设计了隐私感知查询协议，主要解决了2个基本问题：① 保证个人隐私的前提下实现有效查询，满足位置不可追踪和身份不可关联属性；② LBS服务器资源不能被恶意用户窃取，LBS服务器虽然是不可信的，但是LBS服务器上的信息资源是珍贵的，笔者设计了不经意传输协议，确保用户仅能得到需要的服务信息.仿真实验表明，查询处理时间、通信量与用户隐私度、POIs数量及其分布相互影响，严格的隐私保护要求必然要牺牲服务质量.服务质量和隐私保护双方不存在合作的可能.进一步研究将考虑用户分布和POIs分布对查询效率的影响.
| [1] | Benisch M, Kelley P G, Sadeh N, et al. Capturing location-privacy preferences: quantifying accuracy and user-burden tradeoffs[J].Personal and Ubiquitous Computing, 2011, 15(7): 679–694. doi: 10.1007/s00779-010-0346-0 |
| [2] | Zhou Tao. The impact of privacy concern on user adoption of location-based services[J].Industrial Management and Data Systems, 2011, 111(1): 212–226. |
| [3] | Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//2003 International Conference on Mobile Systems, Applications and Services. San Francisco, California: ACM, 2003: 31-42. |
| [4] | Chow C, Mokbel M F, Aref W G. Casper*: query processing for location services without compromising privacy[J].ACM Transactions on Database Systems, 2009, 34(4): 24–48. |
| [5] | Bamba B, Liu Ling, Pesti P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]//2008 International Conference on World Wide Web. Beijing, China: ACM, 2008: 237-246. |
| [6] | Lee B, Oh J, Yu H, et al. Protecting location privacy using location semantics[C]//2011 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, California: ACM, 2011: 1289-1297. |
| [7] | Xu T, Cai Ying. Feeling-based location privacy protection for pocation-based services[C]//2009 ACM Conference on Computer and Communications Security. Chicago, Illinois: ACM, 2009: 348-357. |
| [8] | Chow C Y, Mokbel M F, Liu Xuan. A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//2006 ACM International Symposium on Advances in Geographic Information Systems. Arlington: ACM, 2006: 171-178. |
| [9] | Ghinita G, Kalnis P, Skiadopoulos S. PRIVE: anonymous location-based queries in distributed mobile systems[C]//2007 International Conference on World Wide Web. New York: ACM, 2007: 371-380. |
| [10] | Li Wei, Liu Chunlei. A decentralized location-query-sensitive cloaking algorithm for LBS[C]//2012 IEEE International Wireless Communications and Mobile Computing Conference. Limassol, Cyprus: IEEE, 2012: 1040-1045. |
| [11] | Ghinita G, Kalnis P, Khoshgozaran A, et al. Private queries in location-based services: anonymizers are not necessary[C]//2008 ACM SIGMOD International Conference on Management of Data. Vancouver, Canada: ACM, 2008: 121-132. |
| [12] | Tzeng W. Efficient 1-out-of-n oblivious transfer schemes with universally usable parameters[J].IEEE Transactions on Computers, 2004, 53(2): 232–240. doi: 10.1109/TC.2004.1261831 |