1970-01-01

(2026-04) -mathsf{Veloz}; Efficient and Flexible Distribution Framework for Code-Based Polynomial Commitment Scheme

[[Yuanzhuo Yu]]
[[Shi-Feng Sun]]
[[Yuncong Zhang]]
[[Chenhua Fan]]
[[Tianyi Ma]]
[[Dawu Gu]]

2026-04-12

Abstract

Polynomial commitment schemes (PCSs) are a fundamental cryptographic primitive that allows a prover to reveal evaluations for a committed polynomial. Motivated by the inefficiency of proof generation for large-scale computations as well as the concerns regarding third-party reliance and quantum threats, a line of recent works has focused on distributing code-based PCS, where the proving workload is distributed among multiple sub-provers to accelerate proof generation, while preserving transparent setup and plausible quantum resilience. However, for $M$ sub-provers generating an evaluation proof for a polynomial of size $N$ , existing solutions either require $O(N)$ total communication among sub-provers, or incur an $O(M)$ overhead in proof size.

In this paper, we introduce $\mathsf{Veloz}$ , a novel distribution framework for code-based multilinear PCS, which for the first time achieves communication cost sublinear in $N$ , and eliminates the dependence of proof size on the number of sub-provers, without compromising proving speed or security. At its core is a customized proof aggregation method from interleaved code that efficiently combines sub-proofs via minimum communication. We further present two instantiations of $\mathsf{Veloz}$ : one based on Reed-Solomon code, $\mathsf{Veloz}_{\text{RS}}$ , achieves $O(\frac{N}{M}\log{\frac{N}{\log{N}}})$ proving time, $O(\lambda \cdot \frac{\log^{2}{N}}{\log\log{N}} + M\cdot\frac{N}{\log{N}})$ communication, and $O(\lambda \cdot \frac{\log^{2}{N}}{\log\log{N}})$ proof size; the other based on the fast linear code from Brakedown (Golovnev et al., CRYPTO 2023), $\mathsf{Veloz}_{\text{Lin}}$ , features $O(\frac{N}{M})$ proving time, $O(\lambda \cdot K + M\cdot\frac{N}{K})$ communication, and $O(\lambda \cdot K)$ proof size for $K \in [\sqrt[3]{N}, \sqrt{N}]$ , while enjoying field agnosticity.

We also implement both schemes in Rust and conduct a comprehensive performance evaluation. The experimental results demonstrate their linear scalability with increasing $M$ . More specifically, for $N = 2^{30}$ and $M = 8$ , $\mathsf{Veloz}_{\text{RS}}$ takes 74.8s for proof generation, achieving a 5.18 $\times$ speedup compared to running a single prover, while $\mathsf{Veloz}_{\text{Lin}}$ generates a proof in 26.9s and achieves a 7.02 $\times$ speedup.