Extending Groth16 for Disjunctive Statements

Xudong Zhu; Xinxuan Zhang; Xuyang Song; Yi Deng; Yuanju Wei; Liuyu Yang

Paper 2025/028

Extending Groth16 for Disjunctive Statements

Xudong Zhu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Xinxuan Zhang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Xuyang Song, Anoma

Yi Deng, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Yuanju Wei, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Liuyu Yang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Abstract

Two most common ways to design non-interactive zero knowledge (NIZK) proofs are based on Sigma ($\Sigma$)-protocols (an efficient way to prove algebraic statements) and zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) protocols (an efficient way to prove arithmetic statements). However, in the applications of cryptocurrencies such as privacy-preserving credentials, privacy-preserving audits, and blockchain-based voting systems, the zk-SNARKs for general statements are usually implemented with encryption, commitment, or other algebraic cryptographic schemes. Moreover, zk-SNARKs for many different arithmetic statements may also be required to be implemented together. Clearly, a typical solution is to extend the zk-SNARK circuit to include the code for algebraic part. However, complex cryptographic operations in the algebraic algorithms will significantly increase the circuit size, which leads to impractically large proving time and CRS size. Thus, we need a flexible enough proof system for composite statements including both algebraic and arithmetic statements. Unfortunately, while the conjunction of zk-SNARKs is relatively natural and numerous effective solutions are currently available (e.g. by utilizing the commit-and-prove technique), the disjunction of zk-SNARKs is rarely discussed in detail. In this paper, we mainly focus on the disjunctive statements of Groth16, and we propose a Groth16 variant---CompGroth16, which provides a framework for Groth16 to prove the disjunctive statements that consist of a mix of algebraic and arithmetic components. Specifically, we could directly combine CompGroth16 with $\Sigma$-protocol or even CompGroth16 with CompGroth16 just like the logical composition of $\Sigma$-protocols. From this, we can gain many good properties, such as broader expression, better prover's efficiency and shorter CRS. In addition, for the combination of CompGroth16 and $\Sigma$-protocol, we also present two representative application scenarios to demonstrate the practicality of our construction.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Zk-SNARK Sigma protocol Disjunctive statement Logical composition
Contact author(s): zhuxudong @ iie ac cn
zhangxinxuan @ iie ac cn
xuyangsong1012 @ gmail com
deng @ iie ac cn
weiyuanju @ iie ac cn
yangliuyu @ iie ac cn
History: 2025-01-08: approved; 2025-01-08: received; See all versions
Short URL: https://ia.cr/2025/028
License: CC BY

BibTeX

@misc{cryptoeprint:2025/028,
      author = {Xudong Zhu and Xinxuan Zhang and Xuyang Song and Yi Deng and Yuanju Wei and Liuyu Yang},
      title = {Extending Groth16 for Disjunctive Statements},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/028},
      year = {2025},
      url = {https://eprint.iacr.org/2025/028}
}