You are looking at a specific version 20200621:173728 of this paper. See the latest version.

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, Damgard 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 transactions systems in general. In this paper we focus on the discrete logarithms (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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Partial Proofs of 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.