Paper 2022/1153
Sharp: Short Relaxed Range Proofs
, CNRS, IRIF, Université de Paris, France, Karlsruhe Institute of Technology, KASTEL, DIENS, École normale supérieure, PSL University, CNRS, INRIA, 75005 ParisAbstract
We provide optimized range proofs, called $\mathsf{Sharp}$, in discrete logarithm and hidden order groups, based on square decomposition. In the former setting, we build on the paradigm of Couteau et al. (Eurocrypt '21) and optimize their range proof (from now on, CKLR) in several ways: (1) We introduce batching via vector commitments and an adapted $\Sigma$-protocol. (2) We introduce a new group switching strategy to reduce communication. (3) As repetitions are necessary to instantiate CKLR in standard groups, we provide a novel batch shortness test that allows for cheaper repetitions. The analysis of our test is nontrivial and forms a core technical contribution of our work. For example, for $\kappa = 128$ bit security and $B = 64$ bit ranges for $N = 1$ (resp. $N = 8$) proof(s), we reduce the proof size by $34\%$ (resp. $75\%$) in arbitrary groups, and by $66\%$ (resp. $88\%)$ in groups of order $256$-bit, compared to CKLR. As $\mathsf{Sharp}$ and CKLR proofs satisfy a “relaxed” notion of security, we show how to enhance their security with one additional hidden order group element. In RSA groups, this reduces the size of state of the art range proofs (Couteau et al., Eurocrypt '17) by $77\%$ ($\kappa = 128, B = 64, N = 1$). Finally, we implement our most optimized range proof. Compared to the state of the art Bulletproofs (Bünz et al., S&P 2018), our benchmarks show a very significant runtime improvement. Eventually, we sketch some applications of our new range proofs.
Note: 2022-09-06: Fixed typo in eprint abstract.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. ACM CCS 2022
- DOI
- 10.1145/3548606.3560628
- Keywords
- relaxed range proof zero-knowledge proof of knowledge square decomposition proof of shortness
- Contact author(s)
-
couteau @ irif fr
dahmun goudarzi @ gmail com
michael klooss @ kit edu
michael reichle @ ens fr - History
- 2022-09-06: revised
- 2022-09-05: received
- See all versions
- Short URL
- https://ia.cr/2022/1153
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1153,
author = {Geoffroy Couteau and Dahmun Goudarzi and Michael Klooß and Michael Reichle},
title = {Sharp: Short Relaxed Range Proofs},
howpublished = {Cryptology ePrint Archive, Paper 2022/1153},
year = {2022},
doi = {10.1145/3548606.3560628},
note = {\url{https://eprint.iacr.org/2022/1153}},
url = {https://eprint.iacr.org/2022/1153}
}
