Welcome to the resource topic for 2025/1159
Title:
\mathsf{DekartProof}: Efficient Vector Range Proofs and Their Applications
Authors: Dan Boneh, Trisha Datta, Rex Fernando, Kamilla Nazirkhanova, Alin Tomescu
Abstract:Let p be a prime and consider a committed vector \vec{v} = (v_1, \ldots, v_m) \in \mathbb{F}_p^m.
We develop new techniques for succinctly proving in zero-knowledge that all the elements of \vec{v} are in the range \{0,1,\ldots,n\} for some n<p.
We refer to this as a batched zero-knowledge range proof, or a batched ZKRP.
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.
ePrint: https://eprint.iacr.org/2025/1159
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .