Page 248 - 《软件学报》2021年第12期

3912 Journal of Software 软件学报 Vol.32, No.12, December 2021

因此在本节中不做对比.本节主要对比了本方案和 CVDB 方案、MVDB 方案及不进行全委托计算的方案
(without full delegation scheme)分别在预处理阶段、查询阶段和验证阶段的计算复杂度.其中,不进行全委托计
算的方案是指将本方案中由云服务器和数据拥有者交互生成验证密钥的过程由数据拥有者独立完成,即数据
拥有者独立计算验证密钥,而其他步骤不改变所形成的方案.由于插值操作、双线性映射和指数运算的计算开
销较大,因此忽略其他的运算,仅对比 3 种方案中的插值操作开销、双线性映射开销和指数运算开销,结果见表
3.在表 3 中,A,Interplt,Pairing,Exp 分别代表数据库中的数据集大小、插值操作的开销、双线性映射的开销以及
指数运算的开销.
Table 3 Comparison of computation cost
表 3 计算复杂度对比

实体 阶段 CVDB [18] MVDB [24] Without full PVDFD
delegation scheme 算法 开销
KeyGen 6Exp+Interplt
数据 2 + A 3 + A 4 A +3A+2Exp 3AExp+Interplt VKrec 2AExp
2
拥有者 预处理 2 Exp
总计 (2A+6)Exp+Interplt
授权用户 验证 1Exp+4Pairing 2Exp+4Pairing (A+1)Exp+3Pairing Verify (A+1)Exp+3Pairing
2
VKeval (4A +4A)Exp
2
2
云服务器 查询 (A-1)Exp (A-1)Exp A Exp Query A Exp
2
总计 (5A +4A)Exp
PVDFD 方案在预处理阶段,数据拥有者首先需要将数据库进行插值操作,并执行 6 次指数运算生成 Mexp
协议中 6 个隐藏的对;其次执行 VKrec 算法,执行 2A次指数运算以恢复验证密钥.因此,预处理阶段数据拥有者共
需(2A+6)次指数运算和一次插值操作.若不进行全委托计算,在本地执行全部的密钥生成操作则需要进行一次
插值操作及 3A次指数运算.而 CVDB 方案基于向量承诺实现,MVDB 方案基于向量承诺和布隆过滤器实现,二者
2
在预处理阶段所需代价均为 O(A ).昂贵的平方量级的指数运算操作远远超出了数据拥有者的计算能力,尤其是
当数据库中的数据集较大时,其开销是不可接受的.显然,本文的 PVDFD 方案在预处理阶段的工作量最低,证明
了全委托方案的优越性.而在用户验证阶段,CVDB 方案和 MVDB 方案的开销较小,为常量级;本方案和不进行
全委托的方案的开销均要执行与数据库大小呈线性量级的指数运算,但线性量级的开销是用户可以接受的.
CVDB 方案和 MVDB 方案虽然在验证过程中开销较小,但在预处理阶段开销过大,使其仍无法实际应用.此外,
由于云服务器可以认为是拥有海量计算资源的实体,拥有强大的计算能力.在 PVDFD 方案中,云服务器执行的
任务量最大,是对其强大计算能力的充分利用.CVDB 方案、MVDB 方案和不进行全委托计算的方案对云服务
器的利用较小,不能使其充分发挥作用以减小数据拥有者本地的开销.

5.3 效率分析
本节通过实验对比分析了本方案与 CVDB 方案、MVDB 方案及不进行全委托计算(without FD scheme,即
第 5.2 节所述数据拥有者独立计算验证密钥形成的方案)这 3 种方案在预处理阶段、验证密钥生成过程、验证
阶段和查询阶段的开销.实验采用 PBC 库实现双线性群的初始化,采用 NTL 库实现数据库的插值操作.运行实
验程序的计算机配置为:Intel(R) Core(TM) i7-6700 CPU@3.40GHz 3.41GHz 主频的处理器和 8GB 内存.
1) 比较本方案与 CVDB 方案、MVDB 方案及不进行全委托计算的方案在预处理阶段的时间开销.
预处理阶段包括初始化操作和密钥生成操作.实验结果如图 2 所示,其中,横坐标表示外包数据库中的数据
集大小,纵坐标表示 3 种方案在预处理阶段的执行时间.实验结果表明:本方案和不进行全委托计算的方案在预
处理阶段时间开销较低;且当数据集越大时,两方案的时间开销越接近.这是由于数据集越大,数据库插值的时
间则越长,指数运算的时间可以被忽略.而 MVDB 方案和 CVDB 方案的时间开销均远远高于二者,在数据集大小
为 10 000 时的开销甚至达到了约 100 000s.其原因是 MVDB 方案和 CVDB 方案在预处理阶段需要过于昂贵的
平方量级的指数运算操作,另两方案则只需线性量级的指数运算即可完成.当数据集较大时,MVDB 方案和