CryptoDB
Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
| Authors: |
|
|---|---|
| Download: |
|
| 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
}