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

7 Scopus citations

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 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
Pages470-498
Number of pages29
ISBN (Print)9783031306167
DOIs
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

Conference

Conference42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023
Country/TerritoryFrance
CityLyon
Period4/23/234/27/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this