### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/746

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.