Verification protocols with sub-linear communication for polynomial matrix operations
From MaRDI portal
Publication:1994891
Abstract: We design and analyze new protocols to verify the correctness of various computations on matrices over the ring F[x] of univariate polynomials over a field F. For the sake of efficiency, and because many of the properties we verify are specific to matrices over a principal ideal domain, we cannot simply rely on previously-developed linear algebra protocols for matrices over a field. Our protocols are interactive, often randomized, and feature a constant number of rounds of communication between the Prover and Verifier. We seek to minimize the communication cost so that the amount of data sent during the protocol is significantly smaller than the size of the result being verified, which can be useful when combining protocols or in some multi-party settings. The main tools we use are reductions to existing linear algebra verification protocols and a new protocol to verify that a given vector is in the F[x]-row space of a given matrix.
Recommendations
- Polynomial time interactive proofs for linear algebra with exponential matrix dimensions and scalars given by polynomial time circuits
- Prover efficient public verification of dense or sparse/structured matrix-vector multiplication
- Essentially optimal interactive certificates in linear algebra
- Time-optimal interactive proofs for circuit evaluation
- Secure Linear Algebra Using Linearly Recurrent Sequences
Cites work
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- scientific article; zbMATH DE number 5485522 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 3635490 (Why is no real title available?)
- scientific article; zbMATH DE number 1254300 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 3439001 (Why is no real title available?)
- scientific article; zbMATH DE number 2151192 (Why is no real title available?)
- scientific article; zbMATH DE number 3009965 (Why is no real title available?)
- scientific article; zbMATH DE number 3401090 (Why is no real title available?)
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- A general module theoretic framework for vector M-Padé and matrix rational interpolation
- A probabilistic remark on algebraic program testing
- Certificates for triangular equivalence and rank profiles
- Certification of minimal approximant bases
- Certified dense linear system solving
- Computing Popov and Hermite forms of rectangular polynomial matrices
- Computing canonical bases of modules of univariate relations
- Computing column bases of polynomial matrices
- Computing the rank profile matrix
- Essentially optimal interactive certificates in linear algebra
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast computation of Hermite normal forms of random integer matrices
- Fast projection methods for minimal design problems in linear system theory
- Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
- Fraction-free computation of matrix rational interpolants and matrix GCDs
- High-order lifting and integrality certification
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Invariant Description of Linear, Time-Invariant Controllable Systems
- Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
- Matrix multiplication via arithmetic progressions
- Modern computer algebra
- Normal forms for general polynomial matrices
- On fast multiplication of polynomials over arbitrary algebras
- Polynomial evaluation and interpolation on special sets of points
- Powers of tensors and fast matrix multiplication
- Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)
- Quadratic-time certificates in linear algebra
- Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
- The Knowledge Complexity of Interactive Proof Systems
- Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)
- Unimodular completion of polynomial matrices
This page was built for publication: Verification protocols with sub-linear communication for polynomial matrix operations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994891)
