A Succinct Range Proof for Polynomial-based Vector Commitment
Rui Gao, Jiangsu Cryptographic Technology Engineering Research Center, Nanjing University of Posts and Telecommunications, Zhejiang Lab
Zhiguo Wan, Zhejiang Lab
Yuncong Hu, Department of Computer Science and Engineering, Shanghai Jiao Tong University
Huaqun Wang, Jiangsu Cryptographic Technology Engineering Research Center, Nanjing University of Posts and Telecommunications
Abstract
Range proofs serve as a protocol for the prover to prove to the verifier that a committed number resides within a specified range, such as , without disclosing the actual value. These proofs find extensive application in various domains, including anonymous cryptocurrencies, electronic voting, and auctions. However, the efficiency of many existing schemes diminishes significantly when confronted with batch proofs encompassing multiple elements.
The pivotal challenge arises from their focus on the commitment to a singular element rather than a vector. Addressing this gap, our paper introduces MissileProof, a zero-knowledge, succinct, non-interactive argument of knowledge tailored for the range proof of a vector commitment. Our core contribution lies in reducing this argument to a bi-to-uni variate SumCheck problem and the bivariate polynomial ZeroTest problem, and design two polynomial interactive oracle proofs (PIOPs) for each problem.
Our principal innovation involves the transformation of this argument into a bi-to-uni variate SumCheck problem and the bivariate polynomial ZeroTest problem. To tackle these challenges, we devise two Polynomial Interactive Oracle Proofs (PIOPs) for each problem.
As far as we know, our scheme has the optimal proof size (), the optimal statement length (), and the optimal verification time (), at the expense of slightly sacrificing proof time ( operations on the prime field for FFT and group exponentiations in ). We prove the security of this scheme. Experimental data shows for a committed vector of length and , our work has the best performance in terms of the statement length (0.03125KB), proof size (1.375KB) and verification time (0.01s) with a slightly increased proof time (614s).
@misc{cryptoeprint:2024/1016,
author = {Rui Gao and Zhiguo Wan and Yuncong Hu and Huaqun Wang},
title = {A Succinct Range Proof for Polynomial-based Vector Commitment},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1016},
year = {2024},
url = {https://eprint.iacr.org/2024/1016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.