Interactive Certificates for Polynomial Matrices with Sub-Linear Communication - CASYS Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

Interactive Certificates for Polynomial Matrices with Sub-Linear Communication

Résumé

We develop and analyze new protocols to verify the correctness ofvarious computations on matrices over F[x], where F is a field. Theproperties we verify concern an F[x]-module and therefore cannotsimply rely on previously-developed linear algebra certificates whichwork only for vector spaces. Our protocols are interactivecertificates, often randomized, and featuring a constant number ofrounds of communication between the prover and verifier. We seek tominimize the communication cost so that the amount of data sent duringthe protocol is significantly smaller than the size of the resultbeing verified, which can be useful when combining protocols or insome multi-party settings. The main tools we use are reductions toexisting linear algebra certificates and a new protocol to verify thata given vector is in the F[x]-linear span of a given matrix.
Fichier principal
Vignette du fichier
polynomial_matrix_certificates.pdf (669.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01829139 , version 1 (03-07-2018)
hal-01829139 , version 2 (11-12-2019)

Identifiants

  • HAL Id : hal-01829139 , version 1

Citer

David Lucas, Vincent Neiger, Clément Pernet, Daniel Barry Roche, Johan Rosenkilde. Interactive Certificates for Polynomial Matrices with Sub-Linear Communication. 2018. ⟨hal-01829139v1⟩

Collections

LJK_MAD_CASYS
369 Consultations
328 Téléchargements

Partager

Gmail Facebook X LinkedIn More