Practical Subvector Commitments with Optimal Opening Complexity
Matteo Campa
·
2026-01-25
·
via Cryptology ePrint Archive
We introduce a simple pairing-based vector commitment with subvector opening where, after a one-time preprocessing, the prover can open a subvector of size $\ell$ in linear time. Our focus is on practically relevant solutions compatible with already deployed setups—specifically, the powers-of-$\tau$ setup used by KZG and many popular SNARKs.
We achieve substantial concrete speedups over aSVC (Tomescu et al., SCN 2020), the state of the art in deployable subvector commitments with $O(\ell \log^2 \ell)$ prover and verifier time: our opening is over $60\times$ faster on subvectors of any size; on large subvectors ($\ell \approx$ 64K) our opening and verification achieve $\approx 4000\times$ and $170\times$ speedups respectively (and four times as much with parallelism).
Our main result is a construction where:
- A commitment is a single $\mathbb{G}_2$ element; a proof is a single $\mathbb{G}_1$ element;
- Opening requires $\ell$ point additions in $\mathbb{G}_1$;
- Verification is dominated by $2\ell$ $\mathbb{G}_1$ operations.
We also describe two variants of our main design that are directly compatible with deployed schemes and where the commitment is a $\mathbb{G}_1$ element; these two schemes show similar speedups over prior work. We additionally support cross-commitment and distributed aggregation, and provide an open-source implementation.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。