Essentially Optimal Interactive Certificates in Linear Algebra
summary
Claims interactive, essentially linear time verification procedures for integer linear-algebra outputs (rank, determinant, characteristic polynomial) using randomized checks and modular LU factorizations; demonstrates a 2,000,000×2,000,000 rank computed in ~1,000 CPU-days and shows the verifier runs in time proportional to input bits. Methods combine Freivalds-style vector tests, many small primes or a public random function/hash to derandomize interactivity, and SOS→PSD reductions for polynomial inequalities. Limits: characteristic-polynomial proof currently needs a random-oracle/cryptographic assumption and sparse-det lacks a linear-time certificate; charpoly exponent ≈2.69.
AI-written summary · about
chapters (7)
- 0:00Start
- 7:04Warm-up: Rusin Freivalds's 1979 Certificates
- 26:42Monte-Carlo Yields Cryptographically Strong Certificates [Kaltofen 2012]
- 31:44Certification of Lower Bounds
- 34:05Theodore Motzkin's 1967 Polynomial
- 44:16Dumas's & Kaltofen's 2014 Sparse Matrix Rank Certificate As Interactive Protocol
- 53:20Open Problems
related talks
01h 16mMultilinear Maps Over the Integers: From Design to Security
01h 09mCrypto + ML 1
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 08mCryptography from Ideal Lattices
01h 03mLinear-Time Zero-Knowledge Arguments with Logarithmic Proof-Size
52mAn LLL Algorithm for Module Lattices
01h 09mProofs - Practice 1
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions