## CryptoDB

### Paper: Delegation with Updatable Unambiguous Proofs and PPAD-Hardness

Authors: Lisa Yang , MIT Yael Tauman Kalai , Microsoft Research and MIT Omer Paneth , Tel Aviv University DOI: 10.1007/978-3-030-56877-1_23 (login may be required) Search ePrint Search Google Slides CRYPTO 2020 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.
##### 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
}