International Association
for Cryptologic Research

Sigma protocols are one of the most common and efficient zero-knowledge proofs (ZKPs). Over the decades, a large number of efficient Sigma protocols are proposed, yet few works pay attention to the common design principal. In this work, we propose a generic framework of Sigma protocols for algebraic statements from verifiable secret sharing (VSS) schemes. Our framework provides a general and unified approach to understanding Sigma protocols for proving knowledge of openings of algebraic commitments. It not only neatly explains the classic protocols such as Schnorr, Guillou–Quisquater and Okamoto protocols, but also leads to new Sigma protocols that were not previously known.

Furthermore, we show an application of our framework in designing ZKPs for composite statements, which contain both algebraic and non-algebraic statements. We give a generic construction of ZKPs for composite statements by combining Sigma protocols from VSS and ZKPs following MPC-in-the-head paradigm seamlessly via a technique of witness sharing reusing. Our construction has advantages of requiring no trusted setup, being public-coin and having a fast prover runtime. By instantiating our construction using Ligero++ (Bhadauria et al., CCS 2020), we obtain a new ZK protocol for composite statements, which achieves a new balance between running time and the proof size, thus resolving the open problem left by Backes et al. (PKC 2019). Concretely, the proof size is polylogarithmic to the circuit size and the number of public-key operations that both the prover and the verifier require is independent to the circuit size.