Publicly verifiable databases with efficient insertion/deletion operations

The notion of verifiable database (VDB) enables a resource-constrained 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. Meanwhile, any tampering with the database by the server will be detected by the client. We argue that all existing VDB schemes can only support the updating operation called replacement. That is, the client can efficiently update a data record by assigning a new value. However, the proposed solutions are not applicable for other updating operations such as insertion and deletion. In this paper, we first propose a new VDB scheme that supports all updating operations of replacement, deletion, and insertion by incorporating the techniques of commitment binding and hierarchical commitment. Security evaluation shows that the proposed construction can achieve the desired security properties in the standard computational Diffie-Hellman assumption.