Paper 2026/1440

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

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 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\ell \log(N\ell))$ for proving $\ell$ values in $[0, 2^N)$. We present \textbf{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$-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\left(\frac{N\ell}{\log(N\ell)}\right)\mathbb{G} + O(N\ell)\mathbb{F}$, where $\mathbb{G}$ and $\mathbb{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\times$ speedup over both Bulletproofs and Missileproof when proving 16,384 values in $[0, 2^{64})$.