Cryptology ePrint Archive: Report 2019/667

PPAD-Hardness via Iterated Squaring Modulo a Composite

Arka Rai Choudhuri and Pavel Hubacek and Chethan Kamath and Krzysztof Pietrzak and 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)$

Category / Keywords: foundations / TFNP, PPAD, Nash Equilibrium, Fiat-Shamir transformation

Date: received 5 Jun 2019, last revised 5 Jun 2019

Contact author: achoud at 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

Available format(s): PDF | BibTeX Citation

Version: 20190606:113506 (All versions of this report)

Short URL: ia.cr/2019/667


[ Cryptology ePrint archive ]