Paper 2019/667
PPAD-Hardness 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 END-OF-LINE problem (which is PPAD-complete) 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 END-OF-LINE cannot be solved in $\text{poly}(n)$ time. We prove our result by reducing $f$ to (a variant of) the SINK-OF-VERIFIABLE-LINE problem, which is known to imply PPAD (and in fact CLS) hardness. The main building block of our reduction is a recently discovered interactive public-coin proof by Pietrzak for certifying $y=f(N,x,T)$, which can be made non-interactive using (an analogue of) the Fiat-Shamir 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 EquilibriumFiat-Shamir 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
- 2019-06-06: 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 = {{PPAD}-Hardness via Iterated Squaring Modulo a Composite}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/667}, year = {2019}, url = {https://eprint.iacr.org/2019/667} }