2018/07/03 by David Lucas, Vincent Neiger, Lucas, David +7
Computer Science · #Cryptography and Data Security #FOS: Computer and information sciences #Formal Methods in Verification #Logic, programming, and type systems #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1807.01272
openalex publication_date 2018/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We design and analyze new protocols to verify the correctness of various\ncomputations on matrices over the ring F[x] of univariate polynomials over a\nfield F. For the sake of efficiency, and because many of the properties we\nverify are specific to matrices over a principal ideal domain, we cannot simply\nrely on previously-developed linear algebra protocols for matrices over a\nfield. Our protocols are interactive, often randomized, and feature a constant\nnumber of rounds of communication between the Prover and Verifier. We seek to\nminimize the communication cost so that the amount of data sent during the\nprotocol is significantly smaller than the size of the result being verified,\nwhich can be useful when combining protocols or in some multi-party settings.\nThe main tools we use are reductions to existing linear algebra verification\nprotocols and a new protocol to verify that a given vector is in the F[x]-row\nspace of a given matrix.\n