Practical verified computation with streaming interactive proofs

DOI10.1145/2090236.2090245zbMath1347.68157OpenAlexW2049982182MaRDI QIDQ2826047

Graham Cormode, Justin Thaler, Michael Mitzenmacher

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:11169768

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (21)

Sumcheck arguments and their applications ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Fine-grained secure computation ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Efficient proof composition for verifiable computation ⋮ Gemini: elastic SNARKs for diverse environments ⋮ Refereed delegation of computation ⋮ Ligero: lightweight sublinear arguments without a trusted setup ⋮ Non-interactive publicly-verifiable delegation of committed programs ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ Doubly efficient interactive proofs over infinite and non-commutative rings ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Trusted computing with addition machines. II ⋮ Non-interactive proofs of proximity ⋮ Boosting verifiable computation on encrypted data ⋮ Flexible and efficient verifiable computation on encrypted data ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Arthur-Merlin streaming complexity ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Practical verified computation with streaming interactive proofs