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)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2019/667}},
      url = {https://eprint.iacr.org/2019/667}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.