Succinct Hash-Based Arbitrary-Range Proofs

• Published in: IEEE transactions on information forensics and security 2025, Vol.20, p.145-158
• Main Authors: Li, Weihan, Zhang, Zongyang, Guo, Yanpei, Chow, Sherman S. M., Wan, Zhiguo
• Format: Article
• Language: English
• Subjects: hash-based proofs; inner product argument; Lattices; post-quantum; Security; Sustainable development; Zero-knowledge range proof
• ISSN: 1556-6013; 1556-6021
• DOI: 10.1109/TIFS.2024.3497806

Zero-knowledge range proof (ZKRP) asserts that a committed integer V lies in a given range like [{0, 2^{n}-1}] without other leakages of V . It is vital in various privacy-preserving systems. Moving forward, the quest for post-quantum security is still in its infancy; the proof size of state-of-the-art lattice-based ZKRP (Lyubashevsky et al., CCS 20 and Couteau et al., Eurocrypt 21) remains linear in n , directly impacting the long-term sustainability in applications such as immutable ledgers. Confronting this unresolved impasse, we propose SHARP-PQ, i.e. , succinct hash-based arbitrary-range proof with post-quantum security. SHARP-PQ offers proof size poly-logarithmic to n , optimized batch proofs, and versatile (new) capabilities. Its success stems from the improved inner product argument and exploitation of homomorphism. Empirically, SHARP-PQ features at least 10\times smaller proof size for multiple ranges over lattice-based ZKRPs while maintaining competitive prover and verifier times. SHARP-PQ also outperforms ZKRPs directly constructed from hash-based generic zero-knowledge proofs at most 10 \times .