Paper 2025/941

Proof of Exponentiation: Enhanced Prover Efficiency for Algebraic Statements

Zhuo Wu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Shi Qi, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, 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, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Yi Deng, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Kun Lai
Hailong Wang, Digital Technologies, Ant Group
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.