Welcome to the resource topic for 2019/667
Title:
PPAD-Hardness via Iterated Squaring Modulo a Composite
Authors: Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, 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)
ePrint: https://eprint.iacr.org/2019/667
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .