用于外包空间数据库的范围查询完整性验证方法

摘要

本发明公开了一种用于外包空间数据库的范围查询完整性验证方法，包括：1、基于自适应Hilbert曲线的范围查询转换，生成一维数值段集合；2、用户经过认证与外包空间数据库的服务商建立会话连接，将一维数值段集合发送给服务商；3、服务商根据用户提交的一维数值段集合，检索数据库中符合查询条件的空间对象集合，并将该空间对象集合返回给用户；4、用户接收到服务商返回的查询结果集合，并对其进行消息摘要验证；5、用户根据查询结果中的邻近空间对象信息，对结果集的完整性进行验证。本发明方法可以在外包空间数据库的模式下，为用户提供高效、安全的范围查询完整性验证功能，进而对服务商修改查询结果的行为进行约束，保证范围查询服务的质量。

说明书

技术领域

本发明属于数据库处理技术领域，具体涉及一种用于外包空间数据库的范围查询完整性验 证方法。

背景技术

随着基于位置的服务与位置感知设备日益普及，与位置相关的信息爆炸式增长，由此产生 的大量空间数据超出了小型企业和个人的处理能力。云存储服务提供弹性的资源分配，有效降 低了数据拥有者维护数据的开销，因此数据外包成为一种流行的服务模式。为了保护外包空间 数据的隐私并支持空间数据查询，需要在外包前对空间数据进行处理，构建用于查询的空间数 据索引，并对空间数据内容进行加密。然而，由于服务商在执行查询的过程中，可能对查询结 果进行修改，例如删除部分查询结果，从而在用户不知情的状况下降低服务质量。因此，在空 间数据库外包的服务模式下，保证空间查询的完整性是该服务模式健康发展所要解决的重要问 题。

目前多采用Hilbert曲线构建空间数据的索引，以支持隐私保护的空间查询，并提出了基 于随机复制的查询完整性验证方法，通过随机抽取部分原始数据作为副本，对原始数据和副本 数据采用不同的参数构建索引，从而生成外包数据，其查询完整性验证过程包括空间查询和完 整性验证查询两个步骤，空间查询阶段获得查询结果，完整性验证查询阶段则获得完整性验证 信息，这个过程需要用户与服务商建立两次会话连接，这增加了服务商进行查询分析的机会， 通过对空间查询和完整性验证查询的特征进行抽取，进行针对性的调整，规避完整性验证，另 外，在外包空间数据库中还需要存储额外的对象副本信息，大大增加了数据库系统的存储与维 护负担。

发明内容

本发明的目的在于提供一种外包空间数据库的范围查询完整性验证方法，通过在外包的密 文空间对象中附加基于索引的邻近空间对象信息，使用户可以从查询结果中直接获得完整性验 证的依据，将范围查询和完整性验证通过一次会话连接完成，降低了系统负载，提高了外包空 间数据库的查询效率，同时保证了数据库服务商诚实地为用户提供服务。

为了实现上述目的，本发明采用以下技术方案：

一种用于外包空间数据库的范围查询完整性验证方法，包括以下步骤：首先，用户通过自 适应Hilbert曲线将二维平面的范围查询转换为一维数值段集合，作为查询条件；然后，服务 商将符合查询条件的空间对象返回给用户，用户对查询结果进行消息摘要验证，若未通过则输 出查询结果不完整；最后，用户对查询结果邻居集合进行范围查询验证，若未通过则输出查询 结果不完整，否则输出查询结果完整。

一种用于外包空间数据库的范围查询完整性验证方法，包括以下步骤：

步骤一：用户通过自适应Hilbert曲线的范围查询转换方法，将二维平面的范围查询W＝[xl, xh]×[yl,yh]转换为一维数值段集合R＝{R₁(s₁,e₁),R₂(s₂,e₂),…,R_n(s_n,e_n)}，即查询条件；

xl,xh分别为二维平面的范围查询的x轴方向的最小值、最大值；yl,yh分别为二维平面的 范围查询的y轴方向的最小值、最大值；s_i,e_i分别表示数值段R_i的开始值、结束值，1≤i≤n，n 为数值段的个数；

步骤二：用户经过认证与外包空间数据库的服务商建立会话连接，将步骤一中生成的一维 数值段集合R发送给服务商；外包空间数据库中的每一条记录对应一个空间对象，数据表的 核心字段为一个三元组：<index，Enc((location，text，neighbors(f₍₁₎，f₍₂₎，…，f_(k)，b₍₁₎，b₍₂₎，…， b_(k)))，key)，Sign>；

index为根据当前空间对象的位置坐标location，使用自适应Hilbert曲线生成的索引；text 为当前空间对象附属的其他描述信息；neighbors为与当前空间对象在索引上近邻的空间对象 的位置坐标集合，f_(i)、b_(i)分别表示index的前驱、后继空间对象的位置坐标，1≤i≤k，k为前驱 /后继空间对象的个数，k的取值由数据拥有者设定；Enc()为对称加密算法，key为对称密钥； Sign为使用哈希算法Hash()生成的当前空间对象消息摘要，即 Sign＝Hash(location|text|neighbors)，|表示字符串连接运算；

步骤三：外包空间数据库服务商根据用户提交的一维数值段集合R＝{R₁(s₁,e₁),R₂(s₂,e₂),…, R_n(s_n,e_n)}，检索数据库中符合查询条件的空间对象集合G＝{p₁，p₂，…，p_m}，并将该空间对 象集合G返回给用户，其中：

p_i表示一个检索结果，包含索引值index_i，密文数据信息Enc((location_i，text_i，neighbors_i)， 以及消息摘要Sign_i，1≤i≤m，m为检索结果的个数；

步骤四：用户接收到服务商返回的查询结果集合G＝{p₁，p₂，…，p_m}，对其中的每一个 对象p_i＝<index_i，Enc((location_i，text_i，neighbors_i)，key)，Sign_i>，首先使用解密算法Dec()与密 钥key处理p_i的加密字段Enc((location_i，text_i，neighbors_i)，key)，得到p_i的明文信息(location_i， text_i，neighbors_i)，然后使用哈希算法Hash()生成明文信息的消息摘要，即 Sign_i’＝Hash(location_i|text_i|neighbors_i)，判断Sign_i’与Sign_i是否相同，若不相同，则证明空间对 象p_i的信息被篡改，终止查询完整性验证过程，输出查询结果不完整；若对任意p_j∈G，均有 Sign_j’＝Sign_j，，则进一步进行步骤五；

步骤五：将通过步骤四验证的查询结果集合G＝{p₁，p₂，…，p_m}，分为两类集合：查询 结果位置集合Q＝{location₁，location₂，…，location_m}，查询结果邻居集合N＝{neighbors₁， neighbors₂，…，neighbors_m}；

其中：location_i为第i个查询结果的位置坐标；neighbors_i＝(f_i(1)，f_i(2)，…，f_i(k)，b_i(1)，b_i(2)，…， b_i(k))为与第i个查询结果在索引上近邻的空间对象的位置坐标集合，f_i(j)、b_i(j)分别为location_i 的第j个前驱、后继空间对象的位置坐标，1≤j≤k，k为前驱/后继空间对象的个数；

对于任意位置坐标d(x,y)∈N，若d存在于范围查询W＝[xl,xh]×[yl,yh]中，则判断d是否 属于查询结果位置集合Q，若不属于，则终止查询完整性验证过程，输出查询结果不完整；若 查询结果邻居集合N中不存在满足上述条件的位置坐标，则完成查询完整性验证过程，输出 查询结果完整。

优选的，步骤三种判定p_i符合查询条件的具体依据为：存在R_j∈R，使得s_j≤index_i≤e_j。

优选的，判定位置坐标d(x,y)存在于范围查询W中的具体依据为：xl≤x≤xh，且yl≤y≤yh。 其中x，y分别为d在x轴、y轴方向的坐标值；判定位置坐标d(x,y)属于查询结果位置集合Q 的具体依据为：存在location_j(x_j,y_j)∈Q，使得x_j＝x，且y_j＝y。

和现有技术相比，本发明具有以下优点：

1、更高的安全性

本发明提出的外包空间数据库范围查询完整性验证方法将传统的空间查询和完整性验证 查询合并为一次，通过一次范围查询获得查询结果与完整性验证信息，从而减少了服务商进行 查询分析的机会；并且由于不同的数据拥有者可能设置不同的邻近空间对象数量，这进一步增 大了服务商进行查询结果更改的难度。

2、更高的存储与查询效率

传统的基于随机复制的查询完整性验证方法，在数据库中需要存储额外的对象副本信息， 大大增加了数据库系统的存储与维护负担，而本发明对外包空间数据库中的对象，仅附加少许 邻近对象信息，从而提高了数据库存储资源的利用率；通过将空间查询和完整性验证查询进行 合并，减少了用户与服务商的会话连接次数，提高了查询效率。

本发明公开了一种用于外包空间数据库的范围查询完整性验证方法，包括：1、基于自适 应Hilbert曲线的范围查询转换，生成一维数值段集合；2、用户经过认证与外包空间数据库 的服务商建立会话连接，将一维数值段集合发送给服务商；3、服务商根据用户提交的一维数 值段集合，检索数据库中符合查询条件的空间对象集合，并将该空间对象集合返回给用户；4、 用户接收到服务商返回的查询结果集合，并对其进行消息摘要验证；5、用户根据查询结果中 的邻近空间对象信息，对结果集的完整性进行验证。本发明方法可以在外包空间数据库的模式 下，为用户提供高效、安全的范围查询完整性验证功能，进而对服务商修改查询结果的行为进 行约束，保证范围查询服务的质量。

附图说明

图1为本发明用于外包空间数据库的范围查询完整性验证方法的流程框图。

具体实施方式

下面结合附图对本发明做进一步详细说明。

请参阅图1所示，本发明一种用于外包空间数据库的范围查询完整性验证方法，包括以下 步骤：首先，用户通过自适应Hilbert曲线将二维平面的范围查询转换为一维数值段集合，作 为查询条件；然后，服务商将符合查询条件的空间对象返回给用户，用户对查询结果进行消息 摘要验证，若未通过则输出查询结果不完整；最后，用户对查询结果邻居集合进行范围查询验 证，若未通过则输出查询结果不完整，否则输出查询结果完整。具体包括下列步骤：

步骤一：用户通过自适应Hilbert曲线的范围查询转换方法，将二维平面的范围查询W＝[xl, xh]×[yl,yh]转换为一维数值段集合R＝{R₁(s₁,e₁),R₂(s₂,e₂),…,R_n(s_n,e_n)}，即查询条件，其中：

xl,xh分别为二维平面的范围查询的x轴方向的最小值、最大值，yl,yh分别为二维平面的 范围查询的y轴方向的最小值、最大值。s_i,e_i分别表示数值段R_i的开始值、结束值，1≤i≤n，n 为数值段的个数。

步骤二：用户经过认证与外包空间数据库的服务商建立会话连接，将步骤一中生成的一维 数值段集合R发送给服务商；外包空间数据库中的每一条记录对应一个空间对象，数据表的 核心字段为一个三元组：<index，Enc((location，text，neighbors(f₍₁₎，f₍₂₎，…，f_(k)，b₍₁₎，b₍₂₎，…， b_(k)))，key)，Sign>，其中：

index为根据当前空间对象的位置坐标location，使用自适应Hilbert曲线生成的索引；text 为当前空间对象附属的其他描述信息；neighbors为与当前空间对象在索引上近邻的空间对象 的位置坐标集合，f_(i)、b_(i)分别表示index的前驱、后继空间对象的位置坐标，1≤i≤k，k为前驱 /后继空间对象的个数，k的取值由数据拥有者设定；Enc()为对称加密算法，key为对称密钥； Sign为使用哈希算法Hash()生成的当前空间对象消息摘要，即 Sign＝Hash(location|text|neighbors)，|表示字符串连接运算。

步骤三：外包空间数据库服务商根据用户提交的一维数值段集合R＝{R₁(s₁,e₁),R₂(s₂,e₂),…, R_n(s_n,e_n)}，检索数据库中符合查询条件的空间对象集合G＝{p₁，p₂，…，p_m}，并将该空间对 象集合G返回给用户，其中：

p_i表示一个检索结果，包含索引值index_i，密文数据信息Enc((location_i，text_i，neighbors_i)， 以及消息摘要Sign_i，1≤i≤m，m为检索结果的个数。

判定p_i符合查询条件的具体依据为：

存在R_j∈R，使得s_j≤index_i≤e_j。

步骤四：用户接收到服务商返回的查询结果集合G＝{p₁，p₂，…，p_m}，对其中的每一个 对象p_i＝<index_i，Enc((location_i，text_i，neighbors_i)，key)，Sign_i>，首先使用与Enc()对应的解密 算法Dec()与密钥key处理空间对象p_i的加密字段Enc((location_i，text_i，neighbors_i)，key)，得 到p_i的明文信息(location_i，text_i，neighbors_i)，然后使用与步骤二相同的哈希算法Hash()生成明 文信息的消息摘要，即Sign_i’＝Hash(location_i|text_i|neighbors_i)，判断Sign_i’与Sign_i是否相同，若 不相同，则证明空间对象p_i的信息被篡改，终止查询完整性验证过程，输出查询结果不完整； 若对任意p_j∈G，均有Sign_j’＝Sign_j，则进一步进行下述过程。

步骤五：将通过步骤四验证的查询结果集合G＝{p₁，p₂，…，p_m}，分为两类集合：查询 结果位置集合Q＝{location₁，location₂，…，location_m}，查询结果邻居集合N＝{neighbors₁， neighbors₂，…，neighbors_m}，其中：

location_i为第i个查询结果的位置坐标；neighbors_i＝(f_i(1)，f_i(2)，…，f_i(k)，b_i(1)，b_i(2)，…， b_i(k))为与第i个查询结果在索引上近邻的空间对象的位置坐标集合，f_i(j)、b_i(j)分别为location_i的第j个前驱、后继空间对象的位置坐标，1≤j≤k，k为前驱/后继空间对象的个数。

对于任意位置坐标d(x,y)∈N，若d存在于范围查询W＝[xl,xh]×[yl,yh]中，则判断d是否 属于查询结果位置集合Q，若不属于，则终止查询完整性验证过程，输出查询结果不完整；若 查询结果邻居集合N中不存在满足上述条件的位置坐标，则完成查询完整性验证过程，输出 查询结果完整。

判定位置坐标d(x,y)存在于范围查询W中的具体依据为：

xl≤x≤xh，且yl≤y≤yh。其中x，y分别为d在x轴、y轴方向的坐标值。

判定位置坐标d(x,y)属于查询结果位置集合Q的具体依据为：

存在location_j(x_j,y_j)∈Q，使得x_j＝x，且y_j＝y。

综上所述，本发明提出一种用于外包空间数据库的范围查询完整性验证方法。该方法通过 在外包空间对象中，附加基于索引的邻近对象信息，降低了查询完整性验证对数据库存储系统 的资源消耗。该方法将传统的空间查询和完整性验证查询合并为一次，降低了用户与服务商的 会话连接次数，提高了查询效率，减少了服务商进行查询分析的机会；并且由于不同的数据拥 有者可能设置不同的邻近空间对象数量，这进一步增大了服务商进行查询结果更改的难度。