Paper 2019/667
PPADHardness via Iterated Squaring Modulo a Composite
Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum
Abstract
We show that, relative to a random oracle, solving the ENDOFLINE problem (which is PPADcomplete) is no easier than computing the function \[f(N,x,T) = x^{2^T} \text{mod } N,\] where $N$ is an $n$bit RSA modulus, $x\in \mathbb{Z}_N^*$ and $T\in\mathbb{N}$. It was conjectured by Rivest, Shamir and Wagner, that, unless the factorization of $N$ is known, the fastest algorithm for computing $f$ consists of $\Omega(T)$ iterated squaring operations mod $N$. Under a milder assumption, namely that computing $f$ takes $n^{\omega(1)}$ time for some (possibly exponentially) large $T$, our construction of ENDOFLINE cannot be solved in $\text{poly}(n)$ time. We prove our result by reducing $f$ to (a variant of) the SINKOFVERIFIABLELINE problem, which is known to imply PPAD (and in fact CLS) hardness. The main building block of our reduction is a recently discovered interactive publiccoin proof by Pietrzak for certifying $y=f(N,x,T)$, which can be made noninteractive using (an analogue of) the FiatShamir heuristic. The value $y$ can be computed together with the proof in time $\text{poly}(n)\cdot T$, and the proof can be verified in time $\text{poly}(n) \cdot \text{log} T$. The key technical challenge in our setting is to provide a means by which the solution $y$ together with a proof can be computed in small incremental steps, while the correctness of each intermediate state of this computation can still be verified in time $\text{poly}(n, \text{log} T)$
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 TFNPPPADNash EquilibriumFiatShamir transformation
 Contact author(s)

achoud @ cs jhu edu
hubacek @ iuuk mff cuni cz
ckamath @ ist ac at
pietrzak @ ist ac at
alon rosen @ idc ac il
rothblum @ alum mit edu  History
 20190606: received
 Short URL
 https://ia.cr/2019/667
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/667, author = {Arka Rai Choudhuri and Pavel Hubacek and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum}, title = {PPADHardness via Iterated Squaring Modulo a Composite}, howpublished = {Cryptology ePrint Archive, Paper 2019/667}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/667}}, url = {https://eprint.iacr.org/2019/667} }