Paper 2023/1388

Sigma Protocols from Verifiable Secret Sharing and Their Applications

Min Zhang, School of Cyber Science and Technology, Shandong University
Yu Chen, School of Cyber Science and Technology, Shandong University
Chuanzhou Yao, School of Cyber Science and Technology, Shandong University
Zhichao Wang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Sigma protocols are one of the most common and efficient zero-knowledge proofs (ZKPs). Over the decades, a large number of 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. 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 non-interactive ZKPs for composite statements by combining Sigma protocols from VSS and ZKPs following MPC-in-the-head paradigm in a seamless way via a technique of \textit{witness sharing reusing}. Our construction has advantages of requiring no “glue” proofs for combining algebraic and non-algebraic statements. By instantiating our construction using Ligero++ (Bhadauria et al., CCS 2020) and designing an associated Sigma protocol from VSS, we obtain a concrete ZKP for composite statements which achieves a tradeoff between running time and proof size, thus resolving the open problem left by Backes et al. (PKC 2019).

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in ASIACRYPT 2023
Sigma protocolsVerifiable secret sharingComposite statementsMPC-in-the-head.
Contact author(s)
zm_min @ mail sdu edu cn
yuchen prc @ gmail com
2023-09-22: last of 2 revisions
2023-09-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Min Zhang and Yu Chen and Chuanzhou Yao and Zhichao Wang},
      title = {Sigma Protocols from Verifiable Secret Sharing and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1388},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.