Skip to Main content Skip to Navigation
Conference papers

Zero-Knowledge Elementary Databases with More Expressive Queries

Abstract : Zero-knowledge elementary databases (ZK-EDBs) are cryptographic schemes that allow a prover to commit to a set D of key-value pairs so as to be able to prove statements such as "x belongs to the support of D and D(x) = y" or "x is not in the support of D". Importantly , proofs should leak no information beyond the proven statement and even the size of D 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 in-stantiations 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 k-nearest neighbors and revealing the k smallest or largest records within a given range. In addition, we provide a new realization of trapdoor mercurial commitment from standard lattice asssumptions, thus obtaining the most expressive quantum-safe ZK-EDB construction so far.
Document type :
Conference papers
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/hal-02151645
Contributor : Benoit Libert <>
Submitted on : Sunday, June 9, 2019 - 1:02:31 PM
Last modification on : Wednesday, November 20, 2019 - 2:29:32 AM

File

zk-eedb.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Benoît Libert, Khoa Nguyen, Benjamin Tan, Huaxiong Wang. Zero-Knowledge Elementary Databases with More Expressive Queries. PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Apr 2019, Beijing, China. pp.255-285, ⟨10.1007/978-3-030-17253-4_9⟩. ⟨hal-02151645⟩

Share

Metrics

Record views

215

Files downloads

583