New Publicly Verifiable Databases Supporting Insertion Operation

The notion of verifiable database (VDB) enables a resource-constrained client to securely outsource a very large database to an untrusted server so that it could later retrieve a database record and update it by assigning a new value. Also, any attempt by the server to tamper with the data will be detected by the client. However, neither of the constructions [1], [4] seems to support the insertion operation. In this paper, we propose a new VDB scheme supporting the insertion operation besides replacement and delete operations in the bilinear pairing groups of prime order.