Rarus: A Succinct and Efficient Range Proof for Polynomial-based Vector Commitment

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 committed values simultaneously satisfy range constraints while minimizing communication overhead. Vector commitment schemes provide a promising approach to this problem. Missileproof (CCS'24) recently proposed 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,2 N ). We present Rarus , an efficient range proof for polynomial-based vector commitments that achieves optimal asymptotic complexity across all metrics. Our key innovation is replacing binary decomposition with optimized b b-ary decomposition, coupled with Bi-variate Zero-Test and accelerated 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 supports arbitrary ranges [0,R) beyond powers of two. Experimental results demonstrate that Rarus achieves a 20× speedup over both Bulletproofs and Missileproof when proving 16,384 values in [0,2 64 = ).