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

DOI10.1007/978-3-319-59870-3_7MaRDI QIDQ2014608zbMATHOpenAlexFDO

Authors Jean-Guillaume Dumas, Vincent Zucca

Publication date 25 August 2017

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(5)

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

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)