Paper 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.
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).
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Proofs of Partial KnowledgeOne-out-of-ManyCompressed Sigma-Protocol TheoryZero-KnowledgeSecure AlgorithmicsRing-Signatures
- Contact author(s)
- thomas attema @ tno nl,cramer @ cwi nl,serge fehr @ cwi nl
- History
- 2021-03-09: last of 3 revisions
- 2020-06-21: received
- See all versions
- Short URL
- https://ia.cr/2020/753
- License
-
CC BY