Efficient Verifiable Databases With Insertion/Deletion Operations From Delegating Polynomial Functions
Efficient Verifiable Databases With Insertion/Deletion Operations From Delegating Polynomial Functions
复制标题
DOI：
10.1109/tifs.2017.2758746
复制
发表时间：
2018-02
影响因子：
6.8
通讯作者：
Meixia Miao;Jianfeng Ma;Xinyi Huang;Qian Wang
中科院分区：
文献类型：
--
作者：
Meixia Miao;Jianfeng Ma;Xinyi Huang;Qian Wang
可更新的可验证数据库（VDB）的概念使资源有限的客户端能够安全地将非常大的数据库外包给不受信任的服务器，并且客户端稍后可以检索数据库记录并有效地更新它。此外，客户端还可以检测服务器篡改数据记录的任何不当行为。据我们所知，现有的 VDB 方案无法同时有效地支持所有更新操作（即插入、删除和替换）。在本文中，我们引入了一种称为 Merkle 和哈希树的新原语，然后使用它来设计一种新的 VDB 方案，该方案支持委托多项式函数的所有更新操作。我们的方案的一个有趣的特性是，所有更新操作都可以被视为 Benabbas-Gennaro-Vahlis VDB 方案中“替换”的特例。因此，我们的构建对于实际应用来说非常有效。此外，我们正式证明，当子组成员假设成立时，所提出的构造可以实现所需的安全属性。
The notion of verifiable database with updates (VDB) enables a resource-limited client to securely outsource a very large database to an untrusted server, and the client could later retrieve a database record and update it efficiently. In addition, the client could detect any misbehavior of tampering with the data record by the server. To the best of our knowledge, the existing VDB schemes cannot efficiently support all updating operations (i.e., insertion, deletion, and replacement) simultaneously. In this paper, we introduce a new primitive called Merkle sum hash tree and then use it to design a new VDB scheme that supports for all updating operations from delegating polynomial functions. An interesting property of our scheme is that all updating operations can be viewed as a special case of “replacement” in the Benabbas–Gennaro–Vahlis VDB scheme. Thus, our construction is very efficient for real-world applications. Furthermore, we formally prove that the proposed construction can achieve the desired security properties when the subgroup member assumption holds.