Geohash编码的k匿名位置隐私保护方案

k Anonymous Location Privacy Preservation Scheme Based on Geohash Coding

摘要

采用k匿名技术的位置隐私保护方案为了构造匿名位置集，检索历史数据库的时间开销往往较大，位置服务失去了即时的优越性。为解决此问题，提出了基于Geohash编码的k匿名位置隐私保护方案。该方案将用户的经纬度坐标位置泛化到一个区间区域，使用Geohash算法编码；选取与Geohash编码相同的位置，经反向检索构成候选匿名位置集；筛选多余位置时兼顾历史查询概率，再附上k-\mathrm{1}个伪查询以混淆用户的真实查询内容；收到查询请求服务后，位置服务器获取并加密查询结果，用户再解密获得查询结果，最终实现k匿名位置隐私保护。在双线性映射的相关问题假设前提下，该方案满足正确性、验证性和匿名性，可以抵抗伪装攻击、重放攻击和共谋攻击。仿真实验显示，在处理数据的时间开销和匿名隐私度上，本文提出的方案具有更好的优越性。

Abstract

It takes a lot of time for the location privacy preservation schemes using k anonymity technology to retrieve the historical database to construct an anonymous location set, then the location service loses the advantage of instant response. In order to provide real-time location service, the user's coordinate position expressed by the longitude and latitude is generalized to an interval area, which is encoded by Geohash algorithm. The locations with the same code are selected, and the reverse retrieval technology is used to form a candidate anonymous location set. When screening redundant locations, the historical query probability is considered, and k-\mathrm{1} pseudo queries are attached to confuse the user's real query content. After receiving the query request service, the location server obtains and encrypts the query results, and the user decrypts the query results. Finally, k anonymous location privacy preservation is realized. Based on some assumptions related to bilinear map, the proposed scheme has the properties of correctness, verification and anonymity, and can resist impersonation attack, replay attack and collusion attack. Simulation results show that the proposed scheme has better advantages in the processing data time and anonymity privacy.

Graphical abstract

关键词

Geohash编码 / 位置服务 / k匿名 / 隐私保护 / 移动终端

Key words

Geohash encoding / location-based service / k-anonymity / privacy preservation / mobile terminal

0　 引 言

基于位置的服务（location based service，LBS）是通过无线电通信技术或全球定位系统（global　positioning system，GPS）获取移动终端用户的位置信息，在地理信息系统（geographic information system，GIS）的支持下，为移动终端用户提供相应服务^［1］。随着通信技术和GPS的发展，LBS得到广泛的应用。人们在享受交通导航、网上订票等LBS带来便捷的同时，也在承担着个人位置隐私泄露的风险。攻击者能够从位置信息中，推测出用户的家庭地址、工作地点、常去的服务场所等隐私信息，了解到用户的行动轨迹^［2］。随着LBS使用规模的不断增长，位置隐私的安全问题成为了重要的研究课题^［3，4］。

位置隐私保护按照体系结构大致分为两类：基于匿名中心的位置隐私保护方案^［5，6］和基于移动终端的位置隐私保护方案^［7~11］。在基于匿名中心的位置隐私保护方案中，用户和LBS服务器之间，引入可信的匿名中心，匿名中心通过隐私保护技术^{［12，13］}将用户的位置服务信息匿名化，再发送给LBS服务器请求服务，并将LBS服务器反馈的服务结果返回给用户。在这类方案中，匿名中心承担着主要的计算和通信工作，成为整个系统的安全瓶颈，一旦被攻克，所有用户的隐私信息都将被泄露。Peng等^［14］使用半可信匿名中心替代匿名中心，但半可信匿名中心依旧会成为系统的安全瓶颈。为了避免单匿名中心的安全瓶颈问题，张少波等^［3］引入多个分布式匿名服务器，但该方案会引起系统开销的增加。随着移动终端不断智能化，计算和存储能力大大增强，出现了基于移动终端的位置隐私保护方案。这类方案不再设置匿名中心，移动终端用户直接与LBS服务器通信，获得请求查询服务的结果，从而避免了匿名中心的安全瓶颈和单点泄露问题。很多学者基于移动终端展开位置隐私保护研究，例如，李维皓等^［8］使用移动模型预测用户移动轨迹，利用时空关联性生成伪位置来避免位置隐私泄露。Hayashida等^［9］利用旅行推销商贪心算法生成虚假轨迹来隐藏用户的隐私位置。Niu等^［10］使用背景信息中的历史查询概率，并尽量选择相隔较远的匿名位置来实现位置隐私保护。李维皓等^［11］在背景信息的基础上，考量了用户和LBS服务器短期缓存的查询记录，实现自关联隐私保护算法。

位置隐私保护通常使用k匿名技术，它是由Gruteser等^［15］最先提出的。该技术将用户的真实位置与其他k-1个虚假位置组成匿名位置集，发送给LBS服务器请求服务，如此一来，用户的真实位置被猜测成功的概率为1/k，从而有效地实现了用户位置的匿名。其中，k代表隐私度，由用户根据需求确定数值。为了构建匿名位置集，通常需要查询历史请求记录，可是检索庞大的历史记录，时间开销较大，使得位置服务失去了即时的优越性。为了给用户提供即时的位置服务，本文借助Geohash编码^［16］，实现了面向移动终端用户的k匿名位置隐私保护方案。

1　 基本概念

1.1　区间区域

lat代表纬度（Latitude），lng代表经度（Longitude）。通常约定纬度在前，经度在后，经度与纬度组成地理坐标系统 （geographic coordinate system，GCS），简称坐标系统。GCS使用三维球面来定义地球表面位置，能够标示地球上的任何一个位置。经度的区间范围为［-180°，180°］，东经为正数，西经为负数；纬度的区间范围为［-90°，90°］，北纬为正数，南纬为负数。

如果将用户的经纬度坐标，泛化到一个经纬度区间（［lat1，lat2］，［lng1，lng2］），那么这个区间所表示的区域称为区间区域。

一个用户的经纬度坐标（30.299 4°，70.153 6°），泛化后的区间区域（［30.273°，30.311 9°］，［70.130 6°，70.176 6°］），如图1中红色方框。泛化的方法将在2.3节描述。

1.2　Geohash编码

Geohash算法^［17］将二维经纬度坐标转换为一维字符串的地理位置编码。Geohash算法利用数据结构的二分法，沿着经度和纬度两个不同方向，交替地二分地球表面。具体过程如下。

Step 1 经度区间的划分。对［-180°，180°］进行二分，区间的中位值=（-180°+180°）/2=0°，小于中位值则为左区间［-180°，0°），标记为0；否则将右区间［0°，180°］标记为1。采用同样的方法继续对左右经度区间进行二分，直到需要的精度停止，得到一个由0和1组成的经度编码序列。

Step 2 纬度区间的划分。对［-90°，90°］进行二分，区间的中位值=（-90°+90°）/2=0°，小于中位值则为左区间［-90°，0°），标记为0；否则将右区间［0°，90°］标记为1。采用同样的方法继续对左右纬度区间进行二分，直到需要的精度停止，得到一个由0和1组成的纬度编码序列。

Step 3 交错排列。按照偶数位放经度编码，奇数位放纬度编码，将经度字符串和纬度字符串合并成一个新的编码序列。

Step 4 分组转换。将新的编码序列从右向左，每5位成一组，最后一组不够5位，左边补0。每组的5位编码转换成一个十进制数。

Step 5 Base32编码。对照Base32编码表，将每个十进制数转换成Base32码，按序存放各个Base32码，形成Geohash编码。

例如，对图1中的用户经纬度坐标（30.299 4°， 70.153 6°），纬度30.299 4°按照表1进行纬度编码，得到二进制编码序列101010110001011，经度70.153 6°按照表2进行经度编码，得到二进制编码序列101100011110001。纬度编码和经度编码交错排列后，形成新的二进制编码序列11001 11001 00011 11010 10010 00111，转换成十进制数序列25 25 3 26 18 7。按照表3将十进制数序列转换成Geohash编码tt3uk7。

Geohash编码代表的是一个矩形区域，编码的长度越短，矩形区域越大；编码的长度越长，矩形区域越小。当纬度相同时，经度每隔0.000 01°，宽度相差大约1 m；每隔0.000 1°，宽度相差大约10 m。以此类推，每隔0.1°，宽度相差大约10 000 m。当经度相同时，纬度每隔0.000 01°，宽度相差大约1.1 m；每隔0.000 1°，宽度相差大约11 m。以此类推，每隔0.1°，宽度相差大约11 132 m。可见，Geohash编码长度越长，所表示的范围就越精确。例如，编码长度为5时，精度大约为4 900 m；编码长度为8时，精度大约为19 m。Geohash编码长度取决于位置隐私保护的强度，由用户指定。用户想获得较高的位置隐私保护强度，矩形区域需要较大，对应的编码长度就短一些。

1.3　双线性映射

对于阶为q的加法循环群G₁和乘法循环群G_T，双线性映射e:G_{\mathrm{1}}\times G_{\mathrm{1}}\to G_T具有如下性质：

1） 双线性：任意的Q_{\mathrm{1}},Q_{\mathrm{2}}\in G_{\mathrm{1}}，x,y\in \mathrm{\mathbb{Z}}{}_p{}^{}，满足e(x{Q}_{\mathrm{1}},y{Q}_{\mathrm{2}})=e(Q_{\mathrm{1}},Q_{\mathrm{2}}{)}^{xy}；

2） 可计算性：任意的Q_{\mathrm{1}},Q_{\mathrm{2}}\in G_{\mathrm{1}}，均可计算e(Q_{\mathrm{1}},Q_{\mathrm{2}})；

3） 非退化性：任意的Q_{\mathrm{1}},Q_{\mathrm{2}}\in G_{\mathrm{1}}，满足e(Q_{\mathrm{1}},Q_{\mathrm{1}})\ne I，I为G_T 中的单位元；

4） 对称性：任意的Q_{\mathrm{1}},Q_{\mathrm{2}}\in G_{\mathrm{1}}，满足e(Q_{\mathrm{1}},Q_{\mathrm{2}})=e(Q_{\mathrm{2}},Q_{\mathrm{1}})。

1.4　双线性映射的相关问题假设

1）　椭圆曲线离散对数(elliptic curve discrete logarithm,ECDL)问题

椭圆曲线上阶为q的循环群G，P为G的生成元，给定Q=xP\in G（随机数x\in {\mathrm{\mathbb{Z}}}_q^{\mathrm{*}}值未知），敌手在多项式时间内计算x。若满足\mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{E}\mathrm{C}\mathrm{D}\mathrm{L}}=\mathrm{P}\mathrm{r}[A(Q,P)=x]\ge \epsilon，则说明：不存在概率多项式时间算法A，以不可忽略的概率\epsilon解决ECDL问题。

2）　双线性Diffie⁃Hellman(bilinear Diffie⁃Hellman,BDH)问题

对于阶为q的加法循环群G₁和乘法循环群G_T，P为G₁的生成元，双线性映射e:G_{\mathrm{1}}\times G_{\mathrm{1}}\to G_T，给定输入(P,xP,yP,zP)\in G_{\mathrm{1}}（随机数x,y,z\in {\mathrm{\mathbb{Z}}}_q^{\mathrm{*}}值未知），敌手在多项式时间内计算e{(P,P)}^{xyz}\in G_T。若满足

\mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{B}\mathrm{D}\mathrm{H}}=\mathrm{P}\mathrm{r}[A(P,xP,yP,zP)=e{(P,P)}^{xyz}]\ge \epsilon

则说明：不存在概率多项式时间算法A，以不可忽略的概率\epsilon解决BDH问题。

3）　判定双线性Diffie⁃Hellman(decisional bilinear Diffie⁃Hellman,DBDH)问题

对于阶为q的加法循环群G₁和乘法循环群G_T，P为G₁的生成元，双线性映射e:G_{\mathrm{1}}\times G_{\mathrm{1}}\to G_T，给定输入(P,xP,yP,zP,C)（随机数x,y,z\in {\mathrm{\mathbb{Z}}}_q^{\mathrm{*}}值未知，C\in G_T），敌手在多项式时间内判断等式C=e{(P,P)}^{xyz}是否成立。若满足

\mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}=|\mathrm{P}\mathrm{r}[A(P,xP,yP,zP,e{(P,P)}^{xyz})=\mathrm{1}]|-|\mathrm{P}\mathrm{r}[A(P,xP,yP,zP,C)=\mathrm{1}]|\ge \epsilon

则说明：不存在概率多项式时间算法A，以不可忽略的概率\epsilon解决DBDH问题。

1.5　位置熵

匿名区域AA中包括k个候选位置，假设各个候选位置被检索的概率分别为Q{}_i{}^{}(i\in [\mathrm{1},k])，则每个候选位置成为真实位置的概率为\mathrm{P}\mathrm{r}(i)=Q_i/{\displaystyle \sum _{i=\mathrm{1}}^k}{Q}_{{}_i}，位置熵^［18］为H(R)=-{\displaystyle \sum _{i=\mathrm{1}}^k}\mathrm{P}\mathrm{r}(i)\mathrm{l}\mathrm{g}\mathrm{P}\mathrm{r}(i)。如果候选位置的位置熵越大，隐私度就越高。

2　 k匿名位置隐私保护方案

本文提出的位置隐私保护方案由两类实体：移动终端用户（mobile user，MU）和LBS服务器组成，如图2所示。

位置隐私保护方案采用k匿名机制，两类实体之间的操作步骤和信息交流如下。

Step 1 MU通过智能手机向GPS请求自身位置，获得经纬度坐标（lat，lng）后，在周围生成k-1个虚假位置和虚假查询，然后将自身位置、真实查询和k-1个虚假位置、虚假查询，组成k个查询请求，发送给LBS服务器。

Step 2 LBS服务器收到查询请求后，获取k个查询结果，加密查询结果并通过基站返回给MU。

Step 3 MU收到加密的查询结果后，解密获得想要的查询结果。

2.1　系统初始化

对于LBS服务器，按照下面的步骤获取系统私钥，公开系统公共参数。

Step 1 选择一个大素数p，q是p-1的大素因子，阶为q的加法循环群G₁和乘法循环群G₂，P为G₁的生成元，存在双线性映射e:G_{\mathrm{1}}\times G_{\mathrm{1}}\to G_{\mathrm{2}}。

Step 2 设置3个哈希函数：H_{\mathrm{1}}:{\{\mathrm{0,1}\}}^{\mathrm{*}}\to {G_{\mathrm{1}}}^{\mathrm{*}}， H_{\mathrm{2}}:G_{\mathrm{2}}\to {\{\mathrm{0,1}\}}^n，H_{\mathrm{3}}:\mathrm{S}\mathrm{H}\mathrm{A}\mathrm{256}哈希函数。其中，n是一个整数，{\{\mathrm{0,1}\}}^{\mathrm{*}}是任意长度的二进制字符串。

Step 3 选取一个随机数s\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}作为系统的私钥并保密存储，计算对应的公钥\mathrm{P}\mathrm{K}=s\cdot P。

Step 4g是{{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}上的q阶元素，将S=g^s\mathrm{m}\mathrm{o}\mathrm{d}p保密，计算验证参数\mathrm{S}\mathrm{P}\mathrm{K}=S\cdot P，以便用户验证注册信息。

Step 5 公开系统公共参数：｛G₁，G₂，H₁，H₂， q，P，e，n，PK，SPK｝。

2.2　用户注册

移动终端用户MU需要向系统注册，注册过程如下。

Step 1 MU将k个身份信息组成的集合ID=｛ID₁，ID₂，…，ID _u，…，ID _k ｝发送给LBS服务器进行注册申请。其中，ID _u 作为MU的真实身份，隐藏在集合ID中，u\in [\mathrm{1},k]，其值由MU指定。

Step 2 LBS服务器选择随机数\mathrm{I}{\mathrm{D}}_{\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{y}}\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}，为每个ID _i 计算假名\mathrm{P}\mathrm{I}{\mathrm{D}}_i=H_{\mathrm{3}}(\mathrm{I}{\mathrm{D}}_i+\mathrm{I}{\mathrm{D}}_{\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{y}})、公钥\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_i=H_{\mathrm{1}}(\mathrm{I}{\mathrm{D}}_i)和私钥\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_i=S\cdot \mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_i，生成信息Reg=｛（PID₁，PKID₁，SKID₁），（PID₂，PKID₂，SKID₂），…，（PID _k，PKID _k，SKID _k ）｝，并通过安全信道反馈给MU。

Step 3 MU收到Reg后先计算\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u=H_{\mathrm{1}}(\mathrm{I}{\mathrm{D}}_u)，然后验证等式e(\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,P)=e(\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,\mathrm{S}\mathrm{P}\mathrm{K})是否成立。若成立，则MU收到了正确的假名、公钥和私钥；否则，MU转Step 1重新注册。

2.3　位置泛化

MU通过GPS获得自己的经纬度坐标位置（lat，lng）后，将坐标位置泛化到一个区间区域内。MU根据自身所处的位置是在人口密集的城市还是在稀疏的乡村，选择不同大小的随机数来构建区间区域。若处在人口较为稀疏的乡村，为了提高位置隐私保护的强度，MU匿名的泛化区域设置大一点，随机数选择也大一些。反之，若处在人口较为密集的城市，为了提高查询服务的精度，MU匿名的泛化区域设置小一点，随机数选择也小一些。

1） 人口较为稀疏的乡村：从［0°~0.025°］区间中随机选择4个随机数r₁，r₂，r₃，r₄，为了避开区间的对称性猜测，泛化区间时不同时向前或向后波动随机数，泛化后的区间区域可以表示为（［lat-r₁，lat+r₂］，［lng-r₃， lng+r₄］）。从1.2节可知，经度0.025°大约对应2.5 km的距离，纬度0.025°大约对应2.75 km的距离。若经纬度向前后各波动0.025°，泛化的区间范围大约为（0.025×2/0.025）×2.5×（0.025×2/0.025）×2.75=27.5 km²。通常，随机数的产生遵循正态分布，即在区间的中位值（0°+0.025°）/2= 0.0125°左右波动，而接近区间的端点0°和0.025°较少。因此，按照平均波动0.012 5°来计算，泛化的区间范围平均为（0.0125×2/0.025）×2.5×（0.0125×2/0.025）×2.75=6.875 km²。

2） 人口较为密集的城市：从［0°~0.01°］区间中随机选择4个随机数r₁，r₂，r₃，r₄，泛化后的区间区域（［lat-r₁，lat+r₂ ］，［lng-r₃，lng+r₄ ］）。经度0.01°大约对应1 km的距离，纬度0.01°大约对应1.1 km的距离。若经纬度向前后各波动0.01°，泛化的区间范围大约为（0.01×2/0.01）×1×（0.01×2/0.01） ×1.1=4.4 km²。通常，随机数在区间的中位值（0°+0.01°）/2=0.005°左右波动，而接近区间的端点0°和0.01°较少。因此，按照平均波动0.005°来计算，泛化的区间范围平均为（0.005×2/0.01）×1×（0.005×2/0.01）×1.1=1.1 km²。

2.4　反向检索位置

MU按照1.2节的方法生成Geohash编码，其对应一个矩形区间，如图3所示。该区间内的所有位置，其Geohash编码相同。

检查相同Geohash编码的位置个数，如果与k值相等，则返回这k个位置组成的匿名位置集C。如果小于k值，则扩大到相邻的8个矩形区域。倘若扩大区域后匿名位置的个数仍然小于k值，可以再扩大一圈矩形区间，当然这种情况一般很少出现。如果大于k值或经过扩大区域后大于k值，转筛选多余位置。

2.5　筛选多余位置

如图4所示，将匿名位置的分布区域等分为8×8的位置单元，根据历史查询概率^［19］，每个位置单元填充不同的灰度。其中，灰度越深，代表历史查询概率越高；反之，灰度越浅，代表历史查询概率越低。

假设k=5，则除了MU自身位置外，还需要再筛选出k-1=4个匿名位置。在t时刻，MU位于位置单元C₁中，其历史查询概率为P（C₁）。而C₂~C₁₀各个区间的历史查询概率P（C_i ）=P（C₁）（i=2，3，…，10）。若在t-\mathrm{1}时刻，MU刚刚在C₅处发起过相似查询。当两个时刻之间的差值\mathrm{\Delta }t足够小时，攻击者会发现MU在短时间内搜索过C₅处的服务，从而使得该位置被泄露的概率由1/5增加到1/4，提高了隐私泄露的风险。因此，排除查询过的C₅位置，匿名查询位置集C=｛C₁，C₂，C₃，C₆，C₁₀｝。

2.6　请求位置服务

假设经过反向检索后，MU得到的匿名位置集C=｛C₁，C₂，…，C_u，…，C_k ｝。其中，C_u 是MU的真实位置，隐藏在集合C中，只有MU知道u的值。MU请求位置服务过程如下。

Step 1 LBS服务器随机选择n(n\ge k)个随机数d_i\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}，计算P_i=d_i\cdot \mathrm{P}\mathrm{K}，将｛P₁，P₂，…，P_n ｝作为选择基点公布。

Step 2 MU随机选择k个基点和k个随机数a_i\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}，计算V_i=a_i\cdot P_i，i=1，2，…，k。

Step 3 MU结合注册阶段获得的k个假名集合，反向检索阶段获得的k个匿名位置集合，以及伪查询内容集合，生成查询信息Msg=｛（PID₁，C₁，Q₁，V₁），（PID₂，C₂，Q₂，V₂），…，（PID _k，C_k，Q_k，V_k ）｝发送给LBS服务器请求位置服务。其中，Q_u 是C_u 的真实查询请求。

Step 4 LBS服务器收到Msg后，获取k个查询结果的集合M=｛m₁，m₂，…，m_u，…，m_k ｝，选取随机数b\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}，计算Y_{\mathrm{0}}=b\cdot \mathrm{P}\mathrm{K}，Y_i=b\cdot V_i，n_i=m_i\oplus H_{\mathrm{2}}(e(P_i+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)将Res=｛Y₀，（Y₁，Y₂，…，Y_k ），（n₁，n₂，…，n_k ）｝反馈给MU。

Step 5 MU收到Res信息后，判断e(V_u,Y_{\mathrm{0}})=e(Y_u,\mathrm{P}\mathrm{K})是否成立。若成立，计算乘法逆元{a_u}^{-\mathrm{1}}\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}和解密密钥A_u={a_u}^{-\mathrm{1}}\cdot Y_u，计算m_u=n_u\oplus H_{\mathrm{2}}(e(A_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))，获取需要的查询结果。

3　 方案分析

3.1　性质分析

定理1 正确性：用户可以通过计算m_u=n_u\oplus H_{\mathrm{2}}(e(A_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))获得正确的查询结果。

证

H_{\mathrm{2}}(e(A_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))=

H_{\mathrm{2}}(e({a_u}^{-\mathrm{1}}\cdot Y_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))=

H_{\mathrm{2}}(e({a_u}^{-\mathrm{1}}\cdot b\cdot P_u\cdot a_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))=H_{\mathrm{2}}(e(b\cdot P_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(b\cdot \mathrm{P}\mathrm{K},S\cdot \mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))=H_{\mathrm{2}}(e(P_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b,e(S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)=H_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)

则

n_u\oplus H_{\mathrm{2}}(e(A_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))=

n_u\oplus H_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)=

m_u\oplus H_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)\oplus

H_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)=m_u

因此，用户可通过计算n_u\oplus H_{\mathrm{2}}(e(A_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))获得查询结果m_u。

定理2 验证性：用户可以验证来自LBS服务器信息的真伪。

证 在用户注册阶段，为了防止LBS服务器发来的信息Reg=｛（PID₁，PKID₁，SKID₁），（PID₂，PKID₂，SKID₂），…，（PID _k，PKID _k，SKID _k ）｝中（PID _u，PKID _u，SKID _u ）被篡改，用户MU先计算\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u=H_{\mathrm{1}}(\mathrm{I}{\mathrm{D}}_u)，再验证等式e(\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,P)=e(\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,\mathrm{S}\mathrm{P}\mathrm{K})是否成立。因为e(\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,P)=e(S\cdot \mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,P)=e(\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,S\cdot P)=e(\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,\mathrm{S}\mathrm{P}\mathrm{K})，可见，在用户注册阶段，MU可以验证来自LBS服务器信息的真伪。

在请求服务阶段，当MU收到来自LBS服务器发来的信息Res=｛Y₀，（Y₁，Y₂，…，Y_k ），（n₁，n₂，…，n_k ）｝后，判断e(V_u,Y_{\mathrm{0}})=e(Y_u,\mathrm{P}\mathrm{K})是否成立。因为e(V_u,Y_{\mathrm{0}})=e(V_u,b\cdot \mathrm{P}\mathrm{K})=e(b\cdot V_u,\mathrm{P}\mathrm{K})=e(Y_u,\mathrm{P}\mathrm{K})。因此，在请求服务阶段，MU可以验证来自LBS服务器信息的真伪。

综上所述，用户可以验证来自LBS服务器信息的真伪。

定理3 匿名性：用户位置服务满足匿名性。

证 假设攻击者A从LBS服务器发送给用户MU的信息res=｛Y₀，（Y₁，Y₂，…，Y_k ），（n₁，n₂，…，n_k ）｝中，获取了k个密文结果｛n₁，n₂，…，n_k ｝，其中，n_u=m_u\oplusH_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)。A企图获得MU的真实查询结果m_u，需要通过m_u=n_u\oplus H_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)=n_u\oplus H_{\mathrm{2}}(e(d_u\cdot \mathrm{P}\mathrm{K}+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)完成计算，这就需要获取u、d_u 、s和b这4个数值。如果A可以获得这4个数值，就能获得MU的真实查询结果，用户失去匿名性保护。反之，A不能获得MU的真实查询结果，用户保持匿名性。下面的任务就转换到A能否获得上述4个数值。A获得的k个密文结果｛n₁，n₂，…，n_k ｝，其中，n_u 是与MU的真实身份和真实位置相关联的，u的值是由用户指定的，A并不知道，u值被猜测出来的概率为1/k。另外，s、d_u 和b是LBS服务器从{Z_q}^{\mathrm{*}}中选择的随机数，对A保密。如果A试图从公开的\mathrm{P}\mathrm{K}=s\cdot P中获得s，信息Res的Y_{\mathrm{0}}=b\cdot \mathrm{P}\mathrm{K}中获得b，LBS服务器公布的基点P_u=d_u\cdot \mathrm{P}\mathrm{K}中获得d_u，就需要攻克ECDL难题，而在现阶段这种计算是不可行的。综上所述，本文方案满足匿名性。

3.2　安全性分析

攻击1 伪装攻击：① 攻击者企图通过获得的信息，伪装成用户MU的身份，获得位置请求服务。② 攻击者企图伪装成LBS服务器，完成用户的注册申请和请求位置服务。

攻击①：攻击者A企图将自己的查询服务信息隐藏在用户MU的查询请求信息Msg=｛（PID₁，C₁，Q₁，V₁），（PID₂，C₂，Q₂，V₂），…，（PID _a，C_a，Q_a，V_a ），…，（PID _k，C_k，Q_k，V_k ）｝中，发送给LBS服务器申请位置服务。LBS服务器反馈加密的查询结果信息Res=｛Y₀，（Y₁，Y₂，…，Y_k ），（n₁，n₂，…，n_a，…，n_k ）｝，A需要通过m_a=n_a\oplus H_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)或m_a=n_a\oplus H_{\mathrm{2}}(e(A_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))=n_a\oplus H_{\mathrm{2}}(e({a_u}^{-\mathrm{1}}\cdot Y_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))获取解密的查询结果。通过3.1节分析可知，A无法获得b和s，因而无法通过m_a=n_a\oplusH_{\mathrm{2}}(e(P_u+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)获得解密的查询结果。同理，A无法获得MU选择的a_u 和私钥SKID_MU，因而无法通过m_a=n_a\oplus H_{\mathrm{2}}(e({a_u}^{-\mathrm{1}}\cdot Y_u,\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}),e(Y_{\mathrm{0}},\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}))获得解密的查询结果。因此，攻击者不能伪装成用户MU的身份，获得位置请求服务。

攻击②：攻击者A企图伪装成LBS服务器，完成用户的注册申请和请求位置服务。在用户注册阶段，A为了伪装成LBS服务器，需要将Reg= ｛（PID₁，PKID₁，SKID₁），（PID₂，PKID₂，SKID₂），…，（PID _k，PKID _k，SKID _k ）｝反馈给注册用户，则需要计算出\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_i=S\cdot \mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_i。由于S=g^s\mathrm{m}\mathrm{o}\mathrm{d}p是保密的，并且A在现阶段很难攻克ECDL难题，便不能从\mathrm{S}\mathrm{P}\mathrm{K}=S\cdot P求出S，继而计算出SKID _i。当无法计算出SKID _i，A可能伪造一对PKID _u 和SKID _u，试图通过e(\mathrm{S}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,P)=e(\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_u,\mathrm{P}\mathrm{K})验证，则需要解决DBDH难题，而在现阶段仍无法攻克DBDH难题。因而，攻击者无法伪装成LBS服务器完成用户注册申请。在请求位置服务阶段，A为了伪装成LBS服务器，需要将Res=｛Y₀，（Y₁，Y₂，…，Y_k ），（n₁，n₂，…，n_k ）｝反馈给请求用户，则需要计算出Y_{\mathrm{0}}=b\cdot \mathrm{P}\mathrm{K},Y_i=b\cdot V_i,n_i=m_i\oplus H_{\mathrm{2}}(e(P_i+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}\mathrm{I}{\mathrm{D}}_{\mathrm{M}\mathrm{U}}{)}^b)，这时，A同样需要面临ECDL难题。当无法计算出Res，A可能会伪造数据，企图通过e(V_u,Y_{\mathrm{0}})=e(Y_u,\mathrm{P}\mathrm{K})验证，则同样需要攻克现阶段无法攻克的DBDH难题。因而，攻击者无法伪装成LBS服务器完成用户请求位置服务。

综上所述，本文方案可以抵抗伪装攻击。

攻击2 重放攻击：假设攻击者截获了已注册用户MU的注册请求信息和请求位置服务信息，重新发送给LBS服务器，企图获得与MU同样的服务。

攻击者A可以获得的信息：①系统的公共参数｛G₁，G₂，H₁，H₂，q，P，e，n，PK｝；②用户MU的注册请求信息ID=｛ID₁，ID₂，…，ID _u，…，ID _k ｝；③LBS服务器公布的基点信息｛P₁，P₂，…，P_n ｝；④MU的查询请求信息Msg=｛（PID₁，C₁，Q₁，V₁），（PID₂，C₂，Q₂，V₂），…，（PID _k，C_k，Q_k，V_k ）｝；⑤LBS服务器反馈的查询结果信息Res=｛Y₀，（Y₁，Y₂，…，Y_k ），（n₁，n₂，…，n_k ）｝。

当A将MU已注册的请求信息ID=｛ID₁，ID₂，…，ID _u，…，ID _k ｝重新发送给LBS服务器申请注册时，LBS服务器会重新选择一次性随机数\mathrm{I}\mathrm{D}{\mathrm{\text{'}}}_{\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{y}}\in{{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}，生成不同的假名\mathrm{P}\mathrm{I}{\mathrm{D}}_i\mathrm{\text{'}}=H_{\mathrm{3}}(\mathrm{I}{\mathrm{D}}_i+\mathrm{I}\mathrm{D}{\mathrm{\text{'}}}_{\mathrm{a}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{y}})。因而，即使A使用雷同的身份信息再次注册，LBS服务器也不会返回相同的假名，即不会获得相同的注册请求结果。

当A将MU已请求的查询信息Msg=｛（PID₁，C₁，Q₁，V₁），（PID₂，C₂，Q₂，V₂），…，（PID _k，C_k，Q_k，V_k ）｝重新发送给LBS服务器申请位置服务时，LBS服务器会重新选择一次性随机数b\mathrm{\text{'}}\in {{\mathrm{\mathbb{Z}}}_q}^{\mathrm{*}}，计算Y_{\mathrm{0}}\mathrm{\text{'}}=b\mathrm{\text{'}}\cdot \mathrm{P}\mathrm{K},Y_i\mathrm{\text{'}}=b\mathrm{\text{'}}\cdot V_i和n_i\mathrm{\text{'}}=m_i\oplus H_{\mathrm{2}}(e(P_i+S\cdot \mathrm{P}\mathrm{K},\mathrm{P}\mathrm{K}{\mathrm{U}}_{\mathrm{M}\mathrm{U}}{)}^{b\mathrm{\text{'}}})，生成不同的服务结果\mathrm{R}\mathrm{e}\mathrm{s}=\{Y_{\mathrm{0}}\mathrm{\text{'}},(Y_{\mathrm{1}}\mathrm{\text{'}},Y_{\mathrm{2}}\mathrm{\text{'}},\cdots ,Y_k\mathrm{\text{'}}),(n_{\mathrm{1}}\mathrm{\text{'}},n_{\mathrm{2}}\mathrm{\text{'}},\cdots ,n_k\mathrm{\text{'}})\}。因而，即使A使用雷同的请求查询信息再次请求服务，LBS服务器也不会返回相同的服务结果，且A也无法解密其中的密文信息(n_{\mathrm{1}}\mathrm{\text{'}},n_{\mathrm{2}}\mathrm{\text{'}},\cdots ,n_k\mathrm{\text{'}})。

综上所述，攻击者不能通过重放已注册的请求信息和请求位置服务信息，获得与已注册用户同样的服务，本文方案可以抵抗重放攻击。

攻击3 共谋攻击：攻击者企图与位置服务器或某些恶意用户共谋，猜测出用户MU的真实身份。

假设攻击者A与位置服务器LBS服务器共谋。由于本文方案在泛化区间时使用了4个随机数，且不同时向前或向后波动，防止了区间对称性猜测。可见，泛化区间的生成存在随机因素，匿名位置的产生没有任何规律。A或LBS服务器也只能从MU发送的请求位置服务信息中猜测MU的真实身份，概率为1/k。因此，本文方案可以抵抗攻击者与位置服务器的合谋攻击。

假设攻击者A与恶意用户共谋。本文方案将用户MU的经纬度坐标位置泛化到一个区间区域内，并进行Geohash编码。如果相同Geohash编码的位置个数等于k，直接组成匿名位置集，这时攻击者猜测出MU真实身份的概率为1/k。如果相同Geohash编码的位置个数小于k，则扩大到相邻的8个矩形区域。扩大区域后，匿名位置的个数一般会大于k。MU剔除自己刚刚查询过的位置，筛选出历史查询概率相同的k-1个位置，再融入自身位置，构成k个匿名位置集。在这个过程中，攻击者A只能获得共谋用户的历史查询概率，并不能获得被攻击用户MU的历史查询概率，攻击者猜测出MU真实身份的概率为1/k。因此，本文方案可以抵抗攻击者与恶意用户的合谋攻击。

4　 仿真分析

基于位置隐私保护的系统模型，从处理数据的时间开销和匿名隐私度两个方面进行仿真分析。仿真实验硬件环境i3-8100T CPU、8 GB RAM，软件环境Windows 10 64bit OS、codeblocks-17.12软件。

4.1　处理数据的时间开销

本文方案采用Geohash编码技术来生成匿名位置集，匿名位置集还可以通过曼哈顿距离^［20］或欧氏距离^［21］的计算来构造。实验位置数据集选用Geolife数据集^［22］，其中，第一条位置数据作为用户的真实位置，然后采用三种不同方法生成匿名位置集。

如图5所示，当数据量增加时，三种方法的时间开销都在增加。其中，欧氏距离方法存在乘法运算，时间开销增长最快；Geohash编码方法只是将二维的位置数据转换成一维的字符串，相比较而言，基本没有计算量，时间开销增长很小。

4.2　匿名隐私度

用户位置匿名保护的程度常用位置熵来度量，熵值越大，隐私保护度就越高，当匿名位置集里的所有位置点查询概率均相等，熵值将达到最大。匿名熵与用户选择的匿名度k值有关，k值越大，用户真实位置的隐藏效果就越好，但会增加系统的通信开销和效率。

仿真实验k值取［10，80］，效果如图6所示。当k值增加时，位置熵会增大，但k值增加到一定数值后，位置熵增长的速度会趋于平缓，说明在一定的匿名区域内，假位置过于密集，混淆能力也趋于饱和，这时再增加假位置的数量，对用户真实位置的保护效果欠佳。在本文方案中，当匿名位置的个数小于k，选用查询概率相同的k-1个位置构成匿名位置集，位置熵达到最大，隐私保护度较高。

5　 结 语

现有的很多k匿名位置隐私保护方案因为检索历史数据库的时间开销较大，位置服务失去了即时的优越性。本文方案通过Geohash编码，将用户的真实位置泛化到一个区间区域，该区域内所有位置的Geohash编码相同，通过反向检索构成匿名位置集，筛选多余位置时兼顾历史查询概率，这样可以避免检索的时间滞后性，给用户提供即时的位置服务。通过性质分析，在双线性映射的相关问题假设前提下，方案满足正确性、验证性和匿名性，可以抵抗伪装攻击、重放攻击和共谋攻击。仿真实验显示，在处理数据的时间开销和匿名隐私度上，本文方案具有更好的优越性。位置数据不是一个离线的静态数据，而是一段持续的动态数据，未来的工作还需要处理运动用户的位置请求匿名服务。

参考文献

[1] JAGWANI P， KAUSHIK S. Privacy in location based services： Protection strategies， attack models and open challenges ［C］// Information Science and Applications 2017. Singapore： Springer， 2017： 12-21. DOI：10.1007/978-981-10-4154-9_2 .

[2] ZHANG L， HE L L， LIU D S， et al. An attribute generalization mix-zone without privacy leakage ［J］. IEEE Access，2019，7（1）：57088-57099. DOI： 10.1109/ACCESS.2019.2898996 .

[3] 张少波，刘琴，王国军. 基于位置混淆的轨迹隐私保护方法［J］. 通信学报，2018，39（7）：81-91. DOI：10.11959/j.issn.1000-436x.2018119 .

[4] ZHANG S B， LIU Q， WANG G J. Trajectory privacy protection method based on location obfuscation ［J］. Journal on Communications， 2018，39（7）：81-91. DOI：10.11959/j.issn.1000-436x.2018119（Ch ）.

[5] 王斌，张磊，张国印. 基于多方安全计算的属性泛化mix-zone［J］. 通信学报，2019，40（4）：83-94. DOI：10.11959/j.issn.1000-436x.2019077 .

[6] WANG B， ZHANG L， ZHANG G Y. Attribute generalization mix-zone based on multiple secure computation ［J］. Journal on Communications， 2019，40（4）：83-94. DOI：10.11959/j.issn.1000-436x.2019077（Ch ）.

[7] 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.25204 73 .

[8] PAULET R， KAOSAR M G， YI X. Privacy-preserving and content-protecting location based queries［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（5）：1200-1210. DOI： 10.1109/TKDE.2013.87 .

[9] RAJASEKAR S S， PALANISAMY C， SARANYA K. Privacy-preserving location-based services for mobile users using directional service fetching algorithm in wireless networks ［J］. Journal of Ambient Intelligence and Humanized Computing， 2021，12（7）： 7007-7017. DOI：10.1007 /s12652-020-02361-9 .

[10] 李维皓，丁晟，孟佳洁，等. 基于位置服务中时空关联的隐私保护方案［J］.通信学报， 2018， 39（5）： 134-142. DOI：10.11959/j.issn.1000-436x.2018084 .

[11] LI W H， DING S， MENG J J， et al. Spatio-temporal aware privacy-preserving scheme in LBS ［J］. Journal on Communications， 2018，39（5）：134-142. DOI：10.11959/j.issn.1000-436x.2018084（Ch ）.

[12] HAYASHIDA S， AMAGATA D， HARA T， et al. Dummy generation based on user-movement estimation for location privacy protection ［J］. IEEE Access，2018，6：22958-22969. DOI：10.1109/ ACCESS.2018.2829898 .

[13] NIU B， LI Q H， ZHU X Y， et al. Achieving k-anonymity in privacy-aware location-based services ［C］//IEEE INFOCOM 2014-IEEE Conference on Computer Communications. New York：IEEE， 2014：754-762. DOI： 10.1109/INFOCOM.2014.6848002 .

[14] 李维皓，曹进，李晖. 基于位置服务隐私自关联的隐私保护方案［J］. 通信学报，2019，40 （5）：57-66. DOI：10.11959/j.issn.1000-436x.2019110 .

[15] LI W H， CAO J， LI H. Privacy self-correlation privacy-preserving scheme in LBS［J］. Journal on Communications，2019，40（5）：57-66. DOI：10.11959/j.issn.1000-436x.2019110（Ch ）.

[16] WANG K， ZHAO W， CUI J J， et al. A k-anonymous clustering algorithm based on the analytic hierarchy process ［J］. Journal of Visual Communication and Image Representation， 2019，59：76-83. DOI：10.1016/j.jvcir.2018.12. 052 .

[17] MEMON I， CHEN L， ARAIN Q A， et al. Pseudonym changing strategy with multiple mix zones for trajectory privacy protection in road networks ［J］. International Journal of Communication Systems，2018，31（1）：e3437. DOI：10.1002 /dac.3437 .

[18] PENG T， LIU Q， WANG G J， et al. Multidimensional privacy preservation in location-based services ［J］. Future Generation Computer Systems，2019，93：312-326. DOI：10.1016/j.future.2018.10.025 .

[19] GRUTESER M， GRUNWALD D. Anonymous usage of location⁃based services through spatial and temporal cloaking ［C］// Proceedings of the 1st International Conference on Mobile Systems， Applications， and Services （MobiSys 2003）. New York： Association for Computing Machinery， 2003：31-42. DOI：10.1145/1066116.1189037 .

[20] 向隆刚，王德浩，龚健雅.大规模轨迹数据的Geohash编码组织及高效范围查询［J］. 武汉大学学报·信息科学版，2017，42（1）：21-27. DOI：10.13203/j.whugis20150175 .

[21] XIANG L G， WANG D H， GONG J Y. Organization and efficient range query of large trajectory data based on Geohash ［J］. Geomatics and Information Science of Wuhan University， 2017，42（1）：21-27. DOI：10.13203/j.whugis 20150175 （Ch ）.

[22] NIEMEYER G. Geohash Tips & Tricks ［EB/OL］. ［2013-03-21］.

[23] BERESFORD A R， STAJANO F. Location privacy in pervasive computing［J］. IEEE Pervasive Computing， 2003， 2（1）： 46-55. DOI：10.1109/MPRV.2003.1186725 .

[24] SHAHID A R， PISSINOU N， IYENGAR S S， et al. Delay-aware privacy-preserving location-based services under spatiotemporal constraints ［J］. International Journal of Communication Systems，2021，34：e4656. DOI：10.1002/dac.4656 .

[25] LI Z H， ZHONG X F， WEI J， et al. The application of Manhattan tangent distance in outdoor fingerprint localization［C］//2018 IEEE Global Communications Conference （GLOBECOM）. New York：IEEE， 2018：1-5. DOI：10.1109/ GLOCOM.2018.8647175 .

[26] DEUTSCH A， HULL R， VYAS A， et al. Policy-aware sender anonymity in location-based services-eScholarship［C］//2010 IEEE 26th International Conference on Data Engineering，2010：133-144. DOI：10.1109/ICDE.2010.5447823 .

[27] Geolife［EB/OL］.［2007-10-08］. DOI: 10.1089/glre.2016.201011 .

基金资助

安徽省高等学校自然科学研究重点项目(KJ2019A0727)

安徽省高等学校质量工程项目(2020kfkc434)

安徽省高等学校质量工程项目(2020xsxxkc377)

安徽省高等学校质量工程项目(2020jyxm1572)

安徽省教育厅教学示范课（1940）

合肥师范学院校级科研项目(2021KJZD15)