Paper 2025/941 Original: eprint.iacr.org/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, particularly in critical applications like zk-bridges and zkVMs that require verifying standard cryptographic primitives. 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.