Welcome to the resource topic for 2025/2065
Title:
TensorSwitch: Nearly Optimal Polynomial Commitments from Tensor Codes
Authors: Benedikt Bünz, Giacomo Fenzi, Ron D. Rothblum, William Wang
Abstract: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.
ePrint: https://eprint.iacr.org/2025/2065
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .