How to delegate computations
From MaRDI portal
Publication:5259584
DOI10.1145/2591796.2591809zbMath1315.68135OpenAlexW2023675273MaRDI QIDQ5259584
Ron D. Rothblum, Yael Tauman Kalai, Ran Raz
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2591796.2591809
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (39)
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ 3-Message Zero Knowledge Against Human Ignorance ⋮ Delegating RAM Computations with Adaptive Soundness and Privacy ⋮ Interactive Oracle Proofs ⋮ Adaptive Succinct Garbled RAM or: How to Delegate Your Database ⋮ Delegating RAM Computations ⋮ Bridging the gap between general probabilistic theories and the device-independent framework for nonlocality and contextuality ⋮ Single-server private information retrieval with sublinear amortized time ⋮ SNARGs for P from sub-exponential DDH and QR ⋮ Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings ⋮ Secure and efficient outsourcing computation on large-scale linear regressions ⋮ Incrementally verifiable computation via incremental PCPs ⋮ Belief-invariant and quantum equilibria in games of incomplete information ⋮ Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge ⋮ 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 ⋮ Public-coin 3-round zero-knowledge from learning with errors and keyless multi-collision-resistant hash ⋮ The hunting of the SNARK ⋮ Correlation intractability and SNARGs from sub-exponential DDH ⋮ Quantum cryptography beyond quantum key distribution ⋮ Somewhere statistical soundness, post-quantum security, and SNARGs ⋮ Fully-succinct publicly verifiable delegation from constant-size assumptions ⋮ No-signaling linear PCPs ⋮ Unnamed Item ⋮ No-signaling linear PCPs ⋮ Rational Sumchecks ⋮ Witness indistinguishability for any single-round argument with applications to access control ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Existence of Extractable One-Way Functions ⋮ Spooky Encryption and Its Applications ⋮ Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems ⋮ 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
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
This page was built for publication: How to delegate computations
