Compressing Proofs of k-Out-Of-n Partial Knowledge

In a proof of partial knowledge, introduced by Cramer, Damgard 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. Their solution combines Sigma-protocol theory and linear 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 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 with logarithmic (in n) communication, instead of linear as prior work. However, their method takes explicit advantage of k=1 and does not generalize to k>1. Alternatively, an indirect approach for solving the considered problem is by translating the k-out-of-n relation into a circuit and then applying communication-efficient circuit ZK. For k=1 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 logarithmic communication and for general k and n, without requiring any generic circuit ZK machinery. Our solution puts forward a novel extension of the compressed Sigma-protocol theory (CRYPTO 2020), which we then utilize to compress a new Sigma-protocol for proving knowledge of k-out-of-n DL's down to logarithmic size. The latter Sigma-protocol is inspired by the CRYPTO 1994 approach, but a careful re-design of the original protocol is necessary for the compression technique to apply. Interestingly, even for k=1 and general n our approach improves prior 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.