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 $\rho$, list-decoding and correlated agreement up to $\delta$, and encoding time $\tau \cdot \ell$, where $\ell$ is the block length. For a size $n$ polynomial, security parameter $\lambda$, and sufficiently large field, it has the following efficiency measures, up to lower order terms:

• Commitment time: $(\tau/\rho^{2} + \tau/\rho + 3) \cdot n$ field multiplications.
• Opening time: $6 n$ field multiplications.
• Query complexity: $\frac{1}{-\log(1-\delta^{2})} \cdot \lambda$.
• Verification time: $O(\lambda \log n)$. Moreover, the evaluation proof only contains $O(\log \log n)$ oracles of total size $(\lambda n)^{0.5 + o(1)}$.

With a Reed-Solomon code of rate $1/2$, the query complexity is $2.41 \lambda$ and commitment time is dominated by $(6 \log n + 3) \cdot n$ field multiplications. With an RAA code of rate $1/4$ and distance $0.19$, the query complexity is $19 \lambda$ and the commitment time is $42 n$ field additions and $3 n$ field multiplications. For both instantiations, the opening time is dominated by $6 n$ field multiplications.