构建密文范围检索结果完备性验证数据结构的方法及系统

conference on management of data.acm,2009.)等树结构的方法，基于密码学聚合签名的方法(mykletun e,narasimha m,tsudik g.authentication and integrity in outsourced databases[j].acm transactions on storage,2006,2(2):107-138.)，基于密码学累加器的方法(zhang y,katz j,papamanthou c.integridb:verifiable sql for outsourced databases[c]//proceedings of the 22nd acm sigsac conference on computer and communications security.2015:1480-1491.)等。然而前述方法均假设数据集是明文数据集或仅经过保序加密，在这些方法中服务提供商(通常是云数据库)可以获知数据集的明文记录或数据记录之间的顺序信息，暴露了相关数据的隐私。
[0009]
为了保护数据隐私，wu等人提出了一种支持密文数据范围检索结果完备性验证的验证数据结构svetree以及相应的原型系统servedb(wu s,li q,li g,et al.servedb:secure,verifiable,and efficient range queries on outsourced database[c/ol]//2019ieee 35th international conference on data engineering(icde).2019:626-637.doi:10.1109/icde.2019.00062.)。但验证数据结构svetree构造过程的计算与存储开销高昂，导致其难以处理亿级规模的大规模数据集。svetree构造过程的时间与存储开销受数据记录在值域空间中的分布的影响。当数据记录在值域空间中分布不均匀时，即少部分记录集中在小片区域中，svetree会采用更多的立方体编码层次数来缩小立方体的规模，这会导致svetree结构的计算与存储开销显著增长。同时，验证数据结构svetree会为每一条数据记录生成一个叶节点，当数据集包含的数据记录为亿级规模时，svetree结构包含的树顶点数量也是亿级规模，svetree结构为每个树顶点计算相应的布隆过滤器(bloom filter)会带来大量的计算开销，导致构造svetree结构的所需时间过长。
[0010]
因此，现有支持密文数据的范围检索结果完备性验证的方法，存在着验证数据结构的构造过程的计算与存储开销高昂的缺陷。目前尚缺乏一种高效的支持亿级规模数据集的密文范围检索结果完备性验证的方法。


技术实现要素：

[0011]
发明目的：本发明的目的是提供一种构建密文范围检索结果完备性验证数据结构的方法及系统，支持大规模数据集上的密文范围检索结果的完备性验证，同时降低验证数据结构的构造计算开销。
[0012]
技术方案：本发明提供了一种构建密文范围检索结果完备性验证数据结构的方法及系统，包含以下步骤：
[0013]
(1)从数据集所有者处获取数据集，对数据集中的每条记录赋予唯一且不重复的编号；
[0014]
(2)获取数据集中每个可检索维度取值的全局最大值和全局最小值，从数据集中采样部分数据记录构成采样数据集，根据采样数据集在各可检索维度上的取值以及该维度的全局最大值和全局最小值，计算各可检索维度的分位数数组，分位数数组包含了可搜索维度中的多个分位数；
[0015]
(3)对于数据集中的每条记录，将记录各维度的取值x归一化到[0,1]范围之间；对于记录的每一个可检索维度的取值x，根据相应维度的分位数数组，计算x所处于的分位数区间，如果x的取值在分位数数组中a％分位数与b％分位数范围之间，则将x归一化到[a/
100％,b/100％]范围之间，并用归一化后的值替换取值x，从而得到归一化数据集；
[0016]
(4)根据归一化数据集，通过迭代搜索合适的立方体编码系统层次数l，在第l轮迭代中，将整个数据值域空间平均划分为2
dl
个立方体单元，其中d是数据集可检索维度数量；根据立方体单元取值范围与归一化的数据记录取值的包含关系，将数据记录分配到相应的立方体单元中；如果立方体单元所包含记录数量的最大值小于等于指定阈值，则迭代过程停止，此时的迭代轮数即为立方体编码系统层次数；
[0017]
(5)对于归一化数据集中的每一条记录，根据该记录在各个立方体层次上所属的立方体单元，生成立方体编码集合；
[0018]
(6)对归一化数据集中的数据记录按该数据记录在最后一个立方体层次的立方体编码进行分组，将具有相同立方体编码的记录分为一组，为每一组记录构造立方格，记录的立方体编码构成立方格的键，每一组的记录内容构成立方格的值，对立方格的值进行加密，形成加密的立方格索引；
[0019]
(7)根据加密的立方格索引，构造k叉树结构，k为任意大于等于2的正整数，k叉树中的每个节点有至多k个子节点，k叉树的叶节点数量与立方格数量相同，每一个叶节点对应一个不同的立方格；
[0020]
(8)为k叉树的每个树节点附加一个布隆过滤器，对于每个树节点，将该树节点所覆盖的叶节点对应的立方格的所有立方体编码插入到布隆过滤器中；
[0021]
(9)为k叉树中的每个树节点生成节点哈希签名，节点哈希签名与该树节点的布隆过滤器的内容、该树节点的所有子节点的节点哈希签名有关；
[0022]
(10)加密的立方格索引、k叉树和立方体编码系统层次数共同构成了该数据集的用于密文范围检索结果完备性验证的验证数据结构，将验证数据结构上传至云数据库；同时将验证数据结构的摘要信息共享至客户，客户进行校验及查询。
[0023]
进一步的，步骤(3)中在将一条记录进行归一化时，对于该记录的每一个可检索维度的取值x，在该维度的分位数数组q中查找满足条件q[y]≤x≤q[y+1]的最小数组下标y，计算下标y在分位数数组中对应的分位数为和其中|q|是分位数数组q包含的元素数量，根据公式计算x的归一化值norm(x)，归一化后的值norm(x)的取值范围在[0,1]之间。
[0024]
进一步的，步骤(5)中为记录生成立方体编码时，为每个立方体层次中的所有立方体生成唯一的编号，记录的立方体编码与立方体层次数以及记录在该层次所属的立方体编号相关。
[0025]
进一步的，步骤(7)中构造k叉树的过程采用自底层，即叶节点所在层向上逐层构造的方式，对于某一层的树节点，以k个为一组分组，为每组节点创建一个新的树节点，这组节点均是新创建的树节点的子节点，逐层构造树节点直到某一层中只有一个树节点为止。
[0026]
本发明对应提供一种构建密文范围检索结果完备性验证数据结构的系统，包含多维数据集模块、归一化模块、迭代搜索模块、加密模块、构建验证数据结构模块；
[0027]
多维数据集模块用以从数据集所有者处获取数据集，并从数据集中进行采样形成采样数据集，根据采样数据集计算各可检索维度的分位数数组；
[0028]
归一化模块用以利用分位数数组将数据记录的取值范围归一化到[0,1]范围之间；
[0029]
迭代搜索模块用以通过迭代搜索合适的立方体编码系统层次数；
[0030]
加密模块用以通过立方体编码系统讲数据记录分配到不同的立方体单元中，并对属于同一立方体单元的记录利用密钥进行加密，生成立方格索引；
[0031]
构建验证数据结构模块用以根据立方格索引中的每个立方格作为多叉树的树节点，自底向上逐层构建多叉树，形成完整的验证数据结构。
[0032]
有益效果：本发明与现有技术相比，其显著优点是：通过对数据记录的值进行归一化的过程使得数据记录在值域空间中的分布更加均衡，从而降低立方体编码系统的层次数，并使得树节点布隆过滤器所需要被插入的编码数量降低，最终使得构造过程中的计算开销与计算功耗降低。同时，通过允许以k叉树作为验证数据结构的基础结构，相比采用平衡二叉树的svetree验证数据结构，当k＝4时，本发明所述方法产生的k叉树的高度，即树节点的层次数仅为平衡二叉树的一半，能够减少构造过程中接近50％的计算开销。根据立方体单元创建k叉树的叶节点，叶节点数量与立方体单元的数量相同，通过选取合适的立方体单元所包含记录数量的最大值阈值，立方体单元的数量可显著低于数据集中的记录数量，从而使k叉树的树节点数量低于svetree验证结构中平衡二叉树的树节点数量，大幅降低验证数据结构构造的计算开销与存储开销，为计算功耗的降低提供了支持。
附图说明
[0033]
图1是现有技术中检索完整性验证框架的交互流程图；
[0034]
图2是现有技术中示例数据集；
[0035]
图3是现有技术中示例数据集下数据记录在值域空间的分布图；
[0036]
图4是本发明中归一化后示例数据集；
[0037]
图5是本发明中归一化后示例数据集下数据记录在值域空间的分布图；
[0038]
图6是本发明中归一化示例数据集构造的四叉树结构示意图；
[0039]
图7是本发明与现有技术构造验证数据结构耗时比较图；
[0040]
图8是本发明构建密文范围检索结果完备性验证数据结构的流程图。
具体实施方式
[0041]
以下结合附图对本发明的具体实施方式进行说明。
[0042]
实施例
[0043]
本发明提供的一种构建密文范围检索结果完备性验证数据结构的方法，降低了验证数据结构构造过程的计算开销与空间开销，解决了现有方法在处理大规模数据集时计算时间与空间开销高昂所带来的性能问题。请参阅图3所示，以图3中现有技术下，数据集d以及该数据集记录在二维值域空间内的分布情况为例，该数据集包含10条记录，每条记录有两个可检索维度x和y。系统超参数设置为采样率r＝0.7、分位数数量q＝5、树节点宽度k＝4、每个立方体单元包含记录数最大值阈值u＝2、立方体编码系统的最大层数l＝25。
[0044]
请参阅图8所示，本发明所述的构建密文范围检索结果完备性验证数据结构的方法，包含以下步骤：
[0045]
(1)从数据所有者处获取数据集，对数据集中的每条记录赋予唯一且不重复的编号。
[0046]
对数据集中的记录从0开始连续编号；该数据集共有10条记录，依次从0编号到9，编号结果如图2所示。
[0047]
(2)获取数据集中每个可检索维度取值的全局最大值和全局最小值，从数据集中采样部分数据记录构成采样数据集，根据采样数据集在各可检索维度上的取值以及该维度的全局最大值和全局最小值，计算各可检索维度的分位数数组，分位数数组包含了可搜索维度中的多个分位数。
[0048]
遍历数据集中的每条记录，获得示例数据集在每个可检索维度上的最小值是《1,10》(其中维度x的最小值是min1＝1、y的最小值是min2＝10)，两个可检索维度的最大值是《19,170》(其中维度x的最大值max1＝19、维度y的最大值max2＝170)。
[0049]
根据采样率r＝0.7对数据集中的记录进行随机采样；因为数据集包含10条记录，所以随机采样出7条数据记录，在本例中假设编号为0、1、2、3、4、6、9的记录被采样，构成采样数据集d
′
，采样数据集包含的记录在图2中以灰色底色标出。
[0050]
对于可检索维度x，获取采样数据集中维度x上的取值，形成该维度的值数组v
x
＝[6.5,7.5,6,7,8,12,16]，并将该维度的最小值1和最大值19加入到v
x
中，使v
x
＝[6.5,7.5,6,7,8,12,16,1,19]；对于可检索维度y，根据采样数据集在该维度上的取值，形成该维度的值数组vy＝[140,145,120,110,125,70,30]，将该维度的最小值10和最大值170加入到值数组中，使vy＝[140,145,120,110,125,70,30,10,170]。
[0051]
对每个维度的值数组vi中的所有元素按照递增顺序进行排序；获取值数组包含的元素数量n，根据分位数数量参数q，从值数组vi的第1个元素开始选取，每隔个元素选取一次，直到选取到值数组vi的最后一个元素；值数组vi中被选取到的元素构成了该维度的分位数数组qi；如果值数组的最后一个元素不在分位数数组中，则将值数组的最后一个元素添加到分位数数组的最后。
[0052]
对于可检索维度x，对该维度值数组v
x
中的所有元素按照递增顺序进行排序，得到v
x
＝[1,6,6.5,7,7.5,8,12,16,19]，值数组包含的元素数量n＝9，根据系统超参数q＝5，从值数组v
x
的第一个元素开始选取，每隔个元素(即2个元素)选取一次，直到选取到最后一个元素，依次选取值数组中第1、3、5、7、9个元素(即1、6.5、7.5、12、19)，值数组v
x
中被选取到的元素构成了分位数数组q
x
＝[1,6.5,7.5,12,19]；对于可检索维度y，对值数组vy中的所有元素按照递增顺序进行排序，得到vy＝[10,30，70，110,120,125,140,145，170]，值数组vy包含的元素数量n＝9，根据系统超参数q＝5，每个2个元素选取一次。选取vy中第1、3、5、7、9个元素，被选取到的元素构成了该维度的分位数数组qy＝[10,70,120,140,170]。
[0053]
(3)对于数据集中的每条记录，将记录各维度的取值x归一化到[0，1]范围之间；对于记录的每一个可检索维度的取值x，根据相应维度的分位数数组，计算x所处于的分位数区间，如果x的取值在分位数数组中a％分位数与b％分位数范围之间，则将x归一化到[a/100％,b/100％]范围之间，并用归一化后的值替换取值x，从而得到归一化数据集。
[0054]
在将一条记录进行归一化时，对于该记录的每一个可检索维度的取值x，在该维度的分位数数组q中查找满足条件q[y]≤x≤q[y+1]的最小数组下标y，计算下标y在分位数数
组中对应的分位数为和其中|q|是分位数数组q包含的元素数量，根据公式计算x的归一化值norm(x)，归一化后的值norm(x)的取值范围在[0,1]之间。
[0055]
对于数据集中每一个记录的处理过程是相同的，下面以编号为0的记录为例说明；对于该记录的可检索维度x的取值6.5，在分位数数组q
x
中查找出符合条件q
x
[y]≤6.5≤q
x
[y+1]的最小的数组下标y为1，对应q
x
[1]为6.5和q
x
[2]为7.5，计算分位数数组中对应的分位数是根据以下公式计算可检索维度x的取值6.5归一化值归一化值用归一化的值0.25替换数据记录中的原取值6.5；对于该记录的可检索维度y的取值140，在分位数数组中查找出符合条件的最小数组下标y＝3，计算所得分位数a＝75％、b＝100％，根据公式计算出归一化值使用0.75替换原记录中可检索维度y的取值；经过步骤(6)之后，编号为0的记录在维度x和y的取值分别是0.25和0.75；图2中所示示例数据集的所有记录经过本步骤的操作之后，得到的归一化数据集，如图4所示。请参阅图5所示，归一化数据集的数据记录在值域空间中的分布情况更加均匀。
[0056]
(4)根据归一化数据集，通过迭代搜索合适的立方体编码系统层次数l，在第l轮迭代中，将整个数据值域空间平均划分为2
dl
个立方体单元，其中d是数据集可检索维度数量；根据立方体单元取值范围与归一化的数据记录取值的包含关系，将数据记录分配到相应的立方体单元中；如果立方体单元所包含记录数量的最大值小于等于指定阈值，则迭代过程停止，此时的迭代轮数即为立方体编码系统层次数。
[0057]
根据图3中所示的归一化数据集，第一轮迭代过程从层次数l＝1开始，迭代搜索合适的立方体编码层次数；对于第一轮迭代，l的值为1，将每个可检索维度在[0,1]的区间上平均划分为2个子区间，其中第一个子区间覆盖[0,0.5)范围，第二个子区间覆盖[0.5,1.0]范围，数据集的两个可检索维度(d＝2)的子区间将整个数据值域空间平均划分为4个立方体单元，其中第一个立方体单元覆盖了维度x的子区间[0,0.5)与维度y的子区间[0,0.5)，第二个立方体单元覆盖了维度x的子区间[0.5,1.0]和维度y的子区间[0,0.5)，第三个立方体单元覆盖了维度x的子区间[0,0.5)和维度y的子区间[0.5,1.0]，第四个立方体单元覆盖了维度x的子区间[0.5,1.0]和维度y的子区间[0.5,1.0]；将归一化之后的数据集中的每一条记录，按照各可检索维度的取值分配到对应的立方体单元中，以编号为0的记录为例，该记录在维度x和y的取值分别是0.25和0.75，其落入第三个立方体单元所覆盖的子区间，因此该记录将被分配到第三个立方体单元中；统计所有立方体单元被分配到的记录数量，本实施例中第一个立方体单元被分配到2条记录、第二个立方体单元被分配到3条记录、第三个立方体单元被分配到2条记录、第四个立方体单元被分配到3条记录，因此最大值x＝3；比较x(本实施例中为3)和每个立方体单元包含记录数最大值阈值u(本实施例中为2)，因为x＞u，不满足迭代停止条件。
[0058]
第二轮迭代中层次数l＝2，将每个可检索维度在[0,1]的区间上平均划分为4个子
区间，4个子区间所覆盖的范围分别是[0,0.25)、[0.25,0.5)、[0.5,0.75)、[0.75,1.0]；两个可检索维度将值域空间平均划分为16个立方体单元，如图5所示；将归一化数据集的数据记录分配到各立方体单元中，统计每个立方体单元中被分配到的记录数量，获得的最大值x＝2；比较最大值x和每个立方体单元包含记录数最大值阈值u，因为x≤u，满足迭代停止条件，迭代停止；将迭代停止时的层次数l＝2作为立方体编码系统的层次数参数附加在验证数据结构中。
[0059]
(5)对于归一化数据集中的每一条记录，根据该记录在各个立方体层次上所属的立方体单元，生成立方体编码集合。
[0060]
为层次i中的所有立方体单元赋予一个从0到2
di-1之间的序号(其中d是可检索维度数量)，序号赋予方法对所有记录保持一致。根据记录r在各可检索维度上的取值，计算出该记录在各层次i中所对应的立方体单元，根据立方体单元的序号i，利用密钥sk
′
计算哈希函数值hmac(sk
′
,i||i)(其中||是拼接操作符)，该哈希函数值即为记录r在立方体层次i中的相应的立方体编码c
r,i
。
[0061]
对于归一化数据集中的每条记录生成立方体编码集合的方式是相同，下面以编号为0的记录(简称记录0)的生成过程为例说明；对立方体层次1中的所有立方体单元赋予从0到3之间的序号，该序号根据步骤(4)中所述的立方体单元的枚举顺序确定，记录0在立方体层次1中属于第三个立方体，因此立方体单元的序号i＝2，利用密钥sk
′
计算哈希函数值hmac(sk
′
,1||2)，哈希函数值即为记录0在立方体层次1的立方体编码c
0,1
；为立方体层次2中的所有立方体单元赋予从0到15之间的序号，记录0在立方体层次2中所属立方体单元的序号i＝13，因此采用哈希函数值hmac(sk
′
,2||13)作为记录0在立方体层次2的立方体编码c
0,2
；根据两个层次的立方体编码，记录0的立方体编码集合是{hmac(sk
′
,1||2),hmac(sk
′
,2||13)}。
[0062]
(6)对归一化数据集中的数据记录按该数据记录在最后一个立方体层次的立方体编码进行分组，将具有相同立方体编码的记录分为一组，为每一组记录构造立方格，记录的立方体编码构成立方格的键，每一组的记录内容构成立方格的值，对立方格的值进行加密，形成加密的立方格索引。
[0063]
立方格索引由若干立方格(cube cell)构成，立方格是一个键值对，分组中任一记录的立方体编码集合构成了该键值对的键(key)部分，属于该分组的所有记录的内容构成了键值对的值(value)部分，键值对的值部分利用密钥sk加密，形成加密后的立方格；所有加密后的立方格构成了加密的立方格索引；每一个立方格均对应立方体编码层次l中的一个立方体单元，而每个立方体单元又对应数据值域空间中的一片连续区域，所有属于同一立方格的记录在值域空间内互相靠近。
[0064]
因为立方体层次数l等于2，因此根据归一化数据集记录在立方体编码层次2上对应的立方体编码进行分组，具有相同立方体编码的记录分配到同一组，在本例中编号为8、9的两条记录同属于一个分组，其他记录各自属于独立的分组，一共9个分组；以编号为8、9的两条记录所属的分组为例，该分组对应一个立方格，该立方格是一个键值对，键部分是编号为8的记录的立方体编码集合{hmac(sk
′
,1||1),hmac(sk
′
,2||3)}，值部分是编号为8、9的两条记录内容(在本例中即为记录编号与两个维度x和y的取值)；键值对的值部分用密钥sk配合aes256算法进行加密，从而形成加密后的立方格；本实施例中的所有9个加密后的立方
格构成立方格索引，将9个立方格进行从0到8连续编号，本例中包含编号为8、9两条记录的立方格的编号是1。
[0065]
(7)根据加密的立方格索引，构造k叉树结构，k为任意大于等于2的正整数，k叉树中的每个节点有至多k个子节点，k叉树的叶节点数量与立方格数量相同，每一个叶节点对应一个不同的立方格。
[0066]
在本实施例中，树节点宽度超参数k＝4，因此本步骤构建四叉树，立方格索引中的9个立方格对应四叉树的9个叶节点，如图6中所示四叉树中编号为0到8的树节点即为叶节点，每个叶节点对应一个立方格索引中的立方格，其中编号为1的叶节点对应于编号为1的立方格；从叶节点所在树层次1(最底层)出发，对于最该层中的9个树节点，以4个节点为一组进行分组，其中编号为0到3的树节点分为一组(简称树节点0到树节点3的分组)、编号为4到7的树节点分为另一组，编号为8的树节点单独一组；在本实施例中为树节点0到树节点3的分组创建一个新的树节点，新的树节点的编号为9(简称树节点9)，树节点0到树节点3均是新创建的树节点9的子节点；为其他两个分组创建树节点10和树节点11；编号为9、10、11的树节点构成了树层次2；再从树层次2出发，以4个节点为一组进行分组，共得到一个分组，为该分组创建一个编号为12的树节点，构成树层次3；因为树层次3只包含1个树节点，停止四叉树的构造过程；此时编号为12的树节点即为四叉树的根节点。
[0067]
(8)为k叉树的每个树节点附加一个布隆过滤器(bloom filter)，对于每个树节点，将该树节点所覆盖的叶节点对应的立方格的所有立方体编码插入到布隆过滤器中。
[0068]
对于k叉树中的每个树节点n，递归搜索该树节点的所有子孙节点，并提取出子孙节点中的所有叶节点，这些叶节点即为被树节点n所覆盖的叶节点；对于被树节点n所覆盖的每一个叶节点，将叶节点对应的立方格的立方体编码集合(即立方体格键值对的键部分)中的所有编码插入到树节点的bloom filter中。
[0069]
请参阅图6所示，四叉树的每个树节点附加一个布隆过滤器；向每个树节点的布隆过滤器中插入立方体编码的过程相同，下面以编号为9的树节点(简称树节点9)为例说明；树节点9的所有子孙节点包括编号为0到3的四个树节点；因为这四个子孙节点均为叶节点，因此这些节点是被树节点9所覆盖的叶节点；对于被树节点9所覆盖的每一个叶节点的插入过程类似，下面以插入编号为1的叶节点的过程为例说明，将该叶节点对应的立方格(即编号为1的立方格)的立方体编码集合{hmac(sk
′
,1||1),hmac(sk
′
,2||3)}中的两个编码hmac(sk
′
,1||1)与hmac(sk
′
,2||3)插入到树节点9的布隆过滤器中。
[0070]
(9)为k叉树中的每个树节点生成节点哈希签名，节点哈希签名与该树节点的布隆过滤器的内容、该树节点的所有子节点的节点哈希签名有关。
[0071]
利用hmac机制根据树节点的bloom filter的内容bl以及密钥sk
′
生成bloom filter的哈希签名sig
bl
＝hmac(sk
′
,bl)；再次应用hmac机制，根据树节点的bloom filter的哈希签名sig
bl
、树节点的所有子节点的节点哈希签名、密钥sk
′
生成当前树节点的节点哈希签名sign＝hmac(sk
′
,sig
bl
||sig
c1
||sig
c2
||
…
||sig
ck
)，其中||是拼接操作符，sig
c1
、sig
c2
、
…
、sig
ck
是该树节点的k个子节点的节点哈希签名。
[0072]
对每个树节点附加节点哈希签名的方式相同，下面以编号为9的树节点(简称树节点9)的生成过程为例说明；将树节点9的布隆过滤器中的比特数组当作布隆过滤器的内容bl，根据密钥sk
′
，利用hmac机制计算哈希值hmac(sk
′
,bl)，该哈希值存储为布隆过滤器的
哈希签名sig
bl
；根据sig
bl
以及树节点9的四个子节点(即编号为0到3的树节点)的节点哈希签名sig0、sig1、sig2、sig3，计算公式sig9＝hmac(sk
′
,sig
bl
||sig0||sig1||sig2||sig3)，sig9即为树节点9的节点哈希签名，其中||是拼接操作。
[0073]
(10)加密的立方格索引、k叉树和立方体编码系统层次数共同构成了该数据集的用于密文范围检索结果完备性验证的验证数据结构，将验证数据结构上传至云数据库；同时将验证数据结构的摘要信息共享至客户，客户进行校验及查询。
[0074]
本实施例中获得的加密的立方格索引、四叉树、立方体编码系统层次数l＝2构成验证数据结构，这些内容将被存储到文件中并上传给服务提供商(通常是云数据库)；四叉树的根节点的节点哈希签名、立方体编码系统层次数l＝2、数据集中每个可检索维度的分位数数组q
x
和qy、密钥sk和sk
′
将被存储到另一个文件中，通过安全私密的方式传输给客户。
[0075]
为测试本发明提出的方法的性能，采用foursquare签到数据集、us wild fire事件数据集、gowalla社交网络签到数据集作为输入，测量了本发明提出的方法构造验证数据结构的构造耗时；作为比较，采用文献“wu s,li q,li g,et al.servedb:secure,verifiable,and efficient range queries on outsourced database[c/ol]//2019ieee 35th international conference on data engineering(icde).2019:626-637.”中所述的svetree验证数据结构的构造方法作为参考方法，同时测量了参考方法的构造耗时。请参阅图7所示，实验结果显示本发明提出的方法的构造耗时显著低于参考方法的构造耗时，能够有效提升验证数据结构的构造效率。

技术特征：
1.一种构建密文范围检索结果完备性验证数据结构的方法，其特征在于，包含以下步骤：(1)从数据集所有者处获取数据集，对数据集中的每条记录赋予唯一且不重复的编号；(2)获取数据集中每个可检索维度取值的全局最大值和全局最小值，从数据集中采样部分数据记录构成采样数据集，根据采样数据集在各可检索维度上的取值以及该维度的全局最大值和全局最小值，计算各可检索维度的分位数数组，分位数数组包含了可搜索维度中的多个分位数；(3)对于数据集中的每条记录，将记录各维度的取值x归一化到[0,1]范围之间；对于记录的每一个可检索维度的取值x，根据相应维度的分位数数组，计算x所处于的分位数区间，如果x的取值在分位数数组中a％分位数与b％分位数范围之间，则将x归一化到[a/100％,b/100％]范围之间，并用归一化后的值替换取值x，从而得到归一化数据集；(4)根据归一化数据集，通过迭代搜索合适的立方体编码系统层次数l，在第l轮迭代中，将整个数据值域空间平均划分为2
dl
个立方体单元，其中d是数据集可检索维度数量；根据立方体单元取值范围与归一化的数据记录取值的包含关系，将数据记录分配到相应的立方体单元中；如果立方体单元所包含记录数量的最大值小于等于指定阈值，则迭代过程停止，此时的迭代轮数即为立方体编码系统层次数；(5)对于归一化数据集中的每一条记录，根据该记录在各个立方体层次上所属的立方体单元，生成立方体编码集合；(6)对归一化数据集中的数据记录按该数据记录在最后一个立方体层次的立方体编码进行分组，将具有相同立方体编码的记录分为一组，为每一组记录构造立方格，记录的立方体编码构成立方格的键，每一组的记录内容构成立方格的值，对立方格的值进行加密，形成加密的立方格索引；(7)根据加密的立方格索引，构造k叉树结构，k为任意大于等于2的正整数，k叉树中的每个节点有至多k个子节点，k叉树的叶节点数量与立方格数量相同，每一个叶节点对应一个不同的立方格；(8)为k叉树的每个树节点附加一个布隆过滤器，对于每个树节点，将该树节点所覆盖的叶节点对应的立方格的所有立方体编码插入到布隆过滤器中；(9)为k叉树中的每个树节点生成节点哈希签名，节点哈希签名与该树节点的布隆过滤器的内容、该树节点的所有子节点的节点哈希签名有关；(10)加密的立方格索引、k叉树和立方体编码系统层次数共同构成了该数据集的用于密文范围检索结果完备性验证的验证数据结构，将该验证数据结构上传至云数据库；同时将验证数据结构的摘要信息共享至客户，客户进行校验及查询。2.根据权利要求1所述的构建密文范围检索结果完备性验证数据结构的方法，其特征在于，步骤(3)中在将一条记录进行归一化时，对于该记录的每一个可检索维度的取值x，在该维度的分位数数组q中查找满足条件q[y]≤x≤q[y+1]的最小数组下标y，计算下标y在分位数数组中对应的分位数为和其中|q|是分位数数组q包含的元素数量，根据公式计算x的归一化值norm(x)，归一化
后的值norm(x)的取值范围在[0,1]之间。3.根据权利要求1所述的构建密文范围检索结果完备性验证数据结构的方法，其特征在于，步骤(5)中为记录生成立方体编码时，为每个立方体层次中的所有立方体生成唯一的编号，记录的立方体编码与立方体层次数以及记录在该层次所属的立方体编号相关。4.根据权利要求1所述的构建密文范围检索结果完备性验证数据结构的方法，其特征在于，步骤(7)中构造k叉树的过程采用自底层，即叶节点所在层向上逐层构造的方式，对于某一层的树节点，以k个为一组分组，为每组节点创建一个新的树节点，这组节点均是新创建的树节点的子节点，逐层构造树节点直到某一层中只有一个树节点为止。5.一种构建密文范围检索结果完备性验证数据结构的系统，其特征在于，包含多维数据集模块、归一化模块、迭代搜索模块、加密模块、构建验证数据结构模块；多维数据集模块用以从数据集所有者处获取数据集，并从数据集中进行采样形成采样数据集，根据采样数据集计算各可检索维度的分位数数组；归一化模块用以利用分位数数组将数据记录的取值范围归一化到[0,1]范围之间；迭代搜索模块用以通过迭代搜索合适的立方体编码系统层次数；加密模块用以通过立方体编码系统将数据记录分配到不同的立方体单元中，并对属于同一立方体单元的记录利用密钥进行加密，生成立方格索引；构建验证数据结构模块用以根据立方格索引中的每个立方格作为多叉树的树节点，自底向上逐层构建多叉树，形成完整的验证数据结构。6.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至权利要求4中任意一项所述方法的步骤。7.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至权利要求4中任意一项所述的方法的步骤。

技术总结
本发明公开了一种构建密文范围检索结果完备性验证数据结构的方法及系统，根据采样的数据记录计算各可检索维度的分位数数组；利用分位数数组将数据记录的取值范围归一化到[0,1]的区间；计算立方体编码系统所需的层次数；利用立方体编码系统将数据记录分配到不同的立方体单元中，对属于同一立方体单元的记录利用密钥进行加密，生成立方格索引；构建基于多叉树结构的验证数据结构，以立方格索引中的每个立方格作为多叉树的叶节点，以自底向上的方式逐层构建多叉树，形成完整的验证数据结构。以较小的计算与存储开销构建出能用于密文范围检索结果完备性验证所需的验证数据结构，解决现有方法计算开销过高、难以处理大规模数据集的问题。集的问题。集的问题。


技术研发人员：王肇康 潘佳辉 周璐 季曹枞 张仲辉 宋雨欣
受保护的技术使用者：南京航空航天大学
技术研发日：2023.03.23
技术公布日：2023/7/26