Paper 2026/714

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

Shi-Feng Sun, Shanghai Jiao Tong University

Yuncong Zhang, Shandong University

Chenhua Fan, Xidian University

Tianyi Ma, Shanghai Jiao Tong University

Dawu Gu, Shanghai Jiao Tong University

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.

@misc{cryptoeprint:2026/714,
      author = {Yuanzhuo Yu and Shi-Feng Sun and Yuncong Zhang and Chenhua Fan and Tianyi Ma and Dawu Gu},
      title = {$\mathsf{Veloz}$: Efficient and Flexible Distribution Framework for Code-Based Polynomial Commitment Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/714},
      year = {2026},
      url = {https://eprint.iacr.org/2026/714}
}