SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Yael Tauman Kalai; Alex Lombardi; Vinod Vaikuntanathan

Paper 2022/1409

SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Yael Tauman Kalai, Microsoft Research, Massachusetts Institute of Technology

Alex Lombardi, Simons Institute, University of California, Berkeley

Vinod Vaikuntanathan, Massachusetts Institute of Technology

Abstract

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. We obtain our result by showing how to instantiate the Fiat-Shamir heuristic, under DDH, for a variant of the Goldwasser-Kalai-Rothblum (GKR) interactive proof system. Our new technical contributions are (1) giving a circuit family for finding roots of cubic polynomials over a special family of characteristic fields (Healy-Viola, STACS '06) and (2) constructing a variant of the GKR protocol whose invocations of the sumcheck protocol (Lund-Fortnow-Karloff-Nisan, STOC '90) only involve degree polynomials over said fields. Along the way, since we can instantiate Fiat-Shamir for certain variants of the sumcheck protocol, we also show the existence of (sub-exponentially) computationally hard problems in the complexity class , assuming the sub-exponential hardness of DDH. Previous hardness results all required either bilinear maps or the learning with errors assumption.

Note: Fixed typos. Added funding information.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: SNARGs PPAD Fiat-Shamir Transform
Contact author(s): yael @ microsoft com
alexlombardi @ alum mit edu
vinodv @ mit edu
History: 2022-10-26: last of 2 revisions; 2022-10-18: received; See all versions
Short URL: https://ia.cr/2022/1409
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1409,
      author = {Yael Tauman Kalai and Alex Lombardi and Vinod Vaikuntanathan},
      title = {{SNARGs} and {PPAD} Hardness from the Decisional Diffie-Hellman Assumption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1409},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1409}
}