Paper 2022/1021
Practical StatisticallySound Proofs of Exponentiation in any Group
Abstract
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 proofsize only provide restricted soundness guarantees: Wesolowski's protocol (Journal of Cryptology 2020) is only computationallysound (i.e., it is an argument), whereas Pietrzak's protocol (ITCS 2019) is statisticallysound only in groups that come with the promise of not having any small subgroups. On the other hand, the only statisticallysound 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 proofsize  is as large as $\lambda$. In this work, we propose a statisticallysound 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 proofsize 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in CRYPTO 2022
 Keywords
 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  History
 20220919: revised
 20220807: received
 See all versions
 Short URL
 https://ia.cr/2022/1021
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1021, author = {Charlotte Hoffmann and Pavel Hubáček and Chethan Kamath and Karen Klein and Krzysztof Pietrzak}, title = {Practical StatisticallySound Proofs of Exponentiation in any Group}, howpublished = {Cryptology ePrint Archive, Paper 2022/1021}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1021}}, url = {https://eprint.iacr.org/2022/1021} }