International Association for Cryptologic Research

International Association
for Cryptologic Research


SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Yael Tauman Kalai , Microsoft Research and MIT
Alex Lombardi , Simons Institute and UC Berkeley
Vinod Vaikuntanathan , MIT
DOI: 10.1007/978-3-031-30617-4_16 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
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 TC0 circuit family for finding roots of cubic polynomials over a special family of characteristic 2 fields (Healy-Viola, STACS 2006) and (2) constructing a variant of the GKR protocol whose invocations of the sumcheck protocol (Lund-Fortnow-Karloff-Nisan, STOC 1990) only involve degree 3 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 PPAD, assuming the sub-exponential hardness of DDH. Previous PPAD hardness results all required either bilinear maps or the learning with errors assumption.
  title={SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption},
  author={Yael Tauman Kalai and Alex Lombardi and Vinod Vaikuntanathan},