Welcome to the resource topic for
**2024/1488**

**Title:**

Compact Proofs of Partial Knowledge for Overlapping CNF Formulae

**Authors:**
Gennaro Avitabile, Vincenzo Botta, Daniele Friolo, Daniele Venturi, Ivan Visconti

**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 k 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.

**ePrint:**
https://eprint.iacr.org/2024/1488

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .