Publicly verifiable databases with efficient insertion/deletion operations



Publication Details

Miao, M., Wang, J., Ma, J. & Susilo, W. (2017). Publicly verifiable databases with efficient insertion/deletion operations. Journal of Computer and System Sciences, Online First 1-10.


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 insertionand 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.

Please refer to publisher version or contact your library.



Link to publisher version (DOI)