Sharp: Short Relaxed Range Proofs

We provide optimized range proofs, called 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 Σ-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 λ = 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 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% (λ = 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. anonymous credentials [Cha90], e-voting [Gro05], or e-cash [CHL05], and have been introduced recently in some popular anonymous cryptocurrencies (see [dev22; The22; Bün+20]). Range Proofs. Many range proofs which have been constructed in the past can be categorized in two main paradigms: (1) Range proofs based on n-ary decomposition [CCs08; Gro11], where one proves a statement of the form x ∈ [0, n ) by committing to an n-ary decomposition (x 0 , . . . , x -1 ) of x, and proving that x = i x i • n i and each x i belongs to [0, n) (which can be done efficiently when n is small). The state of the art method in this paradigm is Bulletproofs [Bün+18], which features very small proof size O(λ • log ) for a security parameter λ (using binary decomposition), and also enjoys a transparent setup: the only trusted parameter it requires is an unstructured common random string, which can be easily generated by standard "nothing up my sleeve" methods (in contrast, protocols requiring a structured common string need to trust the parameter generator, which is undesirable). Due to its great concrete efficiency and its transparent setup, Bulletproofs have become the most commonly used solution in real-world applications. (2) Range proofs based on square decomposition [Bou00; Lip03; Gro05; CPP17], where one proves a statement of the form x ≥ 0 by using special integer commitment schemes [FO97; DF02] to commit to x over Z, and by proving the existence of four squares x 1 , . . . , x 4 such that x = i x 2 i (such a decomposition always exist by a theorem of Lagrange, and ensures non-negativity). This generalizes to arbitrary intervals [a, b] by proving non-negativity of (x -a)(b -x). While avoiding n-ary decomposition is attractive, instantiating integer commitments required until recently the use of hidden order groups (such as RSA groups), whose elements are too large to be competitive with Bulletproofs for any reasonable interval size, and which require a trusted setup (to set up the RSA modulus). The CKLR Range Proof. In a recent work [Cou+21], Couteau et al. revived the square decomposition paradigm, by constructing bounded integer commitment schemes, which can be instantiated over cryptographic groups with hard DLOG problem. They instantiate (a variant of) the range proof of [CPP17] with this new commitment scheme, significantly reducing their size and removing the need for a structured common reference string. The CKLR scheme was shown to compare favorably with Bulletproofs: for a careful choice of parameters and underlying group, the proofs are about 15% shorter than Bulletproofs, and require an order of magnitude less group operations. Therefore, on paper, CKLR seems to offer a competitive alternative to Bulletproofs. CKLR versus Bulletproofs. However, this cost estimation ignores several important practical aspects, and the distinction turns out to be far from clear cut in real-world instantiations. The main limitation of CKLR is that it requires exotic group sizes -typically, elliptic curves with elements of size 352 or 416 bits to achieve 128 bits of security for 32-or 64-bit ranges. While in theory, we can use curves with a wide variety of sizes, and many standard options exist, the vast majority of cryptographic applications build upon 256-bit elliptic curves, and highly optimized implementations of some of these curves are available (for example in libsecp256k1 [Wui18] or ristretto255 [Val+19] ). These libraries typically offer runtimes 10 to 20 times faster than the NIST standardized implementations of o