Paper published in a book (Scientific congresses, symposiums and conference proceedings)
UC Updatable Databases and Applications
Damodaran, Aditya Shyam Shankar; Rial, Alfredo
2020In 12th International Conference on Cryptology
Peer reviewed


Full Text
Publisher postprint (521.43 kB)

All documents in ORBilu are protected by a user license.

Send to


Keywords :
Vector commitments; ZK proofs; universal composability
Abstract :
[en] We define an ideal functionality $\Functionality_{\UD}$ and a construction $\mathrm{\Pi_{\UD}}$ for an updatable database ($\UD$). $\UD$ is a two-party protocol between an updater and a reader. The updater sets the database and updates it at any time throughout the protocol execution. The reader computes zero-knowledge (ZK) proofs of knowledge of database entries. These proofs prove that a value is stored at a certain position in the database, without revealing the position or the value. (Non-)updatable databases are implicitly used as building block in priced oblivious transfer, privacy-preserving billing and other privacy-preserving protocols. Typically, in those protocols the updater signs each database entry, and the reader proves knowledge of a signature on a database entry. Updating the database requires a revocation mechanism to revoke signatures on outdated database entries. Our construction $\mathrm{\Pi_{\UD}}$ uses a non-hiding vector commitment (NHVC) scheme. The updater maps the database to a vector and commits to the database. This commitment can be updated efficiently at any time without needing a revocation mechanism. ZK proofs for reading a database entry have communication and amortized computation cost independent of the database size. Therefore, $\mathrm{\Pi_{\UD}}$ is suitable for large databases. We implement $\mathrm{\Pi_{\UD}}$ and our timings show that it is practical. In existing privacy-preserving protocols, a ZK proof of a database entry is intertwined with other tasks, e.g., proving further statements about the value read from the database or the position where it is stored. $\Functionality_{\UD}$ allows us to improve modularity in protocol design by separating those tasks. We show how to use $\Functionality_{\UD}$ as building block of a hybrid protocol along with other functionalities.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Disciplines :
Computer science
Author, co-author :
Damodaran, Aditya Shyam Shankar ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Rial, Alfredo ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
Language :
Title :
UC Updatable Databases and Applications
Publication date :
Event name :
Event date :
From 20-07-2020 to 22-07-2020
Audience :
Main work title :
12th International Conference on Cryptology
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
FnR Project :
FNR11650748 - Stateful Zero-knowledge, 2017 (01/03/2018-28/02/2021) - Alfredo Rial
Name of the research project :
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 17 April 2020


Number of views
266 (34 by Unilu)
Number of downloads
121 (21 by Unilu)

Scopus citations®
Scopus citations®
without self-citations


Similar publications

Contact ORBilu