Publicly Verifiable Databases with All Efficient Updating Operations
The primitive of verifiable database (VDB) can enable a resource-limited client to securely outsource and update an encrypted database to an untrusted cloud server. Meanwhile, the client can detect any misbehavior of the server if the database has been tampered with. We argue that most of the existing VDB schemes can only support the updating operation of replacement, rather than other updating operations such as insertion and deletion. Recently, the first publicly verifiable VDB schemes that supports all updating operations was proposed based on the idea of hierarchical vector commitment. However, one disadvantage of this VDB scheme is that the computation/storage complexity increases linearly when the client continually inserts data records in the same index of the database. Thus, it remains an open problem how to construct an efficient (and publicly verifiable) VDB scheme that can support all updating operations. In this paper, we first introduce a new primitive called committed invertible Bloom filter and utilize it to propose a new publicly verifiable VDB scheme that supports all kinds of updating operations. Additionally, the proposed construction is efficient regardless of the manner of updating operations and thus provides an affirmative answer to the above open problem.
Branch: CSE Domain: Data Mining
Developed In: Java