Non-interactive delegation and batch NP verification from standard computational assumptions

DOI10.1145/3055399.3055497zbMath1369.68209OpenAlexW2625723895MaRDI QIDQ4977995

Yael Kalai, Justin Holmgren, Zvika Brakerski

Publication date: 17 August 2017

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

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

zbMATH Keywords

probabilistically checkable proofsdelegation of computationprivate information retrievalbatch arguments for NPcomputational no-signaling

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60)

Related Items (20)

Non-interactive batch arguments for NP from standard assumptions ⋮ Delegating RAM Computations ⋮ SNARGs for P from sub-exponential DDH and QR ⋮ Incrementally verifiable computation via incremental PCPs ⋮ Non-interactive publicly-verifiable delegation of committed programs ⋮ 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 ⋮ Verifiable private information retrieval ⋮ 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 ⋮ Unnamed Item ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Round-optimal black-box commit-and-prove with succinct communication ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness ⋮ Succinct non-interactive secure computation

This page was built for publication: Non-interactive delegation and batch NP verification from standard computational assumptions