International Association
for Cryptologic Research

Zero-knowledge elementary databases (ZK-EDBs) enable a prover to commit a database ${D}$ of key-value pairs and later prove that ``${x}$ belongs to the support of ${D}$ and ${D}(x)=v$'' or that ``${x}$ does not belong to the support of ${D}$,'' without revealing any extra knowledge (including the size of ${D}$). Recently, Libert et al. (PKC 2019) introduced zero-knowledge expressive elementary databases (ZK-EEDBs) that support richer queries, e.g., range queries over the keys and values.

In this paper, we introduce a new notion called function queriable ZK-EDBs, where the ZK-EDB prover can convincingly answer the query that ``Send all records ${(x,v)}$ in ${{D}}$ satisfying $f(x,v)=1$ for any Boolean circuit $f$,'' without revealing any extra knowledge (including the size of ${D}$).

To construct function queriable ZK-EDBs, we introduce a new variation of zero-knowledge sets (ZKS) which supports verifiable set operations, and present a construction based on groups of unknown order. By transforming the Boolean circuit over databases into the set operation circuit/formula over sets, we present a construction of function queriable ZK-EDBs from standard ZK-EDBs and ZKS supporting verifiable set operations.