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

Jean-Guillaume Dumas 1 Vincent Zucca 2
2 ALMASTY - ALgorithms for coMmunicAtion SecuriTY
LIP6 - Laboratoire d'Informatique de Paris 6
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.
Type de document :
Communication dans un congrès
ACISP 2017 - 22nd Australasian Conference on Information Security and Privacy, Jul 2017, Auckland, New Zealand. Springer, 10343, pp.115-134, 2017, Lecture Notes in Computer Science. 〈http://acisp.massey.ac.nz/〉. 〈10.1007/978-3-319-59870-3_7〉
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01503870
Contributeur : Jean-Guillaume Dumas <>
Soumis le : vendredi 7 avril 2017 - 17:04:46
Dernière modification le : mercredi 13 septembre 2017 - 01:10:57
Document(s) archivé(s) le : samedi 8 juillet 2017 - 16:10:15

Fichiers

report_vc_spmv.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

Collections

Citation

Jean-Guillaume Dumas, Vincent Zucca. Prover efficient public verification of dense or sparse/structured matrix-vector multiplication. ACISP 2017 - 22nd Australasian Conference on Information Security and Privacy, Jul 2017, Auckland, New Zealand. Springer, 10343, pp.115-134, 2017, Lecture Notes in Computer Science. 〈http://acisp.massey.ac.nz/〉. 〈10.1007/978-3-319-59870-3_7〉. 〈hal-01503870〉

Partager

Métriques

Consultations de
la notice

469

Téléchargements du document

49