Paper 2025/1159
$\mathsf{DekartProof}$: Efficient Vector Range Proofs and Their Applications
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- zero-knowledgerange proofspublicly verifiable secret sharingconfidential transactions
- Contact author(s)
-
dabo @ cs stanford edu
tcdatta @ stanford edu
rex fernando @ aptoslabs com
nazirk @ cs stanford edu
tomescu alin @ gmail com - History
- 2025-06-20: approved
- 2025-06-19: received
- See all versions
- Short URL
- https://ia.cr/2025/1159
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1159,
author = {Dan Boneh and Trisha Datta and Rex Fernando and Kamilla Nazirkhanova and Alin Tomescu},
title = {$\mathsf{{DekartProof}}$: Efficient Vector Range Proofs and Their Applications},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1159},
year = {2025},
url = {https://eprint.iacr.org/2025/1159}
}
