ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (3): 521-532.doi: 10.7544/issn1000-1239.2019.20170839

• 信息安全 • 上一篇    下一篇



  1. (东北大学软件学院 沈阳 110169) (
  • 出版日期: 2019-03-01
  • 基金资助: 

Publicly Verifiable Database Model with Full Operations Based on Bilinear Map

Wang Qiang, Zhou Fucai, Xuan Pengkai, Wu Qiyu   

  1. (Software College, Northeastern University, Shenyang 110169)
  • Online: 2019-03-01

摘要: 为解决现有可验证外包数据库方案存在的查询类型较单一、更新和验证代价较高、数据膨胀率较大、效率较低难以应用于实际等问题,提出了一个基于双线性映射的支持全操作的公共可验证外包数据库(publicly verifiable database model with full operations based on bilinear map, BMPVDB)模型.给出了该模型的架构及交互流程,并对该模型进行了形式化定义,针对该模型的安全需求给出了该模型的安全性定义.利用双线性映射构造了一个高效且支持全操作的公共可验证外包数据库方案,并对该方案中各算法进行了详细描述,证明了该方案的安全性,其安全性可归约为q-BSDH(bilinear q-strong Diffie-Hellman)和VBDHE(variant of bilinear Diffie-Hellman exponent)难题.最后将该方案与现有方案进行了对比,理论与实验分析表明:该方案功能更全面(各类集合操作、函数查询、嵌套查询)、更新与验证代价更低为常数级、数据膨胀率更低、效率更高可应用于实际.此外,该方案的验证与更新无需私钥参与,拥有公钥和摘要的用户均可进行验证与更新,实现了公共可验证和公共可更新.

关键词: 双线性映射, 外包数据库, 全操作, 公共可验证, 动态更新

Abstract: The existing verifiable outsourced database schemes only support some kind of tailored queries with low efficiency and large data expanding rate. Besides, the overheads of verification and update of these schemes are unacceptable. As a result, they cannot be applied into practice. To resolve these problem, we propose a novel primitive called publicly verifiable outsourced database with full operations based on bilinear map. We present a system model and security model of our scheme. Based on bilinear map, we construct a publicly verifiable outsourced database scheme with full operations, and design each algorithm in detail. We present the rigorous security proof under q-BSDH assumption and VBDHE assumption. Finally, we make a comparison with other state of art schemes in two directions: functionality and performance. The theoretical analysis and simulation confirm that our scheme is more functional, efficient and practical. Furthermore, verification and update phases do not require data owner’s private key, and any client owning public key and digest can verify the correctness of query and update database. Therefore, our scheme supports public verification and public update.

Key words: bilinear map, outsourced database, full operation, public verification, dynamic update