Paper 2026/714

$\mathsf{Veloz}$: Efficient and Flexible Distribution Framework for Interleaved-Code-Based Polynomial Commitment Scheme

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 interleaved-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 agnosticism. We also implement both schemes in Rust and conduct a comprehensive performance evaluation. The experimental results demonstrate their efficient scalability with increasing $M$. More specifically, for $N = 2^{30}$ and $M = 8$, $\mathsf{Veloz}_{\text{RS}}$ takes 61.8s for proof generation, achieving a 6.46$\times$ speedup compared to running a single prover, while $\mathsf{Veloz}_{\text{Lin}}$ generates a proof in 26.9s and achieves a 7.03$\times$ speedup.

Note: Major updates on the security proof and experiments, and minor updates on the introduction.