Compressing proofs of k-out-of-n partial knowledge

In an (honest-verifier) zero-knowledge proof of partial knowledge, introduced by Cramer, Damgård and Schoenmakers (CRYPTO 1994), a prover knowing witnesses for some k-subset of n given public statements can convince the verifier of this claim without revealing which k-subset.

The accompanying solution cleverly combines Σ -protocol theory and arithmetic secret sharing, and achieves linear communication complexity for general k,n. Especially the ``one-out-of-n'' case k=1 has seen myriad applications during the last decades, e.g., in electronic voting, ring signatures, and confidential transaction systems in general.

In this paper we focus on the discrete logarithm (DL) setting, where the prover claims knowledge of DLs of k -out-of-n given elements. Groth and Kohlweiss (EUROCRYPT 2015) have shown how to solve the special case k=1 %, yet arbitrary~n, with {\em logarithmic} (in n) communication, instead of linear as prior work. However, their method %, which is original, takes explicit advantage of k=1 and does not generalize to k>1 without losing all advantage over prior work. Alternatively, an {\em indirect} approach for solving the considered problem is by translating the k-out-of-n relation into a circuit and then applying recent advances in communication-efficient circuit ZK. Indeed, for the k=1 case this approach has been highly optimized, e.g., in ZCash.

Our main contribution is a new, simple honest-verifier zero-knowledge proof protocol for proving knowledge of k out of n DLs with {\em logarithmic} communication and {\em for general k and n}, without requiring any generic circuit ZK machinery. Our approach deploys a novel twist on {\em compressed} Σ-trotocol theory (CRYPTO 2020) that we then utilize to compress a carefully chosen adaptation of the CRYPTO 1994 approach down to logarithmic size. Interestingly, {\em even for k=1 and general n } our approach improves prior {\em direct} approaches as it reduces prover complexity without increasing the communication complexity. Besides the conceptual simplicity, we also identify regimes of practical relevance where our approach achieves asymptotic and concrete improvements, e.g., in proof size and prover complexity, over the generic approach based on circuit-ZK.

Finally, we show various extensions and generalizations of our core result. For instance, we extend our protocol to proofs of partial knowledge of Pedersen (vector) commitment openings, and/or to include a proof that the witness satisfies some additional constraint, and we show how to extend our results to non-threshold access structures.