SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE

DOI10.1145/3406325.3451055OpenAlexW3082337096MaRDI QIDQ6087038

Dakshita Khurana, Rachel Yun Zhang, Ruta Jawale, Yael Tauman Kalai

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3406325.3451055

zbMATH Keywords

cryptographic protocolsdelegation of computationFiat-Shamir heuristicPPAD hardness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (13)

Non-interactive batch arguments for NP from standard assumptions ⋮ One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model ⋮ SNARGs for P from sub-exponential DDH and QR ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Batch arguments for \textsf{NP} and more from standard bilinear group assumptions ⋮ Parallelizable delegation from LWE ⋮ Non-interactive universal arguments ⋮ SNARGs for monotone policy batch NP ⋮ Public-coin 3-round zero-knowledge from learning with errors and keyless multi-collision-resistant hash ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Correlation intractability and SNARGs from sub-exponential DDH ⋮ Secure computation with shared EPR pairs (or: how to teleport in zero-knowledge) ⋮ Somewhere statistical soundness, post-quantum security, and SNARGs

This page was built for publication: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE