Cryptology ePrint Archive: Report 2020/753

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

Thomas Attema and Ronald Cramer and Serge Fehr

Abstract: In a zero-knowledge (ZK) proof of partial knowledge, introduced by Cramer, Damgård and Schoenmakers (CRYPTO 1994), a prover claiming knowledge of witnesses for some $k$-subset of $n$ given public statements can convince the verifier without revealing which $k$-subset. The accompanying dedicated solution based on secret sharing achieves linear communication complexity for general $k,n$ and for many natural classes of statements. Especially the case $k=1$ and $n=2$ (``one-out-of-two'') 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; the prover's claim pertains to knowledge of discrete logarithms of $k$-out-of-$n$ given elements from a group supporting DL-based cryptography. Groth and Kohlweiss (EUROCRYPT 2015) have shown how to solve the special case $k=1$ and general $n$ with logarithmic communication instead of linear. 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.

Our contributions are as follows. We show a solution with logarithmic communication for general $k,n$ instead of just $k=1$ and general $n$ from prior work. Applying the Fiat-Shamir transform renders a non-interactive logarithmic-size zero-knowledge proof. Our approach deploys a novel twist on a basic primitive from Compressed $\Sigma$-Protocol Theory (CRYPTO 2020) that we then utilize to compress a carefully chosen adaptation of the CRYPTO 1994 approach down to logarithmic size. Interestingly, even for $k=1$ and general $n$ our approach improves prior work as it reduces communication up to almost a factor $1/2$.

We also generalize this to proofs of partial knowledge about compact commitments of long vectors. Optionally, the prover may at the same time demonstrate his secret to satisfy some arbitrary given constraint. Finally, we also generalize from threshold to arbitrary access structures.

Category / Keywords: cryptographic protocols / Proofs of Partial Knowledge, One-out-of-Many, Compressed Sigma-Protocol Theory, Zero-Knowledge, Secure Algorithmics, Ring-Signatures

Date: received 19 Jun 2020, last revised 16 Jul 2020

Contact author: thomas attema at tno nl,cramer@cwi nl,serge fehr@cwi nl

Available format(s): PDF | BibTeX Citation

Note: Change log w.r.t. Version 1 - June 19, 2020: (a) minor editorial changes throughout, (b) elaborated on the alternative approach of constructing proofs of partial knowledge indirectly via circuit ZK protocols, and (c) removed the exact knowledge errors in several theorems (see [AC20a] for a discussion on knowledge errors).

Version: 20200716:113953 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]