Efficient Vector Range Proofs and Their Applications
Trisha Datta (Stanford)
Monday, September 29th 2025, 2-3pm
Abstract:
Let p be a prime and consider a committed vector v. We develop new techniques for succinctly proving in zero-knowledge that all the elements of v are in the range {0,1,...,n} for some n < p. We refer to this as a zero-knowledge vector range proof, or a ZKVRP. This problem comes up often in cryptography: it is needed in publicly verifiable secret sharing (PVSS), confidential transactions, and election protocols. Our approach makes use of a multilinear polynomial commitment scheme and the sum check protocol to efficiently provide a batch range proof for the entire vector. Along the way we introduce a new type of a Polynomial Interactive Oracle Proof (PIOP) we call a Homomorphic PIOP that can be compiled into a SNARK. We use an HPIOP to construct a new efficient zero-knowledge version of the sum check protocol. We compare our new techniques with existing range proofs and lookup arguments.