Paper 2022/746
Efficient Proofs of Knowledge for Threshold Relations
Abstract
Recently, there has been great interest towards constructing efficient zero-knowledge proofs for practical languages. In this work, we focus on proofs for threshold relations, in which the prover is required to prove knowledge of witnesses for $k$ out of $\ell$ statements. The main contribution of our work is an efficient and modular transformation that starting from a large class of $\Sigma$-protocols and a corresponding threshold relation $\mathcal{R}_\mathsf{k,\ell}$, provides an efficient $\Sigma$-protocol for $\mathcal{R}_\mathsf{k,\ell}$ with improved communication complexity w.r.t. prior results. Moreover, our transformation preserves statistical/perfect honest-verifier zero knowledge.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Σ-protocols communication complexity threshold ring signatures
- Contact author(s)
-
gavitabile @ unisa it
vbotta @ unisa it
friolo @ di uniroma1 it
visconti @ unisa it - History
- 2022-06-14: approved
- 2022-06-10: received
- See all versions
- Short URL
- https://ia.cr/2022/746
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/746,
author = {Gennaro Avitabile and Vincenzo Botta and Daniele Friolo and Ivan Visconti},
title = {Efficient Proofs of Knowledge for Threshold Relations},
howpublished = {Cryptology ePrint Archive, Paper 2022/746},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/746}},
url = {https://eprint.iacr.org/2022/746}
}
