Welcome to the resource topic for 2022/1153
Title:
Sharp: Short Relaxed Range Proofs
Authors: Geoffroy Couteau, Dahmun Goudarzi, Michael Klooß, Michael Reichle
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 der 256-bit “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.
ePrint: https://eprint.iacr.org/2022/1153
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .