Paper 2026/487

Linear-Time, Constant-Depth Blind Polynomial Commitments from Generalized RAA Codes, with an End-to-End Blind SNARK Implementation

Yanpei Guo, National University of Singapore

Wenjie Qu, National University of Singapore

Jiaheng Zhang, National University of Singapore

Abstract

In this work, we construct a new and highly efficient blind polynomial commitment scheme (PCS) over non-binary fields. Our scheme is specifically designed to handle encrypted coefficients without requiring expensive bootstrapping operations, achieving a breakthrough in the "complexity-depth" trade-off. The proposed scheme features an extremely efficient prover both asymptotically and concretely. The commitment and evaluation phases are dominated by a strictly linear $O(n)$ number of field operations. Furthermore, the construction maintains a constant multiplicative depth, which is a critical requirement for efficiency in homomorphic encryption settings. Concretely, for large-scale circuit sizes, our prover is significantly faster than prior state-of-the-art schemes such as phalanx and laminate. Our underlying technique is the Generalized RAA code, an extremely efficient error-correcting code that extends the binary RAA code structure to arbitrary non-binary prime fields $\mathbb{F}_{p}$. We analyze the bounds over non-binary fields, which demonstrate that this code maintains a linear minimum distance property with high probability. By combining Ligero’s IOPP framework, we obtain the first asymptotically and concretely good blind PCS that achieves strictly linear $O(n)$ encoding complexity for the prover while avoiding the expensive bootstrapping operations.

@misc{cryptoeprint:2026/487,
      author = {Kexi Huang and Yanpei Guo and Wenjie Qu and Jiaheng Zhang},
      title = {Linear-Time, Constant-Depth Blind Polynomial Commitments from Generalized {RAA} Codes, with an End-to-End Blind {SNARK} Implementation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/487},
      year = {2026},
      url = {https://eprint.iacr.org/2026/487}
}