Paper 2022/746

Efficient Proofs of Knowledge for Threshold Relations

Gennaro Avitabile, DIEM, University of Salerno
Vincenzo Botta, DIEM, University of Salerno
Daniele Friolo, Sapienza University of Rome
Ivan Visconti, DIEM, University of Salerno
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
Creative Commons Attribution
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},
      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.