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

周搏洋 等:全委托的公共可验证的外包数据库方案 3913

CVDB 方案的时间开销是持有小型终端的数据拥有者所不能接受的.
2) 比较本方案和不进行全委托计算的方案生成验证密钥的时间开销.
实验结果如图 3 所示,其中,横坐标表示外包数据库中的数据集大小,纵坐标表示两种方案生成验证密钥的
执行时间.实验结果表明:两方案的执行时间几乎都与数据集大小呈线性关系,而本方案生成验证密钥所需时间
更低.由上文,要计算验证密钥中的σ DB 和{U j },不进行全委托计算的方案需要进行 3A次指数运算,A为数据库大
小.而本方案执行验证密钥恢复算法,进行 2A次指数运算即可求得验证密钥.因此,本方案的开销更小,尤其当数
据集大小较大时,优势更加明显.

Fig.2 Comparison of time cost in pre phase Fig.3 Comparison of time cost in VKEval phase
图 2 预处理阶段开销对比图 图 3 计算验证密钥的开销对比图

3) 比较本方案与 CVDB 方案、MVDB 方案及不进行全委托计算的方案在验证阶段的时间开销.
实验结果如图 4 所示,其中,横坐标表示外包数据库中的数据集大小,纵坐标表示 3 种方案在用户验证阶段
的执行时间.实验结果表明:随着数据集大小的增长,本方案和不进行全委托计算的方案所需的时间开销随之线
性增长;而 CVDB 方案和 MVDB 方案中验证操作的时间开销则为常量级,独立于数据集的大小.这是由于本方
案为了实现公共可验证性,使得用户执行线性量级的指数运算操作.但由图 4 中可看出:当数据集大小为 10 000
时,时间开销约为 14s,这对于用户而言是完全可以接受的.而 CVDB 方案和 MVDB 方案由于将大部分开销都放
在预处理阶段执行,因此在验证阶段开销较小;然而其在预处理操作中过于昂贵的开销,使其难以实际应用.
4) 比较本方案与 CVDB 方案、MVDB 方案及不进行全委托计算的方案在查询阶段的时间开销.
实验结果如图 5 所示,横坐标表示外包数据库中的数据集大小,纵坐标表示 3 种方案在云服务器查询阶段
的执行时间.实验结果表明:CVDB 方案和 MVDB 方案对云服务器的利用率最低,其次是不进行全委托计算的方
案,而本方案对云服务器的利用率最高.这是由于 CVDB 方案和 MVDB 方案将大部分的开销放在了预处理阶段,
数据拥有者执行昂贵的预处理操作,使得其查询和验证的开销较小.然而,云服务器的计算能力很强,数据拥有
者的计算能力却是有限的,仅仅使用云服务器进行数据库的查询操作,是对其计算能力的浪费.此外,持有小型
终端的数据拥有者执行如此昂贵的预处理开销是不现实的.因此,CVDB 和 MVDB 两方案没有利用好云服务器
的特性减小数据拥有者的开销.而不进行全委托的计算方案同样没有利用好云服务器的计算能力.本文把预处
理阶段全委托给云服务器计算,合理地利用了云服务器强大的计算能力,减少了数据拥有者在预处理阶段的时
间开销,虽然使得用户的验证开销略有增长,但该增长是在用户接受范围内的,这使得本方案更适于实际应用.