一种隐私保护多维范围查询方法、装置及存储介质

1.本发明涉及数据加密领域，尤其是涉及一种基于分层hilbert编码的隐私保护多维范围查询方法、装置及存储介质。


背景技术：

2.在不完全可信的云服务环境中，数据拥有者通常将数据加密上传至云服务器，当前多维数据逐维加密方式可以支持隐私保护的多维查询，但数据维度的增高以及空间划分间隔的宽泛，导致云服务器查询结果中包含的冗余数据增多、查询效率降低。基于这种情况，已经存在关于数据密文的范围查询技术，但是这些技术在密文数据范围查询与验证中仍存在相应的问题。例如，songyui wu等人在发表的论文“servedb:secure,verifiable,and eff icient range queries onoutsourced data base”(2019ieee 35th international conference on data engineering(icde))中提出了一种支持多维密文数据的可验证范围查询方法。该方法首先将多维数据利用aes加密，其次为了隐藏多维度数据的数据信息，将多维数据转成一系列的cube codes，然后构建索引结构，索引以标准型布隆过滤器为节点存储，使得云数据库无需解密即可比较多维数据是否满足查询范围。但是这样的方案仍存在不足之处，在其索引树构建的过程中，左右孩子节点中的存储的数据是随意划分的，这使得在进行深度遍历时多维空间相邻的数据无法得到有效的查询，而需要多次遍历相同的节点，增加计算开销，降低了查询效率。


技术实现要素：

3.本发明的目的在于针对上述现有技术中密文数据的验证查询方法计算开销大，查询效率不高的缺陷，提供一种基于分层hilbert编码的隐私保护多维范围查询方法、装置及存储介质，通过分层hilbert编码对多维空间进行细粒度划分并将多维数据分层编码以避免数据顺序特性泄露，同时在编码的数据上结合计数型布隆过滤器(counting bloom filter,cbf)构建索引结构实现密文安全检索，能够用于在云存储背景下同时对云数据库接收的密态多维数据进行范围查询。
4.本发明的目的可以通过以下技术方案来实现：
5.一种基于分层hilbert编码的隐私保护多维范围查询方法，包括以下步骤：
6.s1：数据拥有者生成整个密文范围查询所需要的密钥；
7.s2：数据拥有者利用分层hilbert编码后的密文构建hhcb树(hierarchical hilbert counting bloom filter tree,hhcbtree)；
8.s3：数据使用者将多维范围查询条件按照s2中的分层hilbert编码方式对查询范围进行编码，并利用哈希函数对范围编码集进行哈希映射，生成多维数据查询需要的查询门限；
9.s4：云数据库利用查询门限对hhcb树展开查询，将得到的查询结果返回给数据使用者。
10.所述s1中，数据拥有者通过输入安全参数λ，输出对称密钥sk来加密多维数据，输出hmac哈希函数密钥key，树节点所需随机数r＝{r1,...,r
2n+1
}，其中，n为多维数据的维度。
11.所述s2包括以下步骤：
12.s21：数据拥有者利用分层hilbert编码，在实现n维数据向k维数据的转化的同时隐藏数据信息，即将多维数据映射到k个细粒度划分的多维空间，每个多维数据在相应的第i层空间中都依据hilbert编码方式生成相应的第i层hilbert编码，最终每个多维数据由一个包含k个hilbert编码的编码集组成；
13.s22：根据hilbert编码构建hhcb索引树，其中，hhcb索引树的每个节点均为计数型布隆过滤器(counting bloom filter,cbf)，将编码后的数据映射进布隆过滤器中；
14.s23：hhcb索引树的根节点存储所有数据的编码，其左右孩子节点分别存储一半其父节点中的数据编码，根节点数据依据近似编码划分算法被分配到其左右孩子节点，以此类推直至生成仅包含一个多维数据编码的叶节点。
15.所述s21包括以下步骤：
16.s211：数据拥有者确认多维数据各个维度的最大值和最小值，设定最小间隔单元的边长，确定k值，对多维数据划分进k层空间；
17.s212：对每一层的多维数据采用hilbert编码，并将每个hilbert编码hc(o)作用于hmac函数生成该层数据编码其中区别码diff_num＝0.00001
×
li用于避免不同层级出现相同编码，key为哈希密钥，li表示层级数；每个多维数据拥有k个hilbert编码，共同组成了多维数据o的分层hilbert编码，并且编码过程中第k层的最小间隔单元中最多包含一个多维数据项。
18.所述k值满足：|上界-下界|《2k*step，其中，step为最小间隔单元的边长，其小于多维数据每一维的数轴上数据间的最小间距。
19.所述s3包括以下步骤：
20.s31：数据使用者发送多维数据范围查询的查询请求，并将其查询范围标记为q，利用分层hilbert编码对查询范围q进行转化得到范围编码集{q}；
21.s32：利用hmac函数对范围编码集{q}中的每个数据进行r次运算，得到k*r个hmac地址，基于地址组成查询门限矩阵t
{q}
。
22.所述s4包括以下步骤：
23.s41：云数据查询过程中，判断查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器是否匹配，若匹配，则继续查询左右孩子节点，直至叶子节点停止检索；若不匹配，则当前节点下的所有子节点不再参与查询遍历；
24.s42：云数据库将符合查询条件的查询结果存入查询结果集r；
25.s43：云数据库将查询结果集r返回给数据使用者，数据使用者对查询结果集r进行解密获取最终结果。
26.所述s41中，判断查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器是否匹配具体为：
27.检查t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值是否均大于等于1，
28.若t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数
值是否均大于等于1，表明第i行hmac地址对应的多维数据与编码的查询范围存在交集，则当前节点中有数据符合查询范围的数据，即查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器相匹配；
29.若t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值非均大于等于1，表明该布隆过滤器不包含第i行hmac地址对应的多维数据oi，且hhcb索引树中包含该布隆过滤器的节点的左右子节点也不包含多维数据oi，即查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器不匹配。
30.一种基于分层hilbert编码的隐私保护多维范围查询装置，包括存储器、处理器，以及存储于所述存储器中的程序，所述处理器执行所述程序时实现如上述所述的方法。
31.一种存储介质，其上存储有程序，所述程序被执行时实现如上述所述的方法。
32.与现有技术相比，本发明具有以下有益效果：
33.(1)本发明引入分层hilbert编码方式对多维空间进行细粒度划分并将多维数据分层编码以避免数据顺序特性泄露，减少了查询时繁琐的加解密计算过程，从而提高了查询效率。
34.(2)本发明在编码的数据上结合计数型布隆过滤器构建索引结构，引入近似编码划分方法提高了遍历效率。
35.(3)本发明克服了现有技术中计算开销大，查询效率不高的缺陷，能够更好的运用在实际的云密态数据库场景中，实现云存储背景下同时对云数据库接收的密态多维数据进行范围查询。
附图说明
36.图1为本发明的方法流程示意图；
37.图2为分层hilbert编码时的k值确定图；
38.图3为分层hilbert编码方式示意图；
39.图4为分层hilbert编码方式中范围编码示意图；
40.图5为hhcb树结构和cbf结构示意图。
具体实施方式
41.下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。
42.本实施例提供一种基于分层hilbert编码的隐私保护多维范围查询方法，如图1所示包括以下步骤：
43.s1：数据拥有者生成整个密文范围查询所需要的密钥。
44.s2：数据拥有者对多维明文数据利用分层hilbert编码方式进行编码，基于编码后的密文构建hhcb树(hierarchical hilbert counting bloom filter tree,hhcbtree)，每个节点都由一个计数型布隆过滤器构建，且构建时数据划分按照近似编码划分算法划分。
45.s21：数据拥有者利用分层hilbert编码，在实现n维数据向k维数据的转化的同时隐藏数据信息，即将多维数据映射到k个细粒度划分的多维空间，每个多维数据在相应的第
i层空间中都依据hilbert编码方式生成相应的第i层hilbert编码，最终每个多维数据由一个包含k个hilbert编码的编码集组成。
46.s211：数据拥有者确认多维数据各个维度的最大值和最小值，设定最小间隔单元的边长，确定k值，对多维数据划分进k层空间。
47.s212：对每一层的多维数据采用hilbert编码，并将每个hilbert编码hc(o)作用于hmac函数生成该层数据编码其中区别码diff_num＝0.00001
×
li用于避免不同层级出现相同编码，key为哈希密钥，li表示层级数；每个多维数据拥有k个hilbert编码，共同组成了多维数据o的分层hilbert编码，并且编码过程中第k层的最小间隔单元中最多包含一个多维数据项。
48.s22：根据hilbert编码构建hhcb索引树，其中，hhcb索引树的每个节点均为计数型布隆过滤器(counting bloom filter,cbf)，将编码后的数据映射进布隆过滤器中。
49.s23：hhcb索引树的根节点存储所有数据的编码，其左右孩子节点分别存储一半其父节点中的数据编码，根节点数据依据近似编码划分算法被分配到其左右孩子节点，以此类推直至生成仅包含一个多维数据编码的叶节点。
50.s3：数据使用者将多维范围查询条件按照s2中的分层hilbert编码方式对查询范围进行编码，并利用哈希函数对范围编码集进行哈希映射，生成多维数据查询需要的查询门限，并发送给云数据库。
51.s31：数据使用者发送多维数据范围查询的查询请求，并将其查询范围标记为q，利用分层hilbert编码对查询范围q进行转化得到范围编码集{q}；
52.s32：利用hmac函数对范围编码集{q}中的每个数据进行r次运算，得到k*r个hmac地址，基于地址组成查询门限矩阵t
{q}
。
53.s4：云数据库利用查询门限对hhcb树展开查询，将得到的查询结果返回给数据使用者。
54.s41：云数据查询过程中，判断查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器是否匹配，即检查t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值是否均大于等于1。匹配原则如下：
55.s411：若t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值是否均大于等于1，说明第i行hmac地址对应的多维数据与编码的查询范围存在交集，则当前节点中有数据符合查询范围的数据。
56.s412：若t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值非均大于等于1，说明该布隆过滤器不包含第i行hmac地址对应的多维数据oi，且hhcb索引树中包含该布隆过滤器的节点的左右子节点也不包含多维数据oi。
57.若符合s411情况，则继续查询左右孩子节点，直至叶子节点停止检索；若符合s421情况，则当前节点下的所有子节点不再参与查询遍历。
58.s42：云数据库将符合查询条件的查询结果存入查询结果集r。
59.s43：云数据库将查询结果集r返回给数据使用者，数据使用者对查询结果集r进行解密获取最终结果。
60.上述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说
对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
61.以下提供一种择优的实施例，在该实施例中，实验运行在windows 10系统下，机器配置：2.90ghz amd ryzen 7 4800h处理器，16gb内存；哈希函数个数r＝10，cbf误判率f＝0.00001。
62.本实施例选用真实数据集作为实验数据集，该数据集包含420768项数据，通过人工复制的方式扩充到50万条数据。下面介绍基于分层hilbert编码的隐私保护多维范围查询方法的具体实现过程。
63.步骤1：数据拥有者利用aes算法加密多维明文数据并生成方案所需所有密钥。
64.输入安全参数λ，输出对称密钥sk来加密多维数据，输出hmac哈希函数密钥key，树节点所需随机数r＝{r1,...,r
2n+1
}，其中，n为多维数据的维度。
65.步骤2：数据拥有者利用分层hilbert编码对数据编码并利用编码后的数据生成hhcb索引树。
66.构建hhcb索引树的数据编码方式与查询范围的编码方式均根据分层hilbert编码体系(hhcs)，两种编码方式相近但又略有不同，在hhcs编码体系中为了减低最终的查询误差，k值的确定通过对空间细粒度的划分得到。下面将具体介绍：
67.b1：首先确定k值。如图2所示为分层hilbert编码时的k值确定图，该值是分层hilbert编码划分的基础。k值与hilbert编码的阶数等值，确定k值就是确定hilbert曲线要划分至k阶。在第k阶的划分空间中，每个最小间隔单元内都对多包含一个数据项，下面以示例说明k值的确定方式。
68.图2(a)的一维数轴上包含三个数据x1,x2,x3，|x
3-x2|为轴上数据间最小间距min_step，记任意小于min_step的间隔为最小间隔单元step。图2(b)中，x1,x2,x3均独立分布于一维数轴的最小间隔单元中。当满足计算条件|上界-下界|《2k*step时，可以确定k值。拓展至n维空间，ki是第i维度获取的k值。图2(c)是以step细粒度划分的二维空间，a,b,c为x1,x2,x3向二维空间的拓展，均独立存在于二维最小间隔空间中，每个最小间隔空间至多包含一个数据。
69.b2：根据确定的k值，利用分层hilbert编码体系分别为多维数据和多维范围生成编码。进一步地，b2具体步骤如下：
70.数据拥有者确立基本n维立方体作为分层迭代基础。对于给定多维数据集d＝{d1,..,dn}确定d各维度最大值与最小值。对基本n维立方体各维度二分，生成2n个大小相等的一层n维子立方体1_sub_cubes，以此类推，第i+1层n维子立方体由每个i层n维子立方体2n等分生成，至k层停止，k是基本n维立方体的总分层次数。经k次分层，第k层中每个子立方体边长小于给定阈值且最多包含一个数据。图3给出各维度范围在[0,8]的基本2维立方体，一次划分后被分成4个1_sub_cube，二次划分后每个1_sub_cube又被分成4个2_sub_cube，共生成16个2_sub_cube。
[0071]
b3：获取多维数据在hhcs编码在子立方体生成时计算，不同层级的子立方体的编
码具有唯一性，且第i层子立方体的编码就是包含于其中的多维数据在第i层的编码。假设有一个包含多维数据dj的第i层子立方体g，g的空间坐标(xb,yb)，x,y由b位二进制表示，b＝i。第i层子立方体g根据静态演化规则对空间坐标(xb,yb)降维生成对应的hilbert编码hc(xb,yb)，第i层子立方体g的hhcs编码其中区别码diff_num＝0.00001
×
li用于避免不同层级出现相同编码，最后利用哈希函数hmac和密钥key对第i层hilbert编码与区别码之和运算。同时ci也是多维数据dj在第i层的编码。
[0072]
b4：数据拥有者生成多维数据的hhcs编码。一个多维数据的最终hhcs编码是由k个层级的hhcs编码组成的编码集合。以图3中多维数据d1为例，k＝3。首先获得一次划分后d1所在子立方体的空间坐标(0,0)，其次计算hilbert编码hc(0,0)＝0，一次划分的hhcs编码c1＝hmac(key,0.00001)，key为密钥，最后重复上述过程，直至k层。多维数据d1在第二、第三层的hhcs编码分别为c2＝hmac(key,3.00002),c3＝hmac(key,7.00003)。d1的最终编码集合c
d1
＝{c1,c2,c3}。
[0073]
b5：数据拥有者生成查询范围的hhcs编码。为避免范围编码至k层时编码集过大，hhcs编码体系由上至下依据层级顺序产生查询范围编码集合。从一次划分后，hhcs编码体系会寻找满足查询范围内的一层子立方体，若第i层的子立方体表示的空间完全包含于查询范围中，则将对应编码加入查询编码集合，否则访问下一层子立方体，重复上述操作直至k层。若k层子立方体表示的空间部分包含于查询范围，也将对应编码加入查询编码集合。
[0074]
以图4中二维查询范围q为例，在一层子立方体1_sub_cubes中，编码区2大于查询范围，无子立方体完全包含在范围q内，则访问下一层子立方体。在二层子立方体2_sub_cubes中编码区8完全被查询范围覆盖，则分层编码ca加入查询范围编码集合。在3_sub_cubes中，编码区45和编码区46满足q除ca区域剩余查询范围，cb,cc加入查询范围编码集。q的最终查询范围编码集为cq＝{ca,cb,cc}。cb,cc表示k层子立方体并不完全满足查询范围的区域，尽管k层子立方体最多包含一个数据，但查询结果中仍有极少的范围边缘数据。这种情况下，要求数据使用者解密查询结果，筛除极少数不符合要求的范围边缘数据。
[0075]
b6：多维数据和查询范围利用hhcs编码集合判断两个集合是否相交的，避免查询过程中数据顺序特性的泄露。图4中，多维数据m的编码集cm＝{g1＝hmac(key,2.00001),g2＝hmac(key,8.00002),g3＝hmac(key,33.00003)}。多维范围q的hhcs编码集cq＝{ca＝hmac(key,8.00002),cb＝hmac(key,
[0076]
46.00003),cc＝hmac(key,45.00003)}。c
t
∩cq＝{g2＝ca}，则m满足q范围。
[0077]
步骤三：在hhcs编码基础上创建索引hhcbtree。hhcbtree是在hhcs编码后的数据上创建的高度平衡的二叉树，创建方式自上而下。由n-1个非叶节点和n个叶节点组成，节点由cbf构成，叶节点连接加密多维数据。
[0078]
c1：hhcbtree中节点cbf大小随存储其中的数据数量变化。给定数据集d＝{d1,..,dn}，d的hhcs编码集cd＝{c
d1
,
…
,c
dn
},c
di
＝{c1,
…
,ck}。在cbf误差率f和哈希函数个数r确定情况下，公式(1)可以确定节点cbf的大小p，其中n为插入cbf的数据个数，e是自然对数。
[0079][0080]
多维数据di的hhcs编码c
di
存储于cbf包括三个步骤：
[0081]
c11：单向映射。对于编码j∈[1,k]，给定r个密钥key1,
…
,keyr和hmac，可以计算出r个相应的哈希地址hmac(key1,cj),
…
,hmac(keyr,cj)。
[0082]
c12：去相关性。将r个哈希地址与随机数α
i(i＝1,
…
,2n-1)
二次哈希映射生成新的r个哈希地址hmac(αi,hmac(key1,cj))％p,..,hmac(αi,hmac(keyr,cj))％p，随机数αi避免了相同数据生成相同地址值，使得不同节点间相同数据的个数无法被概率统计
[19]
。
[0083]
c13：映射存储。将cbf中新的r个哈希地址处的计数器增1。当c
di
中k个编码均完成单项映射、去相关性、映射存储步骤，则di存储完成。图5(b)展示了di在cbf的存储过程。
[0084]
c2：hhcbtree创建具体创建过程如下：
[0085]
c21：根节点cbf存储cd中全部数据，根节点的左右节点存储cd随机二分后的两个子集c
dleft
和c
dright
的数据，ed为加密多维数据集合，与cd划分一致，ed分成两个子集e
dleft
和e
dright
，ed为cd中编码对应的加密数据。
[0086]
c22：若父节点数据总量n为偶数，则左右节点存储数据采用近似编码划分|c
dleft
|＝|c
dright
|，若n为奇数，则采用近似编码划分|c
dleft
|＝|c
dright
|+1，即左节点比右节点多一个数据。以此类推，直至集合大小为1。当编码集合cd只包含一个数据项的编码集，此时达到叶节点的创建条件，生成对应的cbf，同时叶节点与对应的加密多维数据连接。当cd是空集时不再创建cbf，即递归终止，达到收敛。图5(a)为包含10个数据的hhcbtree。近似编码划分伪代码如下：
[0087]
算法1:近似编码划分(approximatecodepartition)
[0088][0089]
步骤四：数据使用者生成查询门限。
[0090]
给定查询范围q＝[a,b]，范围编码集cq＝{c1,
…
,cq},c
i(i＝1,..,q)
，数据使用者将cq中每个编码利用r个密钥执行r次hmac运算，生成查询门t
[q]
:{{hmac(key1,c1),
…
,hmac(keyr,c1)},
…
,{hmac(key1,ci),
…
,hmac(keyr,ci)},
…
,{hmac(key1,cq),
…
,hmac(keyr,cq)}}。
[0091]
步骤五：云数据库根据查询门限以及hhcbtree进行范围查询。
[0092]
e1：cbf匹配。利用节点中的随机数node.αi对t
qr
中编码t
ij(i∈[1,q]；j∈[1,r])
二次哈希运算获取最终哈希地址值[t
qr
]，若查询门限[t
qr
]存在i(1≤i≤q)行中任意列j(1≤j≤r)均满足node.cbf[[t
ij
]mod node.p]≥1，则cbf中至少存在一个满足查询条件的数据，记cbf匹配成功。
[0093]
e2：若查询门限[t
qr
]任意i(1≤i≤q)行中任意列j(1≤j≤r)均存在node.cbf[[t
ij
]mod node.p]＝0，则表示cbf中没有满足查询条件的数据，记cbf匹配失败。
[0094]
e3：利用查询门限对hhcb树进行遍历。hhcbtree t的根节点用root表示，在树遍历过程中，若访问节点时cbf匹配成功，则继续访问左右子树直至叶节点leaf停止，并将结果
添加至查询密文结果集r。若则节点中存储的数据不满足查询条件，遍历结束。在遍历过程中，若查询门限第i(1≤i≤q)行中存在第j列满足node.cbf[[t
ij
]mod node.p]＝0，则将第i行从查询门限中删除，避免无效范围重复进行cbf匹配，因为子节点cbf中存储的数据集合cbf中存储的数据集合当父节点数据集合与查询门限不相交子节点数据集合与查询门限也不相交
[0095]
以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思做出诸多修改和变化。因此，凡本技术领域中技术人员依据本发明的构思在现有技术的基础上通过逻辑分析、推理、或者有限的实验可以得到的技术方案，皆应在权利要求书所确定的保护范围内。

技术特征：
1.一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，包括以下步骤：s1：数据拥有者生成整个密文范围查询所需要的密钥；s2：数据拥有者利用分层hilbert编码后的密文构建hhcb树；s3：数据使用者将多维范围查询条件按照s2中的分层hilbert编码方式对查询范围进行编码，并利用哈希函数对范围编码集进行哈希映射，生成多维数据查询需要的查询门限；s4：云数据库利用查询门限对hhcb树展开查询，将得到的查询结果返回给数据使用者。2.根据权利要求1所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述s1中，数据拥有者通过输入安全参数，输出对称密钥来加密多维数据，输出hmac哈希函数密钥，树节点所需随机数。3.根据权利要求1所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述s2包括以下步骤：s21：数据拥有者利用分层hilbert编码，在实现n维数据向k维数据的转化的同时隐藏数据信息，即将多维数据映射到k个细粒度划分的多维空间，每个多维数据在相应的第i层空间中都依据hilbert编码方式生成相应的第i层hilbert编码，最终每个多维数据由一个包含k个hilbert编码的编码集组成；s22：根据hilbert编码构建hhcb索引树，其中，hhcb索引树的每个节点均为计数型布隆过滤器，将编码后的数据映射进布隆过滤器中；s23：hhcb索引树的根节点存储所有数据的编码，其左右孩子节点分别存储一半其父节点中的数据编码，根节点数据依据近似编码划分算法被分配到其左右孩子节点，以此类推直至生成仅包含一个多维数据编码的叶节点。4.根据权利要求3所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述s21包括以下步骤：s211：数据拥有者确认多维数据各个维度的最大值和最小值，设定最小间隔单元的边长，确定k值，对多维数据划分进k层空间；s212：对每一层的多维数据采用hilbert编码，并将每个hilbert编码h
c
(o)作用于hmac函数生成该层数据编码c
i
＝hmac(key,[h
c
(o)]
li
+diff_num)，其中区别码diff_num＝0.00001
×
l
i
用于避免不同层级出现相同编码，key为哈希密钥，l
i
表示层级数；每个多维数据拥有k个hilbert编码，共同组成了多维数据o的分层hilbert编码，并且编码过程中第k层的最小间隔单元中最多包含一个多维数据项。5.根据权利要求4所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述k值满足：|上界-下界|<2
k
*step，其中，step为最小间隔单元的边长，其小于多维数据每一维的数轴上数据间的最小间距。6.根据权利要求1所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述s3包括以下步骤：s31：数据使用者发送多维数据范围查询的查询请求，并将其查询范围标记为q，利用分层hilbert编码对查询范围q进行转化得到范围编码集{q}；s32：利用hmac函数对范围编码集{q}中的每个数据进行r次运算，得到k*r个hmac地址，基于地址组成查询门限矩阵t
{q}
。
7.根据权利要求6所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述s4包括以下步骤：s41：云数据查询过程中，判断查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器是否匹配，若匹配，则继续查询左右孩子节点，直至叶子节点停止检索；若不匹配，则当前节点下的所有子节点不再参与查询遍历；s42：云数据库将符合查询条件的查询结果存入查询结果集；s43：云数据库将查询结果集返回给数据使用者，数据使用者对查询结果集进行解密获取最终结果。8.根据权利要求7所述的一种基于分层hilbert编码的隐私保护多维范围查询方法，其特征在于，所述s41中，判断查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器是否匹配具体为：检查t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值是否均大于等于1，若t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值是否均大于等于1，表明第i行hmac地址对应的多维数据与编码的查询范围存在交集，则当前节点中有数据符合查询范围的数据，即查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器相匹配；若t
{q}
中任意第i行的hmac地址在每个节点中的布隆过滤器相应地址处存储的数值非均大于等于1，表明该布隆过滤器不包含第i行hmac地址对应的多维数据o
i
，且hhcb索引树中包含该布隆过滤器的节点的左右子节点也不包含多维数据o
i
，即查询门限矩阵t
{q}
与hhcb索引树中的布隆过滤器不匹配。9.一种基于分层hilbert编码的隐私保护多维范围查询装置，包括存储器、处理器，以及存储于所述存储器中的程序，其特征在于，所述处理器执行所述程序时实现如权利要求1-8中任一所述的方法。10.一种存储介质，其上存储有程序，其特征在于，所述程序被执行时实现如权利要求1-8中任一所述的方法。

技术总结
本发明属于数据加密领域，涉及一种隐私保护多维范围查询方法、装置及存储介质，其中方法包括以下步骤：数据拥有者生成整个密文范围查询所需要的密钥；数据拥有者利用分层Hilbert编码后的密文构建HHCB树；数据使用者将多维范围查询条件按照分层Hilbert编码方式对查询范围进行编码，并利用哈希函数对范围编码集进行哈希映射，生成查询门限；云数据库利用查询门限对HHCB树展开查询，将得到的查询结果返回给数据使用者。与现有技术相比，本发明引入分层Hilbert编码方式，减少了查询时繁琐的加解密计算过程，提高了查询效率；在索引构建方面引入近似编码划分方法提高了遍历效率，更适用于实际的云密态数据库场景。更适用于实际的云密态数据库场景。更适用于实际的云密态数据库场景。


技术研发人员：田秀霞 卢映如 牛晓宇 张思成 陈强 陈思远
受保护的技术使用者：上海电力大学
技术研发日：2023.06.20
技术公布日：2023/9/20