Delegation for bounded space

DOI10.1145/2488608.2488679MaRDI QIDQ5495827zbMATH OpenOpenAlexFDO

Authors Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

delegationno-signaling proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cryptography (94A60)

Recommendations

• How to delegate computations
• Succinct delegation for low-space non-deterministic computation
• Constant-round interactive proofs for delegating computation
• Constant-round interactive proofs for delegating computation
• No-signaling linear PCPs

Cited in

(29)

• The hunting of the SNARK
• Witness indistinguishability for any single-round argument with applications to access control
• Delegation with updatable unambiguous proofs and PPAD-hardness
• Single-server private information retrieval with sublinear amortized time
• SNARGs for P from sub-exponential DDH and QR
• Incrementally verifiable computation via incremental PCPs
• Somewhere statistical soundness, post-quantum security, and SNARGs
• Fully-succinct publicly verifiable delegation from constant-size assumptions
• Rational sumchecks
• Three-player entangled XOR games are NP-hard to approximate
• Spooky Encryption and Its Applications
• Interactive oracle proofs
• A hierarchy theorem for interactive proofs of proximity
• Constant-round interactive proofs for delegating computation
• How to Delegate Computations: The Power of No-Signaling Proofs
• Probabilistic checking against non-signaling strategies from linearity testing
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• Succinct delegation for low-space non-deterministic computation
• No-signaling linear PCPs
• No-signaling linear PCPs
• Non-interactive publicly-verifiable delegation of committed programs
• Batch arguments for \textsf{NP} and more from standard bilinear group assumptions
• Optimal single-server private information retrieval
• SNARGs for monotone policy batch NP
• Correlation intractability and SNARGs from sub-exponential DDH
• Boosting batch arguments and RAM delegation
• Quantum advantage from any non-local game
• Locally verifiable distributed SNARGs
• Adaptively sound zero-knowledge SNARKs for UP

This page was built for publication: Delegation for bounded space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495827)