UC Updatable Non-Hiding Committed Database with Efficient Zero-Knowledge Proofs

We define an ideal functionality $\Functionality_{\DB}$ and a protocol $\mathrm{\Pi_{\DB}}$ for an updatable non-hiding committed database ($\DB$). $\DB$ is described as the task of storing a database into a suitable data structure that allows you to efficiently prove in zero-knowledge (ZK) that a value is stored in the database at a certain position. The database is \emph{non-hiding} because both prover and verifier know its content. It is \emph{committed} in the sense that only ZK proofs about position-value pairs that are actually stored are possible. It is \emph{updatable} because its contents can be modified dynamically throughout the protocol execution.

The $\DB$ task is used implicitly as building block of privacy-preserving protocols for e-commerce, smart billing and access control. In those protocols, this task is intertwined with others. Our functionality $\Functionality_{\DB}$ allows us to study constructions for this task in isolation. Furthermore, it allows us to improve modularity in protocol design, by using $\Functionality_{\DB}$ as building block of those protocols along with functionalities for other tasks.

Our construction $\mathrm{\Pi_{\DB}}$ uses a non-hiding vector commitment (VC) scheme as building block. Thanks to the efficiency properties of non-hiding VC schemes, $\mathrm{\Pi_{\DB}}$ provides ZK proofs whose computation cost (after initialization) and whose size are both independent of the database size. Therefore, $\mathrm{\Pi_{\DB}}$ is suitable for large databases. Moreover, the database can be updated dynamically and very efficiently.