TensorSwitch: Nearly Optimal Polynomial Commitments from Tensor Codes

A polynomial commitment scheme (PCS) enables a prover to succinctly commit to a large polynomial and later generate evaluation proofs that can be efficiently verified. In recent years, PCSs have emerged as a central focus of succinct non-interactive argument (SNARG) design. We present TensorSwitch, a hash-based PCS for multilinear polynomials that improves the state-of-the-art in two fundamental bottlenecks: prover time and proof size. We frame our results as an interactive oracle PCS, which can be compiled into a cryptographic PCS using standard techniques. The protocol uses any linear code with rate ρ, list-decoding and correlated agreement up to δ, and encoding time τ·ℓ, where ℓ is the block length. For a size n polynomial, security parameter λ, and sufficiently large field, it has the following efficiency measures, up to lower order terms:Commitment time: (τ/ρ2+τ/ρ+3)·n field multiplications.Opening time: 6n field multiplications.Query complexity: 1-log(1-δ2)·λ.Verification time: O(λlogn). Commitment time: (τ/ρ2+τ/ρ+3)·n field multiplications. Opening time: 6n field multiplications. Query complexity: 1-log(1-δ2)·λ. Verification time: O(λlogn). Moreover, the evaluation proof only contains O(loglogn) oracles of total size (λn)0.5+o(1). With a Reed-Solomon code of rate 1/2, the query complexity is 2.41λ and commitment time is dominated by (6logn+3)·n field multiplications. With an RAA code of rate 1/4 and distance 0.19, the query complexity is 19λ and the commitment time is 42n field additions and 3n field multiplications. For both instantiations, the opening time is dominated by 6n field multiplications.