Paper 2022/1021

Practical Statistically-Sound Proofs of Exponentiation in any Group

Abstract

For a group $$ of unknown order, a *Proof of Exponentiation* (PoE) allows a prover to convince a verifier that a tuple $$ satisfies $$. 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 $$ bits of security, say $$, the number of repetitions required -- and hence the (multiplicative) overhead incurred in proof-size -- is as large as $$. In this work, we propose a statistically-sound PoE for arbitrary groups for the case where the exponent $$ is the product of all primes up to some bound $$. For such a structured exponent, we show that it suffices to run only $$ 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 $$ and $$ but different $$ and $$) can be batched by adding only a single element to the proof per additional statement.