隐私保护的安全位置服务范围查询外包方法

摘要

本发明公开了一种隐私保护的安全位置服务范围查询外包方法，包括：步骤1，位置服务提供商利用Hilbert曲线和Merkle哈希树对POI数据进行预处理，获得POI数据密文集和Merkle哈希树树根的签名，并发送给云服务提供商；步骤2，位置服务提供商对用户位置信息进行预处理，获得用户位置信息的Hilbert值范围

说明书

技术领域

本发明属于基于位置服务技术领域，特别是涉及一种隐私保护的安全位置服务范围查询外包方法。

背景技术

随着定位技术的日益成熟以及移动互联网的快速普及，基于位置服务(Location-Based Services，LBS)已成为覆盖了人们生活的方方面面，正在改变人们的生活方式和习惯。典型的LBS特别是移动环境下的LBS是指用户使用移动设备内嵌的全球定位系统(GPS)获取当前位置信息，然后根据其位置信息向LBSP查询附近自己感兴趣的服务，例如查询附近的医院、宾馆、餐厅、加油站等信息。业界已经涌现了一大批LBS的应用，如Foursquare、Facebook、美团、猫眼电影、百度糯米、大众点评等。而瑞典市场研究公司Berg Insight预测全球LBS市场规模将从2014年的103亿欧元，以22.5％的复合年增长率(CAGR)，增长至2020年的348亿欧元。可以预见在不久的将来，LBS必将取得更大范围和更深层次的应用。

在众多的基于位置服务的查询中，基于位置的范围查询寻求位置值在特定范围中的兴趣点(Point Of Interest，POI)集合。具体地，在LBS应用环境中，一个兴趣点POI常常用其位置作为一个空间属性，并使用其它诸多数值属性，如一个餐馆的食品质量、价格、服务、卫生条件。我们说一个POI满足范围查询条件在于，如果一个POI具有某个数值属性，且空间属性在当前查询用户查询区间内。

随着LBS应用的快速发展，特别是近年来移动互联网的迅速普及，LBS数据和服务规模也日益增大，使得LBS服务在计算以及存储上需求急剧增长，这种增长对位置服务提供商(Location-Based Service Provider，LBSP)有限的运营资源构成了巨大的挑战，幸运地是，云计算技术的兴起为应对这一挑战提供了可能。云平台因其具有强大的存储以及高效的计算能力一直备受业界的推崇，通过将LBSP的LBS数据和服务外包到资源强大的CSP，让CSP为用户提供永远在线服务，不但可以减少数据的管理成本，还可以为用户提供更高效的服务，并有着极大的部署弹性和扩展性。LBS的这种外包模式也逐渐成为了LBS应用中主流的服务模式。

虽然LBS外包模式减少了LBSP的运营成本并能为用户提供更高效的LBS。但是，由于CSP不可信，LBS外包应用也面临着诸多安全风险。这当中有两个典型问题，首先是LBSP外包出去的POI数据的安全问题，由于POI数据是LBSP花费大量资源获取的私有资源，是其维持运营的资本，如果泄露给不怀好意的CSP，将损害LBSP的利益。此外，由于POI的位置属性和用户请求位置相关，将POI空间属性明文外包给CSP将会在用户查询时候泄露用户位置隐私；其次是查询结果的真实性问题，由于在LBS外包应用中，用户的请求是由CSP来响应的，CSP可能出于其自身的利益，纂改用户的查询结果。

由于LBS服务的功能核心是满足用户的查询需求，因此前一个问题实质是如何在不告知CSP LBS服务原始数据情况下，满足用户在CSP上的隐私地开展查询需求，其对应的研究问题是位置隐私保护的云端位置密文检索，并在一些现有工作中得到了解决；而后一个问题的实质是如何在让用户从CSP返回的验证信息中检验查询结果的完整性。对这两个问题单独的，这一问题同样也在一些现有工作中得到了解决。然而，当同时考虑两方面问题时，现有工作都不能同时解决问题，要么效率较低。

发明内容

本发明的目的是提供一种隐私保护的安全位置服务范围查询外包方法，本发明可在不告知CSP LBS原始数据情况下，使得用户能够从CSP处获取正确的查询服务数据，同时保障LBSP的数据安全和用户的查询结果完整性。

为达到上述目的，本发明提供的隐私保护的安全位置服务范围查询外包方法，包括步骤：

隐私保护的安全位置服务范围查询外包方法，包括步骤：

步骤1，位置服务提供商对POI数据进行预处理；

本步骤进一步包括子步骤：

1.1根据POI数据集获得整个空间区域，并进一步获得整体空间区域的最小外接矩形区域；

1.2将该最小外接矩形区域划分为4个子矩形区域，该4个子矩形区域记为第1层的子矩形区域；按照预设的构造规则，用三条线段将该4个子矩形区域的中心点顺次连接，获得第1层的子型曲线；所述的构造规则包括Hilbert曲线的起点、方向、缩放因子和阶数，起点选择该4个子矩形区域的中心点之一，方向为顺时针方向或逆时针方向，起点和方向随机设置，缩放因子和阶数根据实际安全需要定制，缩放因子和阶数越大安全性越强；

1.3逐层构造子型曲线，获得Hilbert曲线，具体为：

1.3a对第m层的各子矩形区域分别进行如下操作，其中，m的初始值为1：

将第m层的子矩形区域划分为第(m+1)层的4个子矩形区域，按照预设的构造规则，用三条线段将该第(m+1)层的4个子矩形区域的中心点顺次连接，获得该第m层的子矩形区域的子型曲线；

1.3b沿着第m层的子型曲线的走向，连接第m层的各子矩形区域的子型曲线，得第(m+1)层的子型曲线；

1.3c令m＝m+1，重复执行子步骤1.3a～1.3c，直至获得第M层的子型曲线，第M层的子型曲线即最终的Hilbert曲线；M为预设的层数，根据经验取值；

1.4沿着Hilbert曲线对Hilbert曲线穿过的最小子矩形区域顺序编码，该编码即Hilbert值；

1.5根据POI数据集中各POI对象的位置获得各POI对象的Hilbert值，即将各POI对象位置所落入的最小子矩形区域的编码作为该POI对象的Hilbert值；

1.6按照Hilbert值从大到小对POI数据密文C_i’进行排序，得到排序后的POI数据密文集其中，n为POI数据集中POI对象的总数，C_i’包含第i个POI对象的Hilbert值及密文，该密文即使用对称加密算法对第i个POI对象的位置信息及数据内容进行加密后生成的密文；

1.7对排序后的POI数据密文集构造Merkle哈希树，具体为：

1.7a判断n是否为2的幂数，若是，执行子步骤1.7b；否则，执行子步骤1.7c；

1.7b构造深度为d的二叉树，d和n存在数学关系n＝2^d；二叉树中，每个叶子节点对应一个POI数据密文C_i’，且按Hilbert值从小到大的顺序将各POI数据密文C_i’顺次赋给各叶子节点；叶子节点的哈希值通过对POI数据密文C_i’进行哈希运算获得，每一个非叶子节点的哈希值为它的两个直接子节点的哈希值所串接；

1.7c构造深度为d'的二叉树，d'和n'存在数学关系n'＝2^d'，n'为所有大于n的2的幂数中的最小值；二叉树中，前n个叶子节点分别对应一个POI数据密文C_i’，且按Hilbert值从小到大的顺序将各POI数据密文C_i’顺次赋给前n个叶子节点；其他叶子节点为冗余叶子节点；每一个非叶子节点的哈希值为它的两个直接子节点的哈希值所串接；

1.7d使用C_i’和T_i计算树根的哈希值，将树根哈希值进行签名，T_i为所有被用来验证叶子节点C_i’的最小中间节点集合；

1.8将POI数据密文集和签名发送给云服务提供商；

步骤2，位置服务提供商对用户位置信息进行预处理；

本步骤具体为：

根据用户位置信息确定用户所需要查询的区域范围Q，区域范围Q内所有最小子矩形区域的编码构成Hilbert值范围Q'，将Hilbert值范围Q'发送给云服务提供商；

步骤3，云服务提供商将Hilbert值范围Q'与POI数据密文集中各POI数据密文的Hilbert值一一比对，将与Hilbert值范围Q'中所包含Hilbert值相同的POI数据密文以及用来恢复出签名的最小中间节点集合、签名返还给用户；

步骤4，用户验证返回的POI数据密文的Hilbert值与Hilbert值范围Q'中的Hilbert值在数量和数值上是否一致，若不一致，抛弃本次返回的数据；若一致，采用返回的POI数据密文和最小中间节点集合恢复出树根的签名，并验证与位置服务提供商的签名是否一致，若一致，则对本次返回的POI数据密文进行解密，否则，抛弃本次返回的数据。

子步骤1.2中，将该最小外接矩形区域划分为4个子矩形区域，具体为：

采用过该最小外接矩形区域中心点的两条相互垂直的直线，将该最小外接矩形区域划分为4个子矩形区域。

和现有技术相比，本发明具有如下优点和有益效果：

在保障数据隐私性和查询结果完整性的同时，还可减小计算和通信开销，从而提高效率。

附图说明

图1为本发明系统模型结构示意图；

图2为实施例中Hilbert曲线的构造示意图；

图3为实施例中构建的Merkle哈希树示意图；

图4为根据用户位置信息确定所需要查询的区域范围的示意图；

图5为实施例所采用的6个POI数据集的分布示意图；

图6为本发明方法和现有方法在PC端的计算开销对比图；

图7为本发明方法和现有方法在手机端的计算开销对比图；

图8为本发明方法和现有方法的通信开销对比图。

具体实施方式

下面将先给出本发明所涉及模型和所要解决问题的定义。

一、系统模型

考虑一个拥有兴趣点POI数据集并向移动用户提供位置服务的位置服务提供商LBSP。为了减少它的运行和存储开销，位置服务提供商LBSP将他的POI数据集和基于位置的查询服务外包给第三方云服务提供商CSP，然后由CSP向移动用户提供基于位置的查询服务，系统模型见图1。

二、安全模型

CSP是诚实而好奇的(Honest-But-Curious，HBC)，它会严格按照指令执行系统中的操作，但会从其所接触的数据，最大化窥探用户和LBSP的私密信息，本发明中CSP只知道LBSP外包的密文数据以及根据索引构建算法构建的索引，属于已知密文模型。

三、问题描述

本发明要解决的问题包括外包POI数据的安全及与其关联的用户位置隐私，和用户查询结果完整性验证两方面。为了保证外包POI的数据安全，LBSP需要在预先对POI数据进行机密性和完整性处理，但处理后需保证CSP能够有效检索POI，考虑到在LBS中，用户是根据POI的位置进行范围查询的，而位置信息关乎用户的位置隐私，不能暴露给CSP，需要在进行POI数据外包时进行保护POI的位置；然后，CSP在给用户返还POI查询服务结果时出于自身的利益，可能会篡改用户的查询结果，LBSP如何在外包处理时，以防止CSP篡改用户的查询结果。

本发明通过基于希尔伯特曲线(Hilbert曲线)和Merkle哈希树来解决上述所提问题，下面将对本发明方法的具体实施过程进行详细说明。

1、外包POI数据的预处理

为保证POI数据在CSP上的安全，LBSP须对原始POI数据进行预处理。预处理的目的是在保护POI数据的位置信息同时，可以使CSP对POI的范围检索以便为用户提供服务。

POI对象DO_i是空间数据对象，具有二维位置loc(x_i,y_i)，DO_i表示POI数据集中第i个POI对象，x_i是DO_i的横坐标，y_i是DO_i的纵坐标。由于在LBS中，位置对用户来说是敏感，不能被CSP获取，因此不能将POI的位置信息直接外包给CSP，而需要对其进行转换，并且为了保证CSP能对位置信息经过转换后的POI进行查询，必须让在空间相邻的POI经过转换后依然具有邻近性。

Hilbert曲线具备上述特性，故本发明采用Hilbert曲线对外包POI位置信息进行加密处理，下面将结合小示例说明Hilbert曲线是怎么形成并对空间区域进行隐私编码的。

首先，根据POI数据集获得整体空间区域，并进一步获得整体空间区域的最小外接矩形区域。

然后，将该最小外接矩形区域划分为4个子矩形区域，将该4个子矩形区域记为第1层的子矩形区域；按照预设的构造规则，用三条线段将该4个子矩形区域的中心点顺次连接，获得第1层的子型曲线，见图2(a)。所述的构造规则包括Hilbert曲线的起点、方向、缩放因子和阶数，起点选择该4个子矩形区域的中心点之一，方向可以为顺时针方向或逆时针方向。

4个子矩形区域的划分具体为：

采用过该最小外接矩形区域中心点的两条相互垂直的直线，将该最小外接矩形区域划分为4个子矩形区域。

接着，逐层构造子型曲线，获得Hilbert曲线，可参见图2(b)和图2(c)。

本步骤具体为：

(a)对第m层的各子矩形区域分别进行如下操作，其中，m的初始值取1：

将第m层的子矩形区域划分为第(m+1)层的4个子矩形区域，按照预设的构造规则，用三条线段将该第(m+1)层的4个子矩形区域的中心点顺次连接，获得该第m层的子矩形区域的子型曲线；

(b)沿着第m层的子型曲线的走向，连接第m层的各子矩形区域的子型曲线，得第(m+1)层的子型曲线；

(c)令m＝m+1，重复执行子步骤(a)～(b)，直至获得第M层的子型曲线，第M层的子型曲线即最终的Hilbert曲线；M为预设的层数，根据经验取值。

最后，沿着Hilbert曲线对Hilbert曲线穿过的最小子矩形区域顺序编码，该编码即Hilbert值，这样就实现了将二维空间转化为一维值。

为便于理解，下面将对Hilbert曲线的数学含义进行描述。

设为二维空间下的N阶Hilbert曲线，其中N≥1，见式(1)：

H＝f(x,y)(1)

其中，H表示位置loc(x,y)对应的Hilbert值，H∈[0,2^2N-1]；f表示一单向函数，该函数用来表示loc(x,y)和Hilbert值间的映射关系，x和y分别为位置loc(x,y)的横坐标和纵坐标。

实现了将二维整型空间[0,2^2N-1]²转换到一维整数集[0,2^2N-1]，单向函数f与Hilbert曲线的参数(S₀,θ,N,Γ)相关，S₀表示Hilbert曲线的起始点位置，θ表示Hilbert曲线的方向，N表示Hilbert曲线的阶数，Γ表示Hilbert曲线的缩放因子。这些参数都会影响函数f的计算结果即Hilbert值，故这些参数一起组成了Hilbert曲线加密的密钥HSK，HSK＝(S₀,θ,N,Γ)。CSP或攻击者在不知道解密密钥的情况下，不可能由Hilbert值反推出其所代表的位置信息。LBSP选择合适的Hilbert曲线参数计算外包POI的Hilbert值，Hilbert曲线参数根据实际安全需要定制，N和Γ越大安全性越强，θ随机。

将POI数据记为C_j＝<H_j，Enc_ek(DO_Hj¹||...||DO_Hj^k)>，其中，C_j表示Hilbert值为H_j的所有POI数据；H_j表示第j个Hilbert值；一个Hilbert值可能对应多个POI对象，将Hilbert值为H_j的POI对象记为DO_Hj，DO_Hj包含POI对象的位置信息及数据内容；将这多个POI对象DO_Hj从1到k进行编号，即DO_Hj¹、…DO_Hj^k，分别包含Hilbert值为H_j的第1、…k个POI对象的位置信息和数据内容；Enc_ek(DO_Hj¹||...||DO_Hj^k)表示对Hilbert值为H_j的POI对象使用对称加密算法(如AES算法)进行加密后生成的密文，表示字符拼接。

为构建Merkle哈希树，LBSP按照Hilbert值从大到小对POI数据密文C_i’进行排序，得到排序后的POI数据密文集C_i’为使用对称加密算法对第i个POI对象DO_i的位置信息及数据内容进行加密后生成的密文；i表示POI对象编号，将POI对象编号和Hilbert值编号的关系记为i＝H_IDj，表示编号为i的POI对象DO_i，其Hilbert值编号为j；n为POI数据集中POI对象的总数。然后，将POI数据密文集构造成一棵Merkle哈希树，使得用户可以高效地验证查询结果完整性。具体地：

假设对于某个正整数d，POI对象总数n满足n＝2^d，位置服务提供商LBSP构造深度为d的二叉树，在这个二叉树当中，每个叶子节点对应着一个POI数据密文C_i，且每一个非叶子节点的哈希值为它的两个直接子节点的哈希值所串接。本发明同时用一个辅助集合T_i作为和叶子节点C_i一起计算Merkle哈希树树根的非叶子节点集合，定义T_i为所有被用来验证叶子节点C_i的最小中间节点集合。图3给出了一个n＝6的简单的例子，由于6不是2的任何幂数，则添加冗余叶子节点，使得叶子节点总数为8。该图中，C表示POI数据密文，按照Hilbert值从小到大排列POI数据密文；h表示哈希值，h_i表示对C_i进行哈希运算所得的哈希值，h_0-1表示对h₀和h₁拼接后的哈希值，h_2-3表示对h₂和h₃拼接后的哈希值，h_4-5表示对h₄和h₅拼接后的哈希值，h_6-7表示对h₆和h₇拼接后的哈希值；h_0-3表示对下级h_0-1和h_2-3拼接后的哈希值，h_4-7表示对下级h_4-5和h_6-7拼接后的哈希值，h_0-7表示对下级h_0-3和h_4-7拼接后的哈希值。在这张图中，有返回的POI数据密文C₃和辅助集合T₃＝{h₂,h_0-1,h_4-7}，树根的哈希值root可以使用公式(2)计算：

root＝H(H(h_0-1||H(h₂||H(C₃)))||h_4-7)(2)

式(2)中，||表示字符拼接；H(·)表示哈希运算。

如果n不是2的任何幂数，构造Merkle哈希树时，需要添加冗余叶子节点，使得叶子节点总数为2的幂数。

位置服务提供商LBSP将树根的哈希值进行签名{H(root)}_K-1，其中{·}_K-1表示使用下标所述的私钥K-1计算的签名，私钥K-1在用户注册阶段获得。

最终，LBSP将POI数据密文集和签名发给CSP，CSP使用POI数据密文集计算所有用于构造Merkle哈希树的中间值。

2、范围查询请求

假定用户在位置loc(x,y)向CSP发出位置服务查询请求，则需要对用户的位置信息进行预处理。首先，根据用户位置信息确定其所需要查询的区域范围Q＝[loc_ld,loc_ru]，见图4。loc_ld和loc_ru为所需要查询的区域范围Q(后文简记为“查询范围Q”)的两个边界位置，在查询范围内的任一位置loc_p都满足loc_ld.x≤loc_p.x≤loc_ru.x和loc_ld.y≤loc_p.y≤loc_ru.y，loc_ld.x和loc_ld.y表示边界位置loc_ld的横坐标和纵坐标，loc_ru.x和loc_ru.y表示边界位置loc_ru的横坐标和纵坐标，loc_p.x和loc_p.y表示任一位置loc_p的横坐标和纵坐标。确定查询范围Q后，利用Hilbert曲线转换密钥HSK将二维的范围查询Q转换为一维的Hilbert值查询Q'。见图4，本实施例中，范围查询Q经转换后的Hilbert值查询为8、11、12、13，即Q'＝{8,11,12,13}。最后，将Q'放到查询请求Query中代替其中的loc信息。

3、查询处理

CSP将查询范围Q对应的Hilbert值查询Q'与LBSP外包的POI数据密文集中各POI数据密文的Hilbert值进行一一对比，将所有与Q'中所包含Hilbert值相同的POI数据密文返还给用户。此外，CSP还返回所有可以被用来辅助恢复出签名的辅助集合以及LBSP对Merkle哈希树根root的签名信息{H(root)}_K-1。

4、查询结果验证

一旦收到CSP返回的查询结果，用户使用如下方法验证查询结果的真实性和正确性。

首先，用户验证返回的POI数据密文的Hilbert值是否与Hilbert值查询Q'中Hilbert值在数量和数值上保持一致；然后，使用返回的POI数据密文和辅助集合验证LBSP对哈希树的根root的签名是否正确。如果正确，则认为CSP返回了完整的查询结果，否则查询结果不完整。

实施例

下面将结合实施例进一步说明本发明的有益效果。

本实施例中，哈希函数采用SHA-1，对称加密算法采用AES-128，处理器为Interl(R)Core(TM)i5-2320CPU@3.00GHZ，内存为4.0GB，操作系统为win7，采用的开发语言为JAVA，开发环境为JDK1.7和eclipse3.6，智能手机为小米5：骁龙^TM820四核2.15GHz处理器；3GB>

采用的数据集为位置服务研究中常用的数据集，其中包括4个真实数据集以及2个模拟数据集。真实数据集是从犹他大学官方网站获得的，包括如下四个真实路网POI数据集：OldenBurg(OL:6105个POI数据)、City of San Joaquin County(TG:18263个POI数据)、San Francisco(SF:174956个POI数据)、North America(NA:175813个POI数据)；模拟数据集是由chorochronos网站提供的空间数据生成器SpatialDataGenerators自动生成，包括均匀分布的数据集UN以及由4个高斯分布组成的偏斜数据集SK，数据集UN和SK的数据规模都为100000，其中UN为均匀分布，SK有4个Guass分布数据集组成，其中Guass分布的中心点为随机选择的，每个分布的数据规模为25000。6个数据集对应的分布如图5所示，这些真实数据以及模拟数据很好的对应了位置服务外包应用场景。

本实施例中Hilbert曲线的通用参数设置见表1，为使数据集中各POI空间对象的Hilbert值唯一，本实施例中各数据集所使用的曲线阶数见表2，在相应曲线阶数下，各数据集中POI空间对象的Hilbert值都是唯一的。

表1Hilbert曲线的通用参数

表2各数据集所使用的曲线阶数

图6和图7表示在同样实验参数情况下，方案[1]、方案[2]、本发明方案比较一对数值在PC端与手机端的计算开销，由图可知，本发明方案的计算开销小于方案[1]和方案[2]。又由于本发明方案只涉及HMAC和hash操作，不涉及复杂的模幂运算和大数乘法，因此随着元素位数的增加，本本发明方案的计算开销增长不明显，计算开销增长率远小于涉及模幂运算的方案[1]和方案[2]。

图8表示在同样实验参数情况下，方案[1]、方案[2]、本发明方案比较一对数值的通信开销。由图可知，本发明方案的通信开销小于方案[1]、方案[2]。由于本发明方案的通信只涉及到布隆过滤器的传输，而方案[1]和方案[2]在数值比较过程中均需要发送2^λ个整数，同时方案[2]还涉及不经意传输，因此随着λ的增大，方案[1]、方案[2]通信开销增长明显，为了保持布隆过滤器的误差最小，本发明布隆过滤器的位数也会随着λ增大而增长，通信开销也会相应增长，但是增长速度比方案[1]和方案[2]小。

由图6～图8分析可知，本发明方案的计算量与通信量都较小，全额可以精确匹配，因此，本发明方案更适合应用于资源有限的智能终端。

上述方案[1]和方案[2]指下述文献[1]和[2]中所记载的技术方案：

[1]Yao AC.Protocols for secure computations[C]//Foundations ofComputer Science,1982.SFCS'08.23rd Annual Symposium on.IEEE,1982:160-164.

[2]李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,33(5):769-773.