SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

ePrint Report: SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

We construct succinct non-interactive arguments (SNARGs) for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard. This is the first construction of such SNARGs from a Diffie-Hellman assumption. Our SNARG is also unambiguous: for every (true) statement $x$, it is computationally hard to find any accepting proof for $x$ other than the proof produced by the prescribed prover strategy. …

diffie eprint report hellman