SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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 the Fiat-Shamir heuristic for certain variants of the sumcheck protocol, we also show the existence of (sub-exponentially) hard problems in the complexity class PPAD, assuming the sub-exponential hardness of DDH. Previous PPAD hardness results required either bilinear maps or the learning with errors assumption.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2023, Proceedings
EditorsCarmit Hazay, Martijn Stam
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages29
ISBN (Print)9783031306167
StatePublished - 2023
Externally publishedYes
Event42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 - Lyon, France
Duration: Apr 23 2023Apr 27 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14005 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption'. Together they form a unique fingerprint.

Cite this