Succinct Hash-Based Arbitrary-Range Proofs
- 13 November 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 20 (15566013) , 145-158
Abstract
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× 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×.Keywords
Funding Information
- Academic Excellence Foundation of BUAA
- National Key Research and Development Program of China (2022YFB2702702)
- National Natural Science Foundation of China (62372020, 72031001)
- Beijing Natural Science Foundation (L222050)
- General Research Fund (CUHK 14210621)
- National Natural Science Foundation of China (62272425)
This publication has 36 references indexed in Scilit:
- Practical Product Proofs for Lattice Commitments2020
- Zether: Towards Privacy in a Smart Contract World2020
- Fractal: Post-quantum and Transparent Recursive Proofs from Holography2020
- Succinct Arguments in the Quantum Random Oracle Model2019
- Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation2019
- Aurora: Transparent Succinct Arguments for R1CS2019
- Generalized Mersenne Prime2011
- Non-interactive Zero-Knowledge Arguments for Voting2005
- Compact E-Cash2005
- Software Implementation of the NIST Elliptic Curves Over Prime Fields2001