Prover efficient public verification of dense or sparse/structured matrix-vector multiplication

DOI10.1007/978-3-319-59870-3_7zbMATH Open1489.68034arXiv1704.02768OpenAlexW2607117811MaRDI QIDQ2014608FDOQ2014608

Authors: Jean-Guillaume Dumas, Vincent Zucca 

Publication date: 25 August 2017

Abstract: With the emergence of cloud computing services, computationally weak devices (Clients) can delegate expensive tasks to more powerful entities (Servers). This raises the question of verifying a result at a lower cost than that of recomputing it. This verification can be private, between the Client and the Server, or public, when the result can be verified by any third party. We here present protocols for the verification of matrix-vector multiplications, that are secure against malicious Servers. The obtained algorithms are essentially optimal in the amortized model: the overhead for the Server is limited to a very small constant factor, even in the sparse or structured matrix case; and the computational time for the public Verifier is linear in the dimension. Our protocols combine probabilistic checks and cryptographic operations, but minimize the latter to preserve practical efficiency. Therefore our protocols are overall more than two orders of magnitude faster than existing ones.

Full work available at URL: https://arxiv.org/abs/1704.02768

Recommendations

• New publicly verifiable computation for batch matrix multiplication
• Protecting data privacy in publicly verifiable delegation of matrix and polynomial functions
• A blindly public verifiable outsourcing scheme for matrix multiplication
• Batch verifiable computation with public verifiability for outsourcing polynomials and matrix computations
• Multi-server verifiable delegation of computations: unconditional security and practical efficiency

Mathematics Subject Classification ID

Cryptography (94A60) Internet topics (68M11) Network protocols (68M12) Computer security (68M25)

Cited In (5)

• A blindly public verifiable outsourcing scheme for matrix multiplication
• Verification protocols with sub-linear communication for polynomial matrix operations
• New publicly verifiable computation for batch matrix multiplication
• Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)
• Using Freivalds' algorithm to accelerate lattice-based signature verifications

This page was built for publication: Prover efficient public verification of dense or sparse/structured matrix-vector multiplication

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