We present zkExp (Zero-Knowledge Succinct Exponentiation Proofs), the first zero-knowledge proof system achieving asymptotically efficient bounds for batched exponentiation: O ~ ( k ℓ ) prover time, O ( 1 ) verification time, and constant-size (160–256 B) proofs. For statements y i = g x i ( i = 1 , … , k ) with private exponents x i , zkExp introduces four innovations to overcome long-standing scalability barriers: (1) trace-based square-and-multiply encoding, (2) lazy sumcheck for exponentiation constraints, (3) hybrid FFT decomposition reducing memory from O ( ℓ ) to O ( ℓ ) , and (4) sliding-window batching enabling single-proof aggregation via KZG commitments. The protocol is computationally sound under the ( q , ℓ ) -Generalized Diffie–Hellman Exponent (GDHE) assumption and achieves computational zero-knowledge in the random oracle model. Proofs remain 160–256 B regardless of parameter sizes, with constant verification (3.5 ms). For 4096-bit exponents, prover overhead is 16.3 × (dropping to 1.35 × in 1000-batch settings), while Ethereum verification costs ~ 267 k gas for 1000 exponentiations, 10 × cheaper than ECDSA, with memory consumption below 1.1 MB. zkExp is the first protocol to match theoretical lower bounds for exponentiation proofs while enabling practical deployment in zero-knowledge rollups, anonymous credentials, and on-chain threshold cryptography.
Deressa et al. (Mon,) studied this question.