Document Open Access Logo

Efficient Interactive Proofs for Linear Algebra

Authors Graham Cormode , Chris Hickey

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.48.pdf
  • Filesize: 0.62 MB
  • 19 pages

Document Identifiers

Author Details

Graham Cormode
  • University of Warwick, UK
Chris Hickey
  • University of Warwick, UK

Funding

  • Cormode, Graham: Supported by European Research Council grant ERC-2014-CoG 647557.
  • Hickey, Chris: Supported by European Research Council grant ERC-2014-CoG 647557.

Cite As Get BibTex

Graham Cormode and Chris Hickey. Efficient Interactive Proofs for Linear Algebra. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.48

Abstract

Motivated by the growth in outsourced data analysis, we describe methods for verifying basic linear algebra operations performed by a cloud service without having to recalculate the entire result. We provide novel protocols in the streaming setting for inner product, matrix multiplication and vector-matrix-vector multiplication where the number of rounds of interaction can be adjusted to tradeoff space, communication, and duration of the protocol. Previous work suggests that the costs of these interactive protocols are optimized by choosing O(log n) rounds. However, we argue that we can reduce the number of rounds without incurring a significant time penalty by considering the total end-to-end time, so fewer rounds and larger messages are preferable. We confirm this claim with an experimental study that shows that a constant number of rounds gives the fastest protocol.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive computation
Keywords
  • Streaming Interactive Proofs
  • Linear Algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory, 1(1):2:1-2:54, February 2009. URL: https://doi.org/10.1145/1490270.1490272.
  2. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  3. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs. Cryptology ePrint Archive, Report 2016/116, 2016. URL: https://eprint.iacr.org/2016/116.
  4. Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum. Fiat-Shamir From Simpler Assumptions. Cryptology ePrint Archive, Report 2018/1004, 2018. URL: https://eprint.iacr.org/2018/1004.
  5. Amit Chakrabarti, Graham Cormode, and Andrew Mcgregor. Annotations in data streams. Automata, Languages and Programming, pages 222-234, 2009. Google Scholar
  6. Graham Cormode and Chris Hickey. Cheap Checking for Cloud Computing: Statistical Analysis via Annotated Data Streams. In International Conference on Artificial Intelligence and Statistics, pages 1318-1326, 2018. Google Scholar
  7. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 90-112. ACM, 2012. Google Scholar
  8. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. Proceedings of the VLDB Endowment, 5(1):25-36, 2011. Google Scholar
  9. Samira Daruki, Justin Thaler, and Suresh Venkatasubramanian. Streaming verification in data analysis. In International Symposium on Algorithms and Computation, pages 715-726. Springer, 2015. Google Scholar
  10. Rūsiņš Freivalds. Fast probabilistic algorithms. Mathematical Foundations of Computer Science 1979, pages 57-69, 1979. Google Scholar
  11. Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. Delegating computation: interactive proofs for muggles. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 113-122. ACM, 2008. Google Scholar
  12. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM (JACM), 39(4):859-868, 1992. Google Scholar
  13. Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Commun. ACM, 59(2):103-112, January 2016. Google Scholar
  14. Michael O Rabin. Fingerprinting by random polynomials. Center for Research in Computing Techn., Aiken Computation Laboratory, Univ., 1981. Google Scholar
  15. Srinath TV Setty, Richard McPherson, Andrew J Blumberg, and Michael Walfish. Making argument systems for outsourced computation practical (sometimes). In NDSS, volume 1, page 17, 2012. Google Scholar
  16. Srinath TV Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Andrew J Blumberg, and Michael Walfish. Taking Proof-Based Verified Computation a Few Steps Closer to Practicality. In USENIX Security Symposium, pages 253-268, 2012. Google Scholar
  17. Adi Shamir. IP=PSPACE. Journal of the ACM (JACM), 39(4):869-877, 1992. Google Scholar
  18. Justin Thaler. Time-optimal interactive proofs for circuit evaluation. In Advances in Cryptology-CRYPTO 2013, pages 71-89. Springer, 2013. Google Scholar
  19. Victor Vu, Srinath Setty, Andrew J Blumberg, and Michael Walfish. A hybrid architecture for interactive verifiable computation. In Security and Privacy (SP), 2013 IEEE Symposium on, pages 223-237. IEEE, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact