Succinct delegation for low-space non-deterministic computation

DOI10.1145/3188745.3188924zbMath1427.68112OpenAlexW2809609136MaRDI QIDQ5230332

Yael Tauman Kalai, Amit Sahai, Saikrishna Badrinarayanan, Dakshita Khurana, Daniel Wichs

Publication date: 22 August 2019

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

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

zbMATH Keywords

nondeterministiclow spacenon-interactive delegationNTISPSNARGsuccinct proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Communication complexity, information complexity (68Q11)

Related Items (13)

SNARGs for P from sub-exponential DDH and QR ⋮ Non-interactive publicly-verifiable delegation of committed programs ⋮ Towards reducing delegation overhead in replication-based verification: an incentive-compatible rational delegation computing scheme ⋮ SNARGs for monotone policy batch NP ⋮ Verifiable private information retrieval ⋮ Impossibilities in succinct arguments: black-box extraction and more ⋮ Somewhere statistical soundness, post-quantum security, and SNARGs ⋮ Fully-succinct publicly verifiable delegation from constant-size assumptions ⋮ No-signaling linear PCPs ⋮ No-signaling linear PCPs ⋮ Witness indistinguishability for any single-round argument with applications to access control ⋮ Outsourcing computation: the minimal refereed mechanism ⋮ Round-optimal black-box commit-and-prove with succinct communication

This page was built for publication: Succinct delegation for low-space non-deterministic computation