TY - GEN
T1 - SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption
AU - Kalai, Yael Tauman
AU - Lombardi, Alex
AU - Vaikuntanathan, Vinod
N1 - 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 -