Yang, X., Qu, W., Guo, Y., & Zhang, J. (2026). Rarus: A Succinct and Efficient Range Proof for Polynomial-based Vector Commitment. [Cryptology {ePrint} Archive, Paper 2026/1440]. Added by: Rucknium (17/11/2026, 16:30) Last edited by: Rucknium (17/11/2026, 16:33)
|
 |
|
Abstract
|
Range proofs enable a prover to convince a verifier that a committed value lies within a specific interval without revealing additional information. They are fundamental to privacy-preserving systems including anonymous credentials, e-voting, e-cash, and cryptocurrencies like Monero and Grin. A critical challenge is efficiently proving that multiple com- mitted values simultaneously satisfy range constraints while minimizing communication overhead.
Vector commitment schemes provide a promising ap- proach to this problem. Missileproof (CCS’24) recently pro- posed a range proof for vector commitments achieving O(1) proof size and verifier time, but with prover complexity of O(Nℓ log(Nℓ)) for proving ℓ values in [0, 2N ).
We present Rarus, an efficient range proof for polynomial- based vector commitments that achieves optimal asymp- totic complexity across all metrics. Our key innovation is replacing binary decomposition with optimized b-ary de- composition, coupled with Bi-variate Zero-Test and acceler- ated Uni-variate Sum-Check protocols. Rarus achieves O(1) proof size and verifier time, while reducing prover time to O Nℓ log(Nℓ)
G + O(Nℓ)F, where G and F denote group and field operations respectively. In addition, our protocol sup- ports arbitrary ranges [0, R) beyond powers of two. Experi- mental results demonstrate that Rarus achieves a 20× speedup over both Bulletproofs and Missileproof when proving 16,384 values in [0, 264).
Added by: Rucknium Last edited by: Rucknium
|