International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Sigma Protocols from Verifiable Secret Sharing and Their Applications

Authors:
Min Zhang , School of Cyber Science and Technology, Shandong University, Qingdao, China
Yu Chen , School of Cyber Science and Technology, Shandong University, Qingdao, China
Chuanzhou Yao , School of Cyber Science and Technology, Shandong University, Qingdao, China
Zhichao Wang , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: 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).
BibTeX
@inproceedings{asiacrypt-2023-33647,
  title={Sigma Protocols from Verifiable Secret Sharing and Their Applications},
  publisher={Springer-Verlag},
  author={Min Zhang and Yu Chen and Chuanzhou Yao and Zhichao Wang},
  year=2023
}