1970-01-01

(2026-02) -mathsf{Spectra}; Interval-Agnostic Vector Range Argument for Unstructured Range Assertions

[[Hao Gao]]
[[Qianhong Wu]]
[[Bo Qin]]
[[Fudong Wu]]
[[Zhenyang Ding]]
[[Zhiguo Wan]]

2026-02-20

Abstract

A structured vector range argument proves that a committed vector $\mathbf{v}$ lies in a well-structured range of the form $[0,2^d-1]$ . This structure makes the protocol extremely efficient, although it cannot handle more sophisticated range assertions, such as those arising from non-membership attestations. To address this gap, we study a more general setting not captured by prior constructions. In this setting, for each $i$ , the admissible integer set for $v_i$ is a union of $k$ intervals $\mathsf{R}_i \overset{\text{def}}{=} \bigcup_{j=0}^{k-1}\left[l_{i,j},r_{i,j}\right]$ . In this work, we present novel techniques to prove that $\mathbf{v} \in \mathbb{Z}^n_p$ lies within $\mathsf{R}_0 \times \mathsf{R}_1 \times \cdots \times \mathsf{R}_{n-1}$ . We first introduce $\mathsf{RangeLift}$ , a generic compiler that lifts a structured vector range argument to support such unstructured range assertions. Then we present $\mathsf{Spectra}$ , a realization of $\mathsf{RangeLift}$ over the $\mathsf{KZG}$ -based vector commitment scheme. $\mathsf{Spectra}$ achieves succinct communication and verifier time; its prover complexity is $O(n\,\tfrac{\log N}{\log\log N}\cdot \log(n\tfrac{\log N}{\log\log N}))$ , where $N$ upper bounds the maximum interval size across all $\mathsf{R}_i$ . Notably, $\mathsf{Spectra}$ is interval-agnostic, meaning its prover complexity is independent of the number of intervals $k$ ; therefore, its prover cost matches the single-interval case even when each $\mathsf{R}_i$ is composed of hundreds of thousands of intervals. We also obtain two new structured vector range arguments and a batching-friendly variant of the $\mathsf{Cq}^{+}$ lookup argument (PKC'24), which are also of independent interest. Experiments show that $\mathsf{Spectra}$ outperforms well-known curve-based vector range arguments on standard metrics while supporting strictly more expressive range assertions.