Paper 2022/1021

Practical Statistically-Sound Proofs of Exponentiation in any Group

Charlotte Hoffmann, IST Austria
Pavel Hubáček, Charles University
Chethan Kamath, Tel Aviv University
Karen Klein, ETH Zurich
Krzysztof Pietrzak, IST Austria

For a group $\mathbb{G}$ of unknown order, a *Proof of Exponentiation* (PoE) allows a prover to convince a verifier that a tuple $(y,x,q,T)\in \mathbb{G}^2\times\mathbb{N}^2$ satisfies $y=x^{q^T}$. PoEs have recently found exciting applications in constructions of verifiable delay functions and succinct arguments of knowledge. The current PoEs that are practical in terms of proof-size only provide restricted soundness guarantees: Wesolowski's protocol (Journal of Cryptology 2020) is only computationally-sound (i.e., it is an argument), whereas Pietrzak's protocol (ITCS 2019) is statistically-sound only in groups that come with the promise of not having any small subgroups. On the other hand, the only statistically-sound PoE in *arbitrary* groups of unknown order is due to Block et al. (CRYPTO 2021), and it can be seen as an elaborate parallel repetition of Pietrzak's PoE. Therefore, to achieve $\lambda$ bits of security, say $\lambda=80$, the number of repetitions required -- and hence the (multiplicative) overhead incurred in proof-size -- is as large as $\lambda$. In this work, we propose a statistically-sound PoE for arbitrary groups for the case where the exponent $q$ is the product of all primes up to some bound $B$. For such a structured exponent, we show that it suffices to run only $\lambda/\log(B)$ parallel instances of Pietrzak's PoE. This reduces the concrete proof-size compared to Block et al. by an order of magnitude. Furthermore, we show that in the known applications where PoEs are used as a building block such structured exponents are viable. Finally, we also discuss batching of our PoE, showing that many proofs (for the same $\mathbb{G}$ and $q$ but different $x$ and $T$) can be batched by adding only a single element to the proof per additional statement.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2022
Interactive protocol verifiable delay function SNARK
Contact author(s)
charlotte hoffmann @ ist ac at
hubacek @ iuuk mff cuni cz
ckamath @ protonmail com
karen klein @ inf ethz ch
pietrzak @ ist ac at
2022-09-19: revised
2022-08-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charlotte Hoffmann and Pavel Hubáček and Chethan Kamath and Karen Klein and Krzysztof Pietrzak},
      title = {Practical Statistically-Sound Proofs of Exponentiation in any Group},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1021},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.