Paper 2022/1153

Sharp: Short Relaxed Range Proofs

Geoffroy Couteau, CNRS, IRIF, Université de Paris, France
Dahmun Goudarzi
Michael Klooß, Karlsruhe Institute of Technology, KASTEL
Michael Reichle, DIENS, École normale supérieure, PSL University, CNRS, INRIA, 75005 Paris

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)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
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
2022-09-06: revised
2022-09-05: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.