Interactive Certificates for Polynomial Matrices with Sub-Linear Communication - CASYS Access content directly
Preprints, Working Papers, ... Year : 2018

Interactive Certificates for Polynomial Matrices with Sub-Linear Communication

Abstract

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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : hal-01829139 , version 1

Cite

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
365 View
326 Download

Share

Gmail Facebook X LinkedIn More