Libert B., Nguyen K., Tan B.H.M., Wang H. (2019) Zero-Knowledge Elementary Databases with More Expressive Queries. In: Lin D., Sako K. (eds) Public-Key Cryptography โ PKC 2019. PKC 2019. Lecture Notes in Computer Science, vol 11442. Springer, Cham
Abstract:
Zero-knowledge elementary databases (ZK-EDBs) are cryptographic schemes that allow a prover to commit to a set ๐ฃ of key-value pairs so as to be able to prove statements such as โx belongs to the support of ๐ฃ and ๐ฃ(๐ฅ)=๐ฆโ or โx is not in the support of ๐ฃโ. Importantly, proofs should leak no information beyond the proven statement and even the size of ๐ฃ should remain private. Chase et al. (Eurocryptโ05) showed that ZK-EDBs are implied by a special flavor of non-interactive commitment, called mercurial commitment, which enables efficient instantiations based on standard number theoretic assumptions. On the other hand, the resulting ZK-EDBs are only known to support proofs for simple statements like (non-)membership and value assignments. In this paper, we show that mercurial commitments actually enable significantly richer queries. We show that, modulo an additional security property met by all known efficient constructions, they actually enable range queries over keys and values โ even for ranges of super-polynomial size โ as well as membership/non-membership queries over the space of values. Beyond that, we exploit the range queries to realize richer queries such as ๐-nearest neighbors and revealing the ๐ smallest or largest records within a given range. In addition, we provide a new realization of trapdoor mercurial commitment from standard lattice assumptions, thus obtaining the most expressive quantum-safe ZK-EDB construction so far.
License type:
PublisherCopyrights
Funding Info:
Singapore Ministry of Education under Research Grant MOE2016-T2-2-014(S); BPI-France RISQ (P141580); EU Horizon 2020 Project PROMETHEUS; Gopalakrishnan โ NTU Presidential Post-doctoral Fellowship 2018;National Research Foundation, Prime Ministerโs Office, Singapore - Strategic Capability Research Centres Funding Initiative