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

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

随着信息技术的高速发展,智能手机等小型终端设备成为人们生活中不可或缺的一部分.然而,这些终端设
备受限于较弱的计算和存储能力,无法承受庞大的数据量所带来的昂贵代价.伴随着云计算 [1−3] 的高速发展,这
[4]
些弱计算能力的终端可以将数据外包给云服务提供商 管理,即用户将庞大的数据通过外包的形式让拥有强
大计算能力的云服务器来存储和计算.通过这种将数据外包的方式,用户可以随时随地发出查询请求,云服务器
则会根据不同的请求执行查询操作,并将结果返回给用户.因此,用户本地只需负责数据传输等简单操作即可,
[5]
使得其持有轻量级设备即可执行查询操作.然而,由于用户丧失了对数据的直接控制 ,云服务器可能会伪造查
询结果来减少响应时间和查询代价.这种资源租用的模式也带来了查询的安全性、正确性和隐私性等诸多问
题.在这种情况下,如何使得用户能够检测和验证查询结果的完整性,成为了亟待解决的问题.
[6]
针对上述问题,Benabbas 等人于 2011 年首次提出了可验证数据库(verifiable database,简称 VDB)的概念 ,
包括三方实体:数据拥有者、云服务器和用户.其中:数据拥有者持有数据库,并将其外包给云服务器存储;用户则
可根据索引对数据库进行查询.由于具有可验证性,当用户对索引进行查询时,云服务器返回查询结果和一个能
够验证结果完整性的证据.用户便可根据该证据来验证结果是否被篡改,即:得到查询结果的同时,又能验证其
完整性.而其中需要满足的一个关键条件是:用户查询验证的开销要远远小于其在本地执行查询计算的开销,否
则便失去了外包的意义.对于持有小型终端设备的数据拥有者而言,由于计算能力的限制,方案能实际应用的关
键是,其使用轻量级设备在可接受的时间内能完成协议中的步骤.在可验证数据库方案中,数据拥有者的工作量
主要由外包预处理阶段的开销构成,包括初始化和密钥生成算法.
近年来,国内外研究人员针对可验证数据库做了大量的研究 [7−25] ,其中的很多方案在预处理阶段的开销超
出了持有小型终端的数据拥有者的计算能力,以至于无法在现实中使用.如文献[18]利用向量承诺 [26] 的信息隐
藏性和位置绑定性构建了一个可验证数据库方案,但由于向量承诺所需开销较大,数据拥有者在预处理阶段要
2
执行 O(A )量级的指数运算才能实现初始化和密钥生成等操作,其中,A为数据库中数据集的大小.当数据库很庞
大时,这样的开销对于轻量级的设备而言是不可接受的.为解决这一问题,文献[19]提出了一种分摊模型,将昂贵
的预处理开销分摊到方案后面的查询步骤中,从而对每次查询而言“减小”其预处理阶段的开销.然而实际上,对
数据拥有者而言,分摊的方式并没有减少其在整个方案中的工作量.因此,分摊模型依然不满足数据拥有者的关
键要求.此外,在当前很多方案中,如文献[6,21],用户的验证过程需要私钥的参与,也就是说,只有持有私钥的用户
才能验证查询结果的完整性.而在实际场景中,用户可能希望通过代理来验证查询结果,公共可验证则恰好满足
此要求.在公共可验证的方案中,任何一个被数据拥有者授权,即持有验证密钥的用户均可以对外包数据库的查
询结果进行验证.综上,在实际的不可信云环境中,如何在实现外包数据库完整性验证的前提下,又能够降低数
据拥有者在预处理阶段的开销成为了关键,现有方案未能同时解决数据拥有者预处理开销大及公共可验证的
问题.
针对上述要求,本文提出了一个全委托的公共可验证的外包数据库(publicly verifiable outsourced database
with full delegation,简称 PVDFD)模型,该模型具有以下两个特点.
1) 数据拥有者预处理开销小.利用可验证外包模幂运算,将预处理阶段大量的模幂运算委托给云服务
器,使得数据拥有者与云服务器交互获得验证密钥的工作量小于自己生成验证密钥的工作量,同时保
证验证密钥的保密性.这里的全委托是指除了将数据库外包给云服务器来检索外,还将预处理阶段生
成验证密钥的部分运算交给云来完成;
2) 公共可验证.本方案支持公共可验证,即任何持有验证密钥的用户均可根据任意用户发送的查询请求
及云服务器返回的结果和证据进行验证.

1 相关知识

本文所用符号见表 1.