Paper 2026/339

$\mathsf{Spectra}$: Interval-Agnostic Vector Range Argument for Unstructured Range Assertions

Qianhong Wu, Beihang University

Bo Qin, Renmin University of China

Fudong Wu, Beihang University

Zhenyang Ding, Beihang University

Zhiguo Wan, Hangzhou Normal University

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.

@misc{cryptoeprint:2026/339,
      author = {Hao Gao and Qianhong Wu and Bo Qin and Fudong Wu and Zhenyang Ding and Zhiguo Wan},
      title = {$\mathsf{Spectra}$: Interval-Agnostic Vector Range Argument for Unstructured Range Assertions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/339},
      year = {2026},
      url = {https://eprint.iacr.org/2026/339}
}