Welcome to the resource topic for 2022/1021
Title:
Practical Statistically-Sound Proofs of Exponentiation in any Group
Authors: Charlotte Hoffmann, Pavel Hubáček, Chethan Kamath, Karen Klein, Krzysztof Pietrzak
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 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.
ePrint: https://eprint.iacr.org/2022/1021
Talk: https://www.youtube.com/watch?v=ZxaylVPpLr0
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/211/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .