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

Xinyang Yang, Wenjie Qu, Yanpei Guo, and Jiaheng Zhang, National University of Singapore

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,2N).

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,264 =).

USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {320793,
author = {Xinyang Yang and Wenjie Qu and Yanpei Guo and Jiaheng Zhang},
title = {Rarus: A Succinct and Efficient Range Proof for Polynomial-based Vector Commitment},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {5771--5790},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/yang-xinyang},
publisher = {USENIX Association},
month = aug
}