Efficient proofs of knowledge for threshold relations
Published in ESORICS 22, 2022
Recommended citation: Avitabile, G., Botta, V., Friolo, D., & Visconti, I. (2022, September). Efficient proofs of knowledge for threshold relations. In European Symposium on Research in Computer Security (pp. 42-62). Cham: Springer Nature Switzerland. https://eprint.iacr.org/2022/746.pdf
Recently, there has been great interest towards constructing efficient zero-knowledge proofs for prac- tical 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 l statements. The main contribution of our work is an efficient and modular transformation that starting from a large class of Σ-protocols and a corresponding threshold relation R_k,l provides an efficient Σ-protocol for Rk,` with improved communication complexity w.r.t. prior results. Moreover, our transformation preserves statistical/perfect honest-verifier zero knowledge.
Recommended citation: Avitabile, G., Botta, V., Friolo, D., & Visconti, I. (2022, September). Efficient proofs of knowledge for threshold relations. In European Symposium on Research in Computer Security (pp. 42-62). Cham: Springer Nature Switzerland.