TY - GEN
T1 - SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption
AU - Kalai, Yael Tauman
AU - Lombardi, Alex
AU - Vaikuntanathan, Vinod
N1 - Funding Information:
VV was supported in part by DARPA under Agreement No. HR00112020023, NSF CNS-2154174, and a Thornton Family Faculty Research Innovation Fellowship from MIT. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA. This research was conducted in part while AL was at MIT, where he was supported by a Charles M. Vest fellowship and the grants above.
Publisher Copyright:
© 2023, International Association for Cryptologic Research.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85161723168&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85161723168&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-30617-4_16
DO - 10.1007/978-3-031-30617-4_16
M3 - Conference contribution
AN - SCOPUS:85161723168
SN - 9783031306167
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 470
EP - 498
BT - Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2023, Proceedings
A2 - Hazay, Carmit
A2 - Stam, Martijn
PB - Springer Science and Business Media Deutschland GmbH
T2 - 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023
Y2 - 23 April 2023 through 27 April 2023
ER -