At CRYPTO ’94, Cramer, Damgård, 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.
