可有效更新的低存储开销公共可验证数据库方案  

Publicly Verifiable Databases Scheme with Efficient Updates and Low Storage Overhead

作　　者：吴淇毓 周福才[1] 王强 李宇溪[1] Wu Qiyu;Zhou Fucai;Wang Qiang;Li Yuxi(Software College,Northeastern University,Shenyang 110169)

机构地区：[1]东北大学软件学院,沈阳110169

出　　处：《计算机研究与发展》2018年第8期1800-1808,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61772127);中央高校基本科研业务费专项资金项目(N171704005)~~

摘　　要：围绕外包数据的计算效率和查询结果完整性问题,展开对可验证数据库的研究,提出了一个可有效更新的低存储开销公共可验证数据库模型.给出其算法形式化定义及安全模型,并利用素数阶双线性群构造了一个具体的可有效更新的低存储开销公共可验证数据库方案.该方案允许资源受限的客户将大型数据库外包到专业数据库服务提供商,不仅可以从其查询或更新数据记录,而且能够检测并验证所查询数据的完整性.方案的安全性可以规约为Square-CDH问题假设.与已有方案相比,该方案基于素数阶双线性群,提高了计算效率,并在初始化阶段构造了独立于数据库大小的公共参数,减小了客户的存储开销.同时,方案验证无需私钥参与,从而实现了公共可验证.此外,该方案不仅支持对数据进行修改,还支持对数据的插入及删除操作.性能分析表明,该方案满足客户查询、更新和验证等操作开销独立于数据库大小.Aiming at the computational efficiency of outsourcing database and the completeness of query results, we propose a publicly verifiable database model with efficient updates and low storage overhead. Its description and security model are formalized, besides, a specific publicly verifiable database scheme with efficient updates and low storage overhead using the prime order bilinear groups is also proposed. Our scheme allows a resource-constrained client to securely outsource a very large database to a professional database service provider so that it could later retrieve or update a database record and verify the integrity of the retrieved data. The security of our scheme can be reduced to the hardness of the Square-CDH problem. Compared with the existing schemes, our scheme improves the computational efficiency by using the prime order bilinear groups. We construct the constant size parameter which is independent of the database that reduces the storage overhead of the client. In the meanwhile, the verification phase in the scheme does not require the data owner’s private key so it can be publicly verifiable. In addition, our scheme not only supports the modification of data, but also supports the insertion and deletion on data. The performance analysis shows that the cost of query, verification and update is independent of the database size.

关 键 词：可验证数据库 公共可验证 外包存储 常量大小 双线性映射 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]