Paper 2024/1488

Compact Proofs of Partial Knowledge for Overlapping CNF Formulae

Abstract

At CRYPTO '94, Cramer, Damgaard, and Schoenmakers introduced a general technique for constructing honest-verifier zero-knowledge proofs of partial knowledge (PPK), where a prover Alice wants to prove to a verifier Bob she knows $\tau$ witnesses for $\tau$ claims out of $k$ claims without revealing the indices of those $\tau$ claims. Their solution starts from a base honest-verifier zero-knowledge proof of knowledge $\Sigma$ and requires to run in parallel $k$ execution of the base protocol, giving a complexity of $O(k\gamma(\Sigma))$, where $\gamma(\Sigma)$ is the communication complexity of the base protocol. However, modern practical scenarios require communication-efficient zero-knowledge proofs tailored to handle partial knowledge in specific application-dependent formats. In this paper we propose a technique to compose a large class of $\Sigma$-protocols for atomic statements into $\Sigma$-protocols for PPK over formulae in conjunctive normal form (CNF) that overlap, in the sense that there is a common subset of literals among all clauses of the formula. In such formulae, the statement is expressed as a conjunction of $m$ clauses, each of which consists of a disjunction of $k$ literals (i.e., each literal is an atomic statement) and $\ell$ literals are shared among clauses. The prover, for a threshold parameter $\tau \le k$, proves knowledge of at least $\tau$ witnesses for $\tau$ distinct literals in each clause. At the core of our protocol, there is a new technique to compose $\Sigma$-protocols for regular CNF relations (i.e., when $ \tau=1$) that exploits the overlap among clauses and that we then generalize to formulae where $\tau>1$ providing improvements over state-of-the-art constructions.