International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness

Authors:
Lisa Yang , MIT
Yael Tauman Kalai , Microsoft Research and MIT
Omer Paneth , Tel Aviv University
Download:
DOI: 10.1007/978-3-030-56877-1_23 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: In this work, we show the hardness of finding a Nash equilibrium, a \PPAD-complete problem, based on the quasi-polynomial hardness of the decisional assumption on groups with bilinear maps introduced by Kalai, Paneth and Yang [STOC 2019]. Towards this goal, we construct an {\em unambiguous} and {\em updatable} delegation scheme under this assumption for deterministic computations running in super-polynomial time and polynomial space. This delegation scheme, which is of independent interest, is publicly verifiable and non-interactive in the common reference string (CRS) model. It is {\em unambiguous} meaning that it is hard to compute two different proofs for the same statement. It is {\em updatable} meaning that given a proof for the statement that a Turing machine $M$ reaches configuration $\conf_T$ in $T$ steps, one can {\em efficiently} generate a proof for the statement that $M$ reaches configuration $\conf_{T+1}$ in $T+1$ steps.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30503,
  title={Delegation with Updatable Unambiguous Proofs and PPAD-Hardness},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56877-1_23},
  author={Lisa Yang and Yael Tauman Kalai and Omer Paneth},
  year=2020
}