### Sharp: Short Relaxed Range Proofs

##### Abstract

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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1153

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.