Paper 2020/753
Compressing Proofs of $k$OutOf$n$ Partial Knowledge
Thomas Attema, Ronald Cramer, and Serge Fehr
Abstract
In an (honestverifier) zeroknowledge 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 combines $\Sigma$protocol theory and linear secret sharing, and achieves linear communication complexity for general $k,n$. Especially the ``oneoutof$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$outof$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$ without losing all advantage over prior work. Alternatively, an indirect approach for solving the considered problem is by translating the $k$outof$n$ relation into a circuit and then applying recent advances in communicationefficient 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 honestverifier zeroknowledge 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$outof$n$ DL's down to logarithmic size. The latter $\Sigma$protocol is inspired by the CRYPTO 1994 approach, but a careful redesign 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 circuitZK. 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 nonthreshold access structures.
Note: Change log w.r.t. Version 3  October 21, 2020: (a) minor editorial changes, and (b) revised introduction of our techniques.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Proofs of Partial KnowledgeOneoutofManyCompressed SigmaProtocol TheoryZeroKnowledgeSecure AlgorithmicsRingSignatures
 Contact author(s)

thomas attema @ tno nl
cramer @ cwi nl
serge fehr @ cwi nl  History
 20210309: last of 3 revisions
 20200621: received
 See all versions
 Short URL
 https://ia.cr/2020/753
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/753, author = {Thomas Attema and Ronald Cramer and Serge Fehr}, title = {Compressing Proofs of $k$OutOf$n$ Partial Knowledge}, howpublished = {Cryptology ePrint Archive, Paper 2020/753}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/753}}, url = {https://eprint.iacr.org/2020/753} }