Paper 2025/941
Proof of Exponentiation: Enhanced Prover Efficiency for Algebraic Statements
Abstract
Recent years have seen the widespread adoption of zkSNARKs constructed over small fields, including but not limited to, the Goldilocks field, small Mersenne prime fields, and tower of binary fields. Their appeal stems primarily from their efficacy in proving computations with small bit widths, which facilitates efficient proving of general computations and offers significant advantages, notably yielding remarkably fast proving efficiency for tasks such as proof of knowledge of hash preimages. Nevertheless, employing these SNARKs to prove algebraic statements (e.g., RSA, ECDSA signature verification) presents efficiency challenges. To address this problem, we first define a new circuit model: arithmetic circuits with additional \textit{exponentiation gates}. These gates serve as fundamental building blocks for establishing more intricate algebraic relations. Then we present a \textit{Hash-committed Commit-and-Prove (HCP)} framework to construct Non-interactive Zero-knowledge (NIZK) proofs for the satisfiability of these circuits. Specifically, when proving knowledge of group exponentiations in discrete logarithm hard groups and RSA groups, compared to verifying complex group exponentiations within SNARK circuits, our approach requires proving only more lightweight computations within the SNARK, such as zk-friendly hash functions (e.g., Poseidon hash function). The number of these lightweight computations depends solely on the security parameter. This differentiation leads to substantial speedups for the prover relative to direct SNARK methods, while maintaining competitive proof size and verification cost.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- zkSNARKSigma ProtocolAlgebraic Statement
- Contact author(s)
-
wuzhuo @ iie ac cn
qishi @ iie ac cn
zhangxinxuan @ iie ac cn
deng @ iie ac cn
me @ imlk top
whl383799 @ antgroup com - History
- 2025-05-24: revised
- 2025-05-23: received
- See all versions
- Short URL
- https://ia.cr/2025/941
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/941, author = {Zhuo Wu and Shi Qi and Xinxuan Zhang and Yi Deng and Kun Lai and Hailong Wang}, title = {Proof of Exponentiation: Enhanced Prover Efficiency for Algebraic Statements}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/941}, year = {2025}, url = {https://eprint.iacr.org/2025/941} }