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^{\ast }$ 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 $\mathrm{\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 $$ 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 $$, which can be made non-interactive using (an analogue of) the Fiat-Shamir heuristic. The value $$ can be computed together with the proof in time $$, and the proof can be verified in time $$. The key technical challenge in our setting is to provide a means by which the solution $$ 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 $$