Concise UC Zero-Knowledge Proofs for Oblivious Updatable Databases

We propose an ideal functionality $\mathcal{F}_{\mathrm{C}\mathrm{D}}$ and a construction $\Pi_{\mathrm{C}\mathrm{D}}$ for oblivious and updatable committed databases. $\mathcal{F}_{\mathrm{C}\mathrm{D}}$ allows a prover $\mathcal{P}$ to read, write, and update values in a database and to prove to a verifier $\mathcal{V}$ in zero-knowledge (ZK) that a value is read from or written into a certain position. The following properties must hold: (1) values stored in the database remain hidden from $\mathcal{V}$; (2) a value read from a certain position is equal to the value previously written into that position; (3) (obliviousness) both the value read or written and its position remain hidden from $\mathcal{V}$.$\Pi_{\mathrm{C}\mathrm{D}}$ is based on vector commitments. After the initialization phase, the cost of read and write operations is independent of the database size, outperforming other techniques that achieve cost sublinear in the dataset size for prover and/or verifier. Therefore, our construction is especially appealing for large datasets. In existing “commit-and-prove” two-party protocols, the task of maintaining a committed database between $\mathcal{P}$ and $\mathcal{V}$ and reading and writing values into it is not separated from the task of proving statements about the values read or written. $\mathcal{F}_{\mathrm{C}\mathrm{D}}$ allows us to improve modularity in protocol design by separating those tasks. In comparison to simply using a commitment scheme to maintain a committed database, $\mathcal{F}_{\mathrm{C}\mathrm{D}}$ allows $\mathcal{P}$ to hide efficiently the positions read or written from $\mathcal{V}$. Thanks to this property, we design protocols for e.g. privacy-preserving e-commerce and location-based services where $\mathcal{V}$ gathers aggregate statistics about the statements that $\mathcal{P}$ proves in ZK.