Code-based Distributed Polynomial Commitment Scheme with Linear Prover Time and Polylogarithmic Communication

Zesheng Li; Xinzhen Chen; Yuejia Cheng; Zixing Wang; Yihang Du; Xinxuan Zhang; Yi Deng

Paper 2025/2327

Code-based Distributed Polynomial Commitment Scheme with Linear Prover Time and Polylogarithmic Communication

Zesheng Li, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Xinzhen Chen, National University of Singapore

Yuejia Cheng, Sussex University

Zixing Wang, School of Cyber Science and Technology, Shandong University

Yihang Du, College of Computer Science and Electronic Engineering, Hunan University

Xinxuan Zhang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Yi Deng, Xidian University

Abstract

We present the first fully distributed, code-based polynomial commitment scheme (PCS) that achieves linear prover time and polylogarithmic communication for multilinear polynomials. Our construction builds on Brakedown with proof composition. We design a distributed proof of correct linear encoding. Codeword validity is reduced to a sumcheck relation over the sparse parity-check matrix, whereas systematic consistency is verified through multilinear evaluation checks. These techniques preserve linear prover complexity while reducing the communication size between sub-provers to polylogarithmic scale. We implement our construction and evaluate it on multilinear polynomials ranging in size from $2^{22}$ to $2^{28}$. The prover exhibits near-linear parallel scalability. Compared with existing evaluated distributed PCS implementations with 8 parties, it reduces communication by at least $13\times$ at every tested polynomial size, while its prover time remains within $1.31\times$ of the fastest implementation. These results demonstrate that our asymptotic communication improvements translate into substantial concrete savings while retaining efficient proving.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Distributed Polynomial Commitment Scalable
Contact author(s): lizesheng @ iie ac cn
asleep @ u nus edu
chengyuejia @ foxmail com
zixing @ mail sdu edu cn
202208060130 @ hnu edu cn
zhangxinxuan @ iie ac cn
ydeng cas @ gmail com
History: 2026-08-20: revised; 2025-12-26: received; See all versions
Short URL: https://ia.cr/2025/2327
License: CC BY

BibTeX

@misc{cryptoeprint:2025/2327,
      author = {Zesheng Li and Xinzhen Chen and Yuejia Cheng and Zixing Wang and Yihang Du and Xinxuan Zhang and Yi Deng},
      title = {Code-based Distributed Polynomial Commitment Scheme with Linear Prover Time and Polylogarithmic Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2327},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2327}
}