Paper 2022/766
The Cost of Statistical Security in Interactive Proofs for Repeated Squaring
Abstract
In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element $x$, an integer $T$, and an RSA modulus $N$, it is hard to compute $x^{2^T} \mod N$or even decide whether $y\stackrel{?}{=}x^{2^T} \mod N$in parallel time less than the trivial approach of computing $T$ sequential squarings. This rise has been driven by efficient interactive proofs for repeated squaring, opening the door to more efficient constructions of verifiable delay functions, various secure computation primitives, and proof systems for more general languages. In this work, we study the complexity of statisticallysound interactive proofs for the repeated squaring relation. Technically, we consider interactive proofs where the prover sends at most $k \ge 0$ elements per round and the verifier performs generic group operations over the group $\mathbb{Z}_N^\star$. As our main contribution, we show that for any oneround proof with a randomized verifier (i.e., an MA proof) the verifier either runs in parallel time $\Omega(T/(k+1))$ with high probability, or is able to factor $N$ given the proof provided by the prover. This shows that either the prover essentially sends $p,q$ such that $N = p\cdot q$ (which is infeasible or undesirable in most applications), or a variant of Pietrzak's proof of repeated squaring (ITCS 2019) has optimal verifier complexity $O(T/(k+1))$. In particular, it is impossible to obtain a statisticallysound oneround proof of repeated squaring with efficiency on par with the computationallysound protocol of Wesolowski (EUROCRYPT 2019), with a generic group verifier. We further extend our oneround lower bound to a natural class of recursive (multiround) interactive proofs for repeated squaring.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Interactive ProofsRepeated SquaringLower Bounds
 Contact author(s)

cfreitag @ cs cornell edu
ilank @ cs huji ac il  History
 20220616: approved
 20220614: received
 See all versions
 Short URL
 https://ia.cr/2022/766
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/766, author = {Cody Freitag and Ilan Komargodski}, title = {The Cost of Statistical Security in Interactive Proofs for Repeated Squaring}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/766}, year = {2022}, url = {https://eprint.iacr.org/2022/766} }