基于网格的位置隐私保护方法*

李向东，张少波,2，郭 敏，王国军,4+

1.中南大学 信息科学与工程学院，长沙 410083

2.湖南科技大学 计算机科学与工程学院，湖南 湘潭 411201

3.中南大学 软件学院，长沙 410075

4.广州大学 计算机科学与教育软件学院，广州 510006

基于网格的位置隐私保护方法*

李向东1，张少波1,2，郭 敏3，王国军1,4+

1.中南大学 信息科学与工程学院，长沙 410083

2.湖南科技大学 计算机科学与工程学院，湖南 湘潭 411201

3.中南大学 软件学院，长沙 410075

4.广州大学 计算机科学与教育软件学院，广州 510006

在基于位置的服务（location based service，LBS）中，可信第三方模型是当前位置隐私保护中的主要模型，该模型中匿名器知道用户的具体位置，若它被攻击者攻破，将会造成用户位置信息的泄露。为此，提出一种基于网格的位置隐私保护方法，该方法将可信第三方模型中可信的第三方（trusted third party，TTP）替换为一个半可信的第三方（semi-trusted third party，STTP）作为匹配服务器。该匹配服务器只起匹配和缓存的作用，无法获得用户具体位置，从而能够更好地保护用户的位置隐私。安全分析表明，该方法能有效保护用户的位置隐私；同时与可信第三方模型进行了对比分析，实验结果表明，其性能比可信第三方模型更好。

基于位置的服务；位置隐私保护；网格；半可信第三方

1 引言

目前，移动互联网得到飞速发展，智能移动终端变得相当普及，基于位置的服务（location based service，LBS）[1-2]因此有着令人欣喜的前景。它改变了人们的生活方式，使用户可随时随地获得和其当前位置有关的各种信息或服务，例如紧急救援、路线导航和社交娱乐等。

然而，基于位置的服务都需要用户输入其当前位置信息，有的甚至需要用户实时发送位置信息，如果这些信息保护不好，用户的位置隐私就会被泄露，通过分析就能够推断出用户的很多真实情况。比如，某用户患有一种不便公开的疾病，当其查询某专科医院位置及前往路线时，如果攻击者将其截获，就可推测出该用户或其家人可能患有此种疾病，而这往往是用户不愿意让别人知道的。由此可见，用户位置隐私的保护非常重要。

目前，可信第三方模型[3-4]是位置隐私保护中的主要模型（如图1）。匿名器的主要任务是跟踪用户的具体位置，并将其进行k-匿名处理，之后发送给服务提供商；同时接收服务提供商返回的查询结果，处理后再返回给用户。

可信第三方模型有以下几个缺点：（1）若匿名器被攻击者攻破，将会造成用户位置信息的泄露，甚至会影响整个结构的稳定和安全；（2）若用户数量密度较大时，所选的匿名区域就比较小，用户位置就比较容易确定；（3）当大量移动用户频繁更新位置信息时，匿名区域需要扩大，大幅增加了查询处理的开销；（4）在连续的基于位置的服务中，用户位置在不断变化，匿名器和服务提供商的计算开销和通信开销较大。

针对上述问题，本文提出了一种基于网格的位置隐私保护方法。该方法包括用户、服务提供商和位于二者之间的匹配服务器3个实体。用户使用网格[5-6]划分查询面积，加密查询并产生加密标识符来隐匿具体位置，匹配服务器只起匹配和缓存的作用，服务提供商提供查询服务。匹配服务器和服务提供商均不知道用户具体位置，从而能更好地保护用户的位置隐私。

本文方法具有以下优点：（1）不需要完全可信的第三方服务器，只需要一个半可信第三方（semi-trusted third party，STTP）作为匹配服务器，负责执行简单的匹配操作及一定的缓存操作；（2）确保匹配服务器无法得知当前查询用户的具体位置信息，服务提供商也只能知道用户在查询面积内，但无法推断出用户的具体位置。

Fig.1 Trusted third party model图1 可信第三方模型

2 基于网格的位置隐私保护方法

2.1 查询处理过程及各实体分析

基于网格的位置隐私保护方法主要包括3个实体：用户、匹配服务器和服务提供商（如图2）。

Fig.2 Location privacy protection method based on Grid图2 基于网格的位置隐私保护方法

该方法整个查询处理过程如下：

（1）用户指定提供服务的服务提供商，确定一个大的查询面积，并将其分为大小相同的网格单元。然后，加密包含有查询面积、网格划分及服务提供商信息的查询。用户所在网格单元及其附近网格单元构成一个查询区域，加密该区域中网格单元的标识，产生一组加密标识符。接下来，用户将加密后的查询和加密标识符通过网络发送给匹配服务器。

（2）匹配服务器缓存加密标识符，将加密后的查询通过网络转发给用户指定的服务提供商。

（3）服务提供商从服务器数据库中选择出合适的信息点（point of interest，POI）。对于每个选定的POI，服务提供商找到覆盖该POI的网格单元，对其进行加密，并加密网格单元标识产生加密标识符。加密后的POI和加密标识符一起通过网络返回给匹配服务器。

（4）匹配服务器缓存加密后的POI和加密标识符，将与（1）中用户发送的加密标识符相匹配的POI的子集通过网络返回给用户。

（5）用户接收后进行解密，得到这些POI的具体位置，然后执行一定的过滤操作，从中计算出需要的查询结果。

2.2 使用k近邻查询保护位置隐私

2.2.1 k近邻查询过程分析

基于网格的位置隐私保护方法使用k近邻查询保护用户位置隐私，当中包含6个主要步骤，如图3，其中k=3。

步骤1用户使用网格划分查询面积。

用户指定提供服务的服务提供商，确定一个大的查询面积，假设它是一个正方形区域，由其左下角顶点(xa,ya)到右上角顶点(xb,yb)表示（不规则空间区域通过使用最小边界矩形可模拟为正方形区域）。用户不一定位于查询面积的中心，可在该区域的任何地方。然后把查询面积划分为m×m个大小相同的网格单元，其中m由用户指定（如图3（a），m=6）。每个网格单元用(c,r)表示，c是从左到右的列索引，r是从下到上的行索引，满足0≤c,r＜m。给定网格单元左下角顶点的坐标(xc,yc)，则该网格单元的标识可通过式（1）计算：

步骤2用户产生一个请求。

用户选择一个随机值K，派生出3个不同的值：

其中，KDF(⋅)是一个值推导方程[7]。

对于指定的服务提供商，一个加密的查询如式（3）所示：

其中，SP是用户指定的服务提供商；IBE.Encsp(.)是基于指定服务提供商的加密[8]；POI-type是POI的类型。使用网格划分的查询面积由m、(xa,ya)和(xb,yb)指定。

用户所在网格单元及其附近网格单元构成一个查询区域Sc。对于Sc中的每个网格单元i，其标识(ci,ri)被加密产生加密标识符Ci：

其中，H(⋅)是抵抗冲突的哈希方程[9]；SE.Enckey(⋅)是在key值下的一个对称加密算法（比如AES）。Sc中的所有网格单元的加密标识符Ci构成一个加密标识符集Se。需要注意，用户将确保Se中加密标识符的排列是随机的。

最后，用户产生如下请求，然后通过网络发送给匹配服务器。

Fig.3 Usingk-NN query to protect location privacy图3 使用k近邻查询保护位置隐私

如图3（a），用户位于网格(3,3)，因此通过匹配服务器请求在单元(3,3)和它邻接的网格单元构成的查询区域（图中阴影单元表示）内的POI。

步骤3匹配服务器处理请求。

匹配服务器接收到用户的请求后，缓存加密标识符集Se，将加密后的查询转发给服务提供商。

步骤4服务提供商处理查询。

服务提供商接收后进行解密，得到POI-type、K和由m、(xa,ya)及(xb,yb)确定的查询面积。然后从服务器数据库中，在用户指定的查询面积内，选择与所需的POI-type匹配的np个POI。对于每个选定的POIj，带有一个位置(xj,yj)(1≤j≤np)，服务提供商即可通过式（1）计算出其标识(cj,rj)。

然后，计算如下：

其中，MACkey(⋅)是在值 key 下的消息认证码[10]；Cj是POI对应的加密标识符；lj包含了加密表中POI的具体位置；σj是为了防止匹配服务器的某些攻击（如篡改加密的POI）。

最后，服务提供商以式（11）所示形式将选中的POI集通过网络返回给匹配服务器：

步骤5用户确定搜索区域。

匹配服务器将服务提供商返回的加密POI的加密标识符，与步骤2中用户发送的加密标识符集Se进行匹配，然后将相匹配的加密POI发送给用户。

图3（b）的粗线矩形内是用户最早的查询区域，该区域内包含的POI少于3个（只有p1和p2）。因此，继续请求匹配服务器上与该区域邻近的网格单元（图3（b）中粗线矩形周围的阴影单元），又发现了p3，一共发现了3个POI，即p1、p2和p3，如图3（c）。

用户通过这3个POI确定出搜索区域（图3（c）中的圆形区域），该区域以用户所在位置为圆心，以用户与第3个最近的POI之间的距离为半径。该区域与用户还未请求的8个网格单元相交（即粗线矩形外的8个单元）。用户将对这些网格单元发布一个新的请求。

步骤6用户对结果进行求精。

假设用户收到了μ个匹配的POI。对于每个匹配的POI，如 lj,σj(1≤j≤np)，用户通过EK解密lj，即可访问到POI的具体位置(xj,yj)。最后通过选择k个最近的POI来确定精确的结果。如图3（d），用户找到了k近邻查询的精确结果，包括3个离其最近的POI：p1、p2和p4。

2.2.2 查询结果更新维护

在连续的基于位置的服务中，用户在不断移动，需要查询面积内未被用户请求过的其他网格单元内的POI信息，因此需要对查询结果进行更新维护。

该阶段有以下3个主要步骤。

步骤1用户发送更新维护请求。

用户请求过的网格单元构成缓存区域（图4中浅色阴影网格单元）。搜索区域与缓存区域外的4个网格单元相交，它们构成网格单元集Sc′，其加密标识符集为Se′。用户同样产生一个针对这4个网格单元的请求，并通过网络发送给匹配服务器。

步骤2匹配服务器处理请求。

Fig.4 k-NN query result maintenance图4 k近邻查询查询结果更新维护

匹配服务器已缓存了查询面积内的POI及其加密标识符，因此不需要联系服务提供商去处理结果更新请求。匹配服务器将与用户发送的结果更新维护请求中的加密标识符集Se′相匹配的POI返回给用户。

步骤3用户对结果进行求精。

用户将匹配服务器新返回的POI和缓存区域中的POI，按照与用户距离远近升序排列，距离用户最近的k个POI组成了新的查询结果。如图4（b），用户从匹配服务器获得两个新的POI：p5和p6。距离用户最近的3个POI组成新的查询结果：p1、p2和p5。

2.3 方法安全性分析与证明

2.3.1 服务提供商端安全性分析与证明

本小节将证明服务提供商无法获得用户的具体位置。下面通过挑战游戏进行详细分析。形式上，定义一个挑战者C（即匹配服务器）和一个敌手S（即恶意的服务提供商）。

挑战C准备系统参数，发送给S。S指定POI-type、网格划分查询面积以及两个位置(x0,y0)和(x1,y1)，发送给C。C随机选择一个bit位b∈{0,1}，使用(xb,yb)、网格信息和POI-type产生Msg2，将Msg2作为挑战密文发送给S。

猜测S提交对b的猜测b′∈{0,1}，如果b′=b，则称敌手成功。

定义1如果对于任何服务提供商，它赢得上述挑战游戏的概率都不超过1/2+negl(l)，此处negl(l)是一个可忽略函数，则一种基于网格的位置隐私保护方法实现了服务提供商端的安全。

引理1一种基于网格的位置隐私保护方法实现了服务提供商端的安全。

证明从匹配服务器到服务提供商的信息流Msg2=query。由式（3），query是在指定服务提供商的情况下，对POI-type、K和网格信息的加密，与用户位置无关，因此，S在通过Msg2猜测b的时候，无法获得任何有帮助的信息。

2.3.2 匹配服务器端安全性分析与证明

本小节将证明匹配服务器不能从来自用户的请求或者来自服务提供商的内容中，获得用户的具体位置。下面仍通过挑战游戏进行详细分析。形式上，定义一个挑战者C（用户和所有的服务提供商）和一个敌手Q（恶意的匹配服务器）。

挑战给定系统参数，Q执行多项式次的私有值查询：Q提交指定服务提供商的信息给C，并接收相应的私有值。Q接着指定POI-type、（故意的）服务提供商（其私有值已被查询）、网格信息、查询面积，及查询面积内的两个用户位置(x0,y0)和(x1,y1)，然后发送给C。C随机选择一个bit位b∈{0,1}，使用(xb,yb)和其他由Q指定的信息，产生Ms和Ms，并返回给Q。Q继续执行上述查询（但不请求服务提供商的私有值）。

猜测Q提交对b的猜测b′∈{0,1}，如果b′=b，则称敌手成功。

定义2如果对于所有的概率多项式时间，Q赢得上述挑战游戏的概率无限接近于1/2，则基于网格的位置隐私保护方法实现了匹配服务器端的安全。

引理2基于网格的位置隐私保护方法实现了匹配服务器端的安全。

证明通过一系列游戏G0,G1,…,Gi证明引理2。当Q赢得游戏Gi后，用Xi来表示。

G0：同上述挑战。注意：存在两个范围，分别以(x0,y0)和(x1,y1)为圆心，R0和R1为半径，这两个范围包含相同数目的POI。由于范围是用户选择的，从而敌手是未知的。

G1：改变(HK,EK,MK)的产生。从空间 κH×κE×κM中随机选择这3个值。由KDF保证安全，得出|Pr[X1]-Pr[X0]|是可忽略的[8,11]。

G2：改变 Ms中lj的产生。代替对用户具体位置的加密，lj加密一个在值EK下随机选择的位置（与(x0,y0)和(x1,y1)不同）。由SE保证安全，得出|Pr[X2]- Pr[X1]|是可忽略的[12-13]。

G3：改变 Ms和Ms中所有的Ci。约束：在相同网格单元内的POI与网格单元共享相同的hi。由SE保证安全，得出|Pr[X3]- Pr[X2]|是可忽略的[12-13]。

G4：改变用户端消息的请求，成为长度相同的随机数组的加密。由IBE的安全，得出|Pr[X4]-Pr[X3]|是可忽略的[8]。在G4中，Ms和Ms与C选择的b是独立的，因此Q能够成功地提交正确猜测的可能性至多是1 2，由此得出是可忽略的。

2.3.3 查询结果完整性分析与证明

本小节将证明匹配服务器不能修改返回给用户的任何一个POI的信息，也无法新增虚假POI。下面再次通过挑战游戏进行详细分析。形式上，定义一个挑战者C（用户和所有的服务提供商）和一个敌手Q（恶意的匹配服务器）。

挑战给定系统参数，Q执行多项式次的以下查询。私有值查询：Q提交指定的服务提供商信息，然后被返回相应的私有值。服务查询：Q产生Msg1并发送给服务提供商，接着接收到Msg3。Q提交POI-type、（故意的）服务提供商（其私有值还未被查询）、网格信息、查询面积，以及用户的位置(x,y)。C产生Ms和Ms，发送给Q。Q产生Ms。

猜测如果Ms⊄Msg4，但用户接受了Ms，则称敌手成功。

定义3如果在概率多项式时间内，Q无法以不可忽略的概率赢得上述挑战游戏，则基于网格的位置隐私保护方法实现了查询结果的完整性。

引理3基于网格的位置隐私保护方法实现了查询结果的完整性。

证明通过一系列游戏G0,G1,…,Gi证明引理3。当敌手Q赢得游戏Gi后，用Xi来表示。

G0：同引理2。

G1：改变 Ms和Ms的产生。代替输入一个随机的K然后由KDF输出，MK从κM中随机选择。由KDF保证安全，得出|Pr[X1]-Pr[X0]|是可忽略的[8,11]。

通过Q去构造一个算法τ，该算法破坏了MAC的强不可伪造性[8,11]。给出预言机OM，τ产生了包含IBE值的系统参数。然后借助Q输入系统参数，开始下面的查询。私有值查询：给出服务提供商，τ使用IBE产生服务提供商的私有值，返回给Q。服务查询：给出Msg1=SP,request,Se，τ使用服务提供商的私有值（可以从IBE计算出来）解密查询，然后获得POI-type、K、m、(xa,ya)和(xb,yb)。根据服务提供商规定的策略，产生Msg3并返回给Q。

当Q接收到Msg3后，输出（故意的）服务提供商、POI-type、网格信息、查询面积和用户的位置(x,y)。τ然后使用Q给出的信息产生Ms和Ms，如下：

对于所有的POI，τ使用嵌入在UMsg*中的K推导出的值来计算Ci和li。然后发送(Ci,li)给预言机OM，被返回 σi=MACMK(Ci,li)。

3 实验与分析

3.1 模拟实验环境

（1）软硬件环境

硬件环境：Intel®CoreTMi5-4590 CPU处理器，主频3.30 GHz，内存4.00 GB RAM。

软件环境：64位Windows 7操作系统，编译环境Java 1.7，编程语言采用Java语言。

（2）实验数据

本实验使用Thomas Brinkhoff轨迹生成器[14]生成模拟移动对象数据，模拟生成20 000个移动用户在某市城区1 606km2的真实交通网中的运动轨迹作为数据集。使用了10 000个POI，k近邻查询中默认的POI请求数为k=10，可信第三方模型的k-匿名度为200。

使用OpenSSL（http://www.openssl.org）、GMP（http://www.gmplib.org）和PBC（http://crypto.stan ford.edu/pbc/）进行基于身份的加密。

3.2 实验结果分析

3.2.1 POI数目增加时两种方法性能对比分析

图5显示了随着服务提供商数据库中POI的数目从10增加到100 000，其他参数不变，基于网格的位置隐私保护方法（STTP）和可信第三方模型（TTP）的性能对比。

（1）计算开销分析

基于网格的位置隐私保护方法在各种情况下，其计算开销均小于可信第三方模型的计算开销，前者的性能好于后者。

基于网格划分的隐私保护方法中，随着POI数目的增多，计算开销也在增大。因为服务提供商在接收到用户请求并解密后，得到查询面积，然后在该查询面积内，从数据库中选择相应的POI。查询面积内的POI数目增多，因此计算开销会增大。

可信第三方模型中，当POI的数目在1 000以上时，随着POI数目的增加，它必须扩大匿名区域的面积，因此大幅增加了计算开销。

（2）通信开销分析

当POI数目较小（10和100）时，可信第三方模型的通信开销比基于网格的位置隐私保护方法稍大，因为其匿名区域非常小，POI数目也少。当POI数目在1 000以上时，其通信开销增长得更快，也比基于网格的位置隐私保护方法的通信开销更大。

3.2.2 移动用户数增加时两种方法性能对比分析

图6显示了随着移动用户数从10 000增加到50 000，其他参数不变，两种方法的性能对比。

（1）计算开销分析

Fig.5 Performance comparison of two schemes when the number of POIs is increased图5 POI数目增加时两种方法性能对比

Fig.6 Performance comparison of two schemes when the number of mobile users is increased图6 移动用户数增加时两种方法性能对比

基于网格的位置隐私保护方法的计算开销保持不变，始终在1 ms以下，因为它与移动用户数相独立，只与查询用户指定的查询面积有关。

可信第三方模型的计算开销比基于网格的位置隐私保护方法的高10～20倍。随着移动用户数的递增，可信第三方模型的匿名区域就越小，计算开销在逐渐减少。

（2）通信开销分析

基于网格的位置隐私保护方法的通信开销保持不变，且远远低于可信第三方模型。

3.2.3 k-匿名度增加时两种方法性能对比分析

图7显示了k-匿名度增加时两种方法的性能对比。基于网格的位置隐私保护方法通过加密标识符来保护用户位置隐私，其性能不受k-匿名度变化的影响，因此计算开销和通信开销保持不变。

当k增大时，可信第三方模型的计算开销增长得很快，因为可信第三方模型必须产生更大的匿名区域来满足用户位置隐私保护要求。其匿名区域的扩大，同样导致返回给用户的POI集更大，通信开销因此增长很快。

3.2.4 用户所需POI数增加时的性能分析

图8显示了用户所需POI数（即k-近邻查询中的k值）从5增加到500，其他参数不变，基于网格划分的隐私保护方法（STTP）的性能分析。

（1）计算开销分析

Fig.7 Performance comparison of two schemes whenk-anonymity level is increased图7 k-匿名度增加时两种方法性能对比

Fig.8 Performance analysis of STTP when the number of POIs required is increased图8 用户所需POI数增加时STTP的性能分析

随着用户所需POI数的增多，基于网格划分的隐私保护方法的计算开销也在增加。其增加只影响了用户和匹配服务器，因为随着用户所需POI数的增多，用户和匹配服务器上的计算开销就更大。由于用户所需POI数的增多，没有改变查询面积的大小，而服务提供商的负载只与查询面积的大小有关，从而服务提供商的计算开销保持不变。

（2）通信开销分析

随着用户所需POI数的增多，通信开销也增加了。然而，只增加了用户端的通信开销，因为用户请求了近邻处更多的POI。

4 结束语

针对可信第三方模型中匿名器若被攻击者攻破，将会造成用户位置信息泄露的问题，本文提出了一种基于网格的位置隐私保护方法，它能够有效地保护用户的位置隐私，且性能明显比可信第三方模型更好。

本文只分析了基于网格的位置隐私保护方法如何使用k近邻查询保护用户的位置隐私，该方法在其他空间查询下的情况，如范围查询、反近邻查询[15]和密度查询[16]等，是下一步研究的内容。

[1]Krishnan RB,Prasad N H,Gokul U,et al.Privacy preserving location based services[J].International Journal of Engineering Science and Computing,2016,6(3):2710-2714.

[2]Liutkauskas V,Matulis D,PlėštysR.Location based services[J].Elektronika ir Elektrotechnika,2004,52(3):35-40.

[3]Song D,Sim J,Park K,et al.Aprivacy-preserving continuous location monitoring system for location-based services[J].International Journal of Distributed Sensor Networks,2015:14.

[4]Relish M,Young P,Vogel V,et al.Trusted third party for medication adherence[J].Circulation:Cardiovascular Quality and Outcomes,2016,9(S2):A266.

[5]Pooranian Z,Shojafar M,Abawajy J H,et al.An efficient meta-heuristic algorithm for grid computing[J].Journal of Combinatorial Optimization,2015,30(3):413-434.

[6]Carpenter F,Manson D,Jeffery K,et al.Grid cells form a global representation of connected environments[J].Current Biology,2015,25(9):1176-1182.

[7]IEEE.Std 1363TM-2000 Standard specifications for public-key cryptography[S].New York,2000.

[8]Susilo W,Guo Fuchun,Mu Yi.Efficient dynamic threshold identity-based encryption with constant-size ciphertext[J].Theoretical Computer Science,2016,609:49-59.

[9]Ye Junwei.Analysis of hash table conflict processing method[J].Science&Technology Vision,2014(6):230.

[10]Smart N P.Hash functions,message authentication codes and key derivation functions[M]//Cryptography Made Simple.Switzerland:Springer International Publishing,2016:271-294.

[11]Yau S S,An H G.Anonymous service usage and payment in service-based systems[C]//Proceedings of the 13th International Conference on High Performance Computing Communication,Banff,Canada,Sep 2-4,2011.Washington:IEEE Computer Society,2011:714-720.

[12]Gao Shang,Krogstie J,Thingstad T,et al.Amobile service using anonymous location-based data:finding reading rooms[J].The International Journal of Information and Learning Technology,2015,32(1):32-44.

[13]Jager T.Verifiable random functions from weaker assumptions[C]//LNCS 9015:Proceedings of the 12th Theory of Cryptography Conference,Warsaw,Poland,Mar 23-25,2015.Berlin,Heidelberg:Springer,2015:121-143.

[14]Panagiotakis C,Pelekis N,Kopanakis I.Segmentation and sampling of moving object trajectories based on representativeness[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(7):1328-1343.

[15]HidayatA,Cheema MA,Taniar D.Relaxed reverse nearest neighbors queries[C]//LNCS 9239:Proceedings of the 14th International Symposium on Spatial and Temporal Databases,Hong Kong,China,Aug 26-28,2015.Switzerland:Springer International Publishing,2015:61-79.

[16]Heendaliya L,Wisely M,Lin Dan,et al.Influence-aware predictive density queries under road-network constraints[C]//LNCS 9239:Proceedings of the 14th International Symposium on Spatial and Temporal Databases,Hong Kong,China,Aug 26-28,2015.Switzerland:Springer International Publishing,2015:80-97.

附中文参考文献：

[9]叶军伟.哈希表冲突处理方法浅析[J].科技视界,2014(6):230.

Location Privacy Protection Method Based on Grid*

LI Xiangdong1,ZHANG Shaobo1,2,GUO Min3,WANG Guojun1,4+
1.School of Information Science and Engineering,Central South University,Changsha 410083,China
2.School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China
3.School of Software,Central South University,Changsha 410075,China
4.College of Computer Science and Educational Software,Guangzhou University,Guangzhou 510006,China
+Corresponding author:E-mail:csgjwang@gmail.com

LI Xiangdong,ZHANG Shaobo,GUO Min,et al.Location privacy protection method based on grid.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1258-1268.

In the location based service(LBS),trusted third party model is the main model of current location privacy protection.The anonymous server in this model knows the user's location,if it is attacked,which will cause the leakage of the user's location information.Therefore,this paper puts forward a location privacy protection method based on grid.The method replaces the trusted third party(TTP)as a semi-trusted third party(STTP),which is a matching server.The matching server only matches and caches,and cannot know the user's location,so as to protect user's location privacy better.Security analysis shows that this method can effectively protect the user's location privacy.At the same time,this paper compares this method with trusted third party model.The experimental results show that the performance of this method is better than trusted third party model.

un was born in 1970.He

the Ph.D.degree in computer science from Central South University in 2002.Now he is a professor and Ph.D.supervisor at Guangzhou University and Central South University.His research interests include system security,privacy protection,trusted computing and big data security. 王国军（1970—），男，湖南长沙人，2002年于中南大学获得博士学位，现为广州大学和中南大学教授、博士生导师，主要研究领域为系统安全，隐私保护，可信计算，大数据安全。

LI Xiangdong was born in 1992.He is an M.S.candidate at Central South University.His research interests include information security and privacy protection.李向东（1992—），男，山西吕梁人，中南大学硕士研究生，主要研究领域为信息安全，隐私保护。

ZHANG Shaobo was born in 1979.He is a Ph.D.candidate at Central South University.His research interests include privacy protection and cloud computing security.张少波（1979—），男，湖南邵阳人，中南大学博士研究生，主要研究领域为隐私保护，云计算安全。

GUO Min was born in 1992.She is an M.S.candidate at Central South University.Her research interests include software engineering,trusted computing and privacy protection.郭敏（1992—），女，山东济南人，中南大学硕士研究生，主要研究领域为软件工程，可信计算，隐私保护。

A

：TP309

*The National Natural Science Foundation of China under Grant Nos.61472451,61272151,61402161,61502163(国家自然科学基金).Received 2016-07,Accepted 2016-10.

CNKI网络优先出版:2016-10-18,http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.010.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1258-11

10.3778/j.issn.1673-9418.1607017

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

Key words:location-based service;location privacy protection;grid;semi-trusted third party