周搏洋,陈春雨,王 强,周福才

1(东北大学 软件学院,辽宁 沈阳 110169)

2(中国科学院 沈阳自动化研究所,辽宁 沈阳 110016)

随着信息技术的高速发展,智能手机等小型终端设备成为人们生活中不可或缺的一部分.然而,这些终端设备受限于较弱的计算和存储能力,无法承受庞大的数据量所带来的昂贵代价.伴随着云计算[1-3]的高速发展,这些弱计算能力的终端可以将数据外包给云服务提供商[4]管理,即用户将庞大的数据通过外包的形式让拥有强大计算能力的云服务器来存储和计算.通过这种将数据外包的方式,用户可以随时随地发出查询请求,云服务器则会根据不同的请求执行查询操作,并将结果返回给用户.因此,用户本地只需负责数据传输等简单操作即可,使得其持有轻量级设备即可执行查询操作.然而,由于用户丧失了对数据的直接控制[5],云服务器可能会伪造查询结果来减少响应时间和查询代价.这种资源租用的模式也带来了查询的安全性、正确性和隐私性等诸多问题.在这种情况下,如何使得用户能够检测和验证查询结果的完整性,成为了亟待解决的问题.

针对上述问题,Benabbas 等人于2011 年首次提出了可验证数据库(verifiable database,简称VDB)的概念[6],包括三方实体:数据拥有者、云服务器和用户.其中:数据拥有者持有数据库,并将其外包给云服务器存储;用户则可根据索引对数据库进行查询.由于具有可验证性,当用户对索引进行查询时,云服务器返……