Geoffroy Couteau
email: couteau@irif.fr

Michael Klooß
email: michael.klooss@kit.edu

Huang Lin
email: huanglinepfl@gmail.com

Michael Reichle
email: michael.reichle@ens.fr

Efficient Range Proofs with Transparent Setup from Bounded Integer Commitments

Keywords:

We introduce a new approach for constructing range proofs. Our approach is modular, and leads to highly competitive range proofs under standard assumption, using less communication and (much) less computation than the state of the art methods, without relying on a trusted setup. Our range proofs can be used as a drop-in replacement in a variety of protocols such as distributed ledgers, anonymous transaction systems, and many more, leading to significant reductions in communication and computation for these applications. At the heart of our result is a new method to transform any commitment over a finite field into a commitment scheme which allows to commit to and efficiently prove relations about bounded integers. Combining these new commitments with a classical approach for range proofs based on square decomposition, we obtain several new instantiations of a paradigm which was previously limited to RSA-based range proofs (with high communication and computation, and trusted setup). More specifically, we get:

-Under the discrete logarithm assumption, we obtain the most compact and efficient range proof among all existing candidates (with or without trusted setup). Our proofs are 12% to 20% shorter than the state of the art Bulletproof (Bünz et al., IEEE S&P '18) for standard choices of range size and security parameter, and are more efficient (both for the prover and the verifier) by more than an order of magnitude. -Under the LWE assumption, we obtain range proofs that improve over the state of the art in a batch setting when at least a few dozen range proofs are required. -Eventually, under standard class group assumptions, we obtain the first concretely efficient standard integer commitment scheme (without bounds on the size of the committed integer) which does not assume trusted setup.

Introduction

In this work, we develop new techniques to construct range proofs, an important building block in a variety of modern cryptographic protocols such as distributed ledgers, anonymous transactions, ecash, e-voting, and many more. The range proofs obtained with our methods are highly competitive with the state of the art: they rely on standard assumptions, require less communication and computation, and do not assume any trusted setup. Furthermore, our approach is modular and can be instantiated in the discrete logarithm setting, in the lattice setting (leading to the most efficient post-quantum range proofs in a batch setting), and in the class group setting. Below, we review some background.

Range proofs and anonymous transactions. Zero-knowledge proofs, introduced in the seminal work of Goldwasser,Micali,and Rackoff [GMR89], allow a prover to convince a verifier that a statement is true, while concealing all information beyond the truth of the statement. They are a fundamental primitive in cryptography, with inumerable applications. Range proofs, whose genesis can be traced back to [BCDv88], are a particular type of zero-knowledge proof where the prover wishes to convince the verifier that a committed value belongs to a certain range. Range proofs are a core building block in numerous applications such as anonymous credentials [Cha90], e-voting [Gro05], and e-cash [CHL05]. Furthermore, efficient range proofs have recently become central components in distributed ledgers, the prime example being the recent integration of Bulletproof [BBB + 18] in the cryptocurrency Monero6 and later Mimblewimble-based anonymous cryptocurrencies such as Beam7 and Grin8 . Range proofs also play an essential role in anonymous payment schemes for smart contract platforms such as Zether [BAZB20].

In most of these anonymous payment schemes, (positive and negative) integers are encoded as finite field elements, and negative spendings constitute a valid transaction in general, if they are not explicitly disallowed. This feature can be exploited to launch a double-spending attack, allowing the adversary to print money out of thin air [MIO18]. In a confidential payment scheme where both inputs and outputs of a transaction are hidden in either a digital commitment (as in Monero) or an encryption (as in Zether), range proofs are necessary to guarantee that the hidden value falls into the correct range and prevent the aforementioned overflow attack.

The maximum throughput of a distributed ledger protocol is mainly determined by the maximum block size and average transaction size [CDE + 16]. The smaller the transaction size is, the larger the maximum throughput is. The average transaction size in an anonymous payment scheme is largely determined by the zero-knowledge range proof size. Therefore, the proof size is a crucial parameter for the design of a range proof scheme. The proof generation and verification time are also vital to the performance of the system built on the range proof scheme. In the case of a decentralized anonymous payment scheme, the proof generation time will determine how fast the anonymous payment can be launched and have a direct impact on the user experience and system scalability [CZJ + 17]. The proof verification time, on the other hand, has a great impact on the workload of the miners. gi

Standard Approaches for Building Range Proofs

Due to their wide variety of applications, many constructions of range proofs have been proposed over the past decades. All these constructions can be categorized in two main high level approaches, which we outline below.

First method: n-ary decomposition. The first method is the one employed both in the early (folklore) constructions of range proofs, as well as in the latest state-of-the-art constructions (such as Bulletproof). To prove that a committed integer x belong to an interval of the form [0, n -1], where n is some small value, this method uses the following high-level template:

1. First, commit to the n-ary decomposition of x, denoted (x 0 , • • • , x -1 ). 2. Second, prove that the relation x = -1 i=0 x i • n i holds. 3. Third, prove that each component of the committed tuple belongs to [0, n -1]. Since n is typically very small, this can be achieved using some brute-force method (for example, when using binary decomposition, it amounts to proving that each component is a bit, which can be done using standard methods).

When the commitment scheme satisfies some homomorphic properties, it is generally simple to lift a proof as above to a proof for a more general interval [a, b]. The first instance of this approach is a folklore discrete-logarithm-based construction using the Pedersen commitment scheme to commit to the bit decomposition of x. Denoting β = log(b -a) the bitlength of the interval size and λ the bitlength of group elements, This leads to a range proof communicating O(λ • β) bits. This approach was first improved in [CCs08] to O(λ • β/log β) by using decomposition in a larger basis, and later in [Gro11] to O(λ • β 1/3 ), using pairings.

In a recent breakthrough work, the authors of [BBB + 18] introduced Bulletproof, which managed to reduce the communication to O(λ • log β) under the plain DLOG assumption (without pairings) while still remaining computationally efficient. Their approach relies on generalized Pedersen commitment to commit to the entire bit-decomposition of x using few group elements, and on a clever recursive proof strategy to simultaneously prove that all committed values are bits.9 This comes at the cost of a larger number of rounds O(log β) (but this is typically not a concern in real-world applications, where the Fiat-Shamir heuristic is used to make the proof non-interactive) and a computational soundness guarantee (leading to a zero-knowledge argument instead of a proof).

A strong advantage of the proofs obtained in this line of work is that they do not require any trusted setup. In real-world applications such as cryptocurrencies, this is an important feature to avoid having to trust any central authority with the secure generation of the parameters (we will discuss this more later). Due to this feature and its good concrete efficiency, Bulletproof is currently considered the state of the art method for range proofs, and has found its way into several real-world protocols.

Second method: square decomposition. The second method can be traced back to the work of Boudot [Bou00], and was initially introduced to avoid the large O(λ • β) cost of the range proofs obtained (at the time) by the first method. It relies on the following high-level template (or a close variant thereof): first, proving that x ∈ [a, b] reduces to proving that x -a and b -x (whose commitments can typically be computed homomorphically from a commitment to x) are positive. Now, to prove that a committed value y is positive:

1. First, decompose y as y = 4 i=1 y 2 i over the integers. Lagrange's four square theorem guarantees that such a decomposition exists, and efficient algorithms allow to quickly find one. 2. Second, commit to the y i and prove (using standard methods) that y = 4 i=1 y 2 i over the integers.

The advantage of this method is that it requires committing only to a constant number of components (independent of the interval size), instead of ≈ β components with the first method. This typically leads to proofs with communication O(β + λ) bits. However, it is crucial for this method that the relation is proven over the integers: standard commitment schemes such as Pedersen only allow committing values over Z p for some prime p, but finding a 4-square decomposition over Z p does not provide any guarantee of positivity. Hence, a core component of this line of work is the notion of integer commitment schemes, introduced in [FO97,DF02], which allows to commit and prove relations among values directly over the integers.

The square decomposition method has been refined in [Lip03]. Later, the work of Groth [Gro05] observed that one can instead decompose 4y + 1 as a sum of three squares (positive integers congruent to 1 modulo 4 can always be decomposed this way) to reduce the proof size, and further efficiency and security improvements were described in [CPP17]. A common issue of all these works is that all known integer commitment schemes require the use of RSA groups or class groups with a hard-to-factor discriminant. This means that the group size is very large (typically 2048 or 3072 bits), and that these proofs all require a trusted setup to generate a public product of secret prime factors 10 . Assuming a trusted setup is a rather undesirable property in a decentralized anonymous payment scheme: in general, the party responsible for the setup step can exploit the trapdoor information obtained through this process to print an unlimited amount of cryptocurrency without being detected [Sle,Ben]. Although one could potentially mitigate the risk of the above attack by using secure multi-party computation to execute the setup step (as was done e.g. for zcash11 ), it introduces additional engineering complexity and potential vulnerabilities.

Furthermore, even before Bulletproof, these proof systems were competitive with proofs obtained with the first method only for very large intervals. Compared to Bulletproof, they lead to much larger proof sizes for any interval size (and are also computationally less efficient). Due to their higher cost and their need of a trusted setup, this second method is largely considered obsolete and non-competitive with the proofs obtained through the first method.

Our Contribution

In this work, we turn the tables and demonstrate that the square decomposition method can be refined to create highly competitive range proofs, with smaller communication and computation compared to the state of the art Bulletproof, without trusted setup (meaning that our proofs only require a transparent setup), and under standard assumptions. Among other advantages, our method is modular and can also be instantiated in the lattice setting to obtain post-quantum range proofs which are highly competitive with the sate of the art in a batch scenario (where several range proofs must be computed at once), and in the class group setting with prime discriminant. Furthermore, our proofs require only three rounds of interaction, an important feature if one does not want to rely on the Fiat-Shamir heuristic, and can be modified to achieve statistical soundness instead of computational soundness (at a small cost in efficiency). At the heart of our constructions is a new generic method to convert any commitment scheme over Z p into a bounded integer commitment scheme, i.e., a commitment scheme which allows to commit to bounded-range integers and to prove relations over Z between committed bounded-range integers.

Instantiation in the discrete-log setting. Instantiating our framework with the standard Pedersen commitment scheme, we obtain a bounded integer commitment scheme under the discrete logarithm assumption. When plugging this bounded integer commitment scheme in the range proof of [CPP17], we obtain a range proof which does not require any trusted setup and can benefit simultaneously from the compactness of square-decomposition-based range proofs (i.e., constant number of group elements) and the possibility of instantiating the Pedersen commitment scheme over prime-order elliptic curve, with small group elements12 . To further optimize the proof size, we describe an optimized variant which relies on the short-exponents discrete logarithm assumption (i.e., the assumption that it is hard to compute discrete logarithm even when the exponent is sampled from a large enough bounded range), which is a well-studied variant of the standard discrete log assumption. For example, for an interval size of 2 32 and 128 bits of security, we obtain range proofs of size 501 Bytes, compared to the 608 Bytes of Bulletproof. For the same parameters, the computational cost for both the prover and the verifier are more than an order of magnitude smaller compared to Bulletproof. The high efficiency of prover and verifier is crucial for use of (range) proofs on resource constrained devices, such as smartphones. Such devices are of special interest for privacy-enhancing technologies, such as anonymous credentials [Cha90] and payment systems. To achieve practicalility, tradeoffs have to made. For example, the work [BBDE19] relies on [CCs08], which requires pairings and relatively large public parameters, whereas the work [HKRR20] relies on uncompressed, i.e. linear-size, Bulletproofs, trading communication for computation. Our range proofs are a great fit for these settings.

Detailed comparison with Bulletproof.

A more detailed comparison with Bulletproof is given in Table 1. Below, we explain how the numbers in the table have been obtained. Computing the exact costs of our range proof is rather tedious, since it involves careful optimizations with rejection sampling techniques, and optimizations using the short-exponent discrete logarithm assumption. We consider range proofs over an interval [a, b] with β = log(b -a) ∈ {32, 64}, a security parameter λ ∈ {80, 128}, and a group of size q (which might not be the same for Bulletproof and our range proof). The formula below additionally uses parameters C, S, L corresponding respectively to the challenge size, a bound on the length of short exponents, and a bound for rejection sampling. Our concrete numbers are obtained by setting C = 2 λ , S = 2 2λ , L = 256 √ 2λ . The formulas for computing the range proof size (in the non-interactive setting, when Fiat-Shamir is used), the prover work, and the verifier work, are given below:

-Proof size (in bits): 30(β + log(CL )) + log(C)/λ (2λ + 4(2β + log(CL ) + 2 log(SCL )) + 2) (our work) versus log q • (2β + 9) (Bulletproof). -Prover work (in group multiplications): 2.31 • (4β + 8 log S + 6 log C + 7 log L ) + 30 (our work) versus 18 • (β log q) (Bulletproof). -Verifier work (in group multiplications): 4.5β + 7 log S + 13 log C + 9 log L + 10 versus at least 3β • log q (lower bound on the cost for Bulletproof, computed as the cost of a single inner product argument) -Group size (in bits): log q = log(32(2 β CL ) 2 ) + 1 (our work) versus log q = 2λ (Bulletproof)

In the above, prover and verifier work are computed as the number of multiplications required for the exponentiations (we do not directly count the exponentiations for fairness of comparison: Bulletproof and our work do not use the same group size, and our optimized construction also uses exponentiations with short exponents), which largely dominate the overall cost. We note that in both our work and Bulletproof, the verifier work can be optimized by relying on multiexponentiations techniques; since these techniques apply identically in both works and do not significantly change the bottom line in terms of comparisons, we ignore them in this overview.

Asymptotically, our proofs have size O(λ+β), while Bulletproof has size O(λ log β). We note that in the range of parameters β = O(λ), our techniques actually lead to an asymptotic improvement over Bulletproof; for larger ranges, Bulletproof is more efficient, and for very small ranges, the asymptotic costs are the same for both. Previous square-decomposition-based range proofs had asymptotic cost O(β + λ 3-o(1) ) due to their use of RSA modulus (which allow for subexponential attacks).

We stress that when not using the Fiat-Shamir heuristic, our scheme can be instantiated to have only three rounds (this slightly increases the proof size, because it requires to not use rejection sampling, since the latter causes the protocol to restart with non-negligible probability) while Bulletproof requires log β rounds. Even with rejection sampling and our concrete choice of parameters, the expected number of rounds is less than 5. The round complexity is known to strongly impact the tightness of the security loss in the random oracle model. Thus for sufficiently large β, our security analysis is significantly tighter than the one of Bulletproofs in the random oracle model. Furthermore, our scheme can be instantiated to have statistical soundness. On the other hand, Bulletproof allows for extremely efficient batching of a large number of range proofs communicationwise, and would therefore become preferable when many range proofs must be performed at once if communication is the sole concern (though it usually is not). In any case, and independently of the number of range proofs, our range proofs requires 20 to 40 times less group multiplications for the prover, and 6 to 15 times less for the verifier.

Instantiation in the lattice setting. For the instantiation of our framework in the lattice setting, we build upon the commitment scheme and proof system from [YAZ + 19]. The commitments built this way allow to commit to long vectors over Z n q (think of n as being a few thousands, e.g. n = 5000). Our techniques require to use a relatively large modulus q in order to avoid overflows in the computation. As a consequence, our commitments and proofs are quite large. However, in exchange for using a large modulus, the commitment and proof system obtained by compiling the commitment of [YAZ + 19] with our techniques allow to batch many range proofs extremely efficiently: we can essentially perform up to n range proofs in parallel for the cost of a single range proof, even if the range proofs have different ranges. This improves over the communication achieved by the best plain LWE-based range proofs [YAZ + 19] in a batch setting. For example for a total proof size of 1.21 MB and β = 32, the scheme from [YAZ + 19] allows to batch 32 range proofs at once, wheras our scheme allows for 180 range proofs.

Note that under Ring-LWE (or Module-LWE) assumptions, range proofs ([ESLL19,BLLS20]) obtain better efficiency. In appendix A, we discuss the application of our techniques in this setting.

Instantiation in the class group setting. Eventually, we also instantiate our method in the class group setting. The proofs obtained this way improve over our DLOG-based proofs only for large ranges, where Bulletproof would be more efficient. On the other hand, instantiating our approach in the class group setting leads to the first concretely efficient construction of unbounded integer commitment scheme which does not require a trusted setup (the only known alternative uses RSA-UFO, which is impractical, see the discussion in [LM19]).

Concurrent Works.

In the DLOG setting, the work of [CHJ + 20] recently claimed an improvement in proof size compared to [BBB + 18] by slightly reducing the number of group elements required in [BBB + 18]. The computational cost of their proof is the same as in [BBB + 18]. To our knowledge, their scheme was not peer reviewed yet; we note that our range proofs are still shorter than theirs, and more than an order of magnitude computationally more efficient.

Technical Overview

As we outlined in the introduction, at the heart of our results is a method to convert standard homomorphic commitment schemes into bounded integer commitment schemes -that is, a scheme that allows to commit to integers from a bounded range, but also to prove in zero-knowledge relations between commited values over the integers, see [FO97,DF02] -with a certain set of additional specific properties. We now provide details on our approach.

A Natural Approach via Σ-Protocols

For simplicity, suppose that we have at our disposal a commitment scheme com with message space and random coin space Z q , for some large prime q, which is homomorphic over the messages and the coins: com(m 1 ; r 1 ) • com(m 2 ; r 2 ) = com(m 1 + m 2 ; r 1 + r 2 ). This is satisfied for example by the Pedersen commitment scheme com(m; r) = g m h r for two group elements (g, h) over a group of order q. The transformation works for a more general class of commitments, this choice of structure is for the sake of concreteness in the presentation. Suppose now that we would like to obtain a bounded integer commitment scheme out of com. The first obvious idea is to proceed as follows:

map values in Z q to integers [-(q -1)/2, (q -1)/2] in the natural way; -define com to be exactly like com, but where the committed values are restricted to [-R, R],

where R (q -1)/2 is some bound.

Intuitively, the bound R is here to ensure that we will have enough "room" to guarantee that if a relation between elements of [-R, R] holds modulo q, then it must also hold over the integers.

Looking ahead, for building a range proof, we will want to prove relations of the form x = i x 2 i , and we will choose R such that no overflow occurs when computing i x 2 i mod q with x i ∈ [-R, R]. The next step is to equip this commitment com with a zero-knowledge proof system allowing to prove relations between committed values over the integers. However, this turns out to be particularly challenging. To see this, consider the standard Σ-protocol between a prover P and a verifier V for proving knowledge of an opening (m, r) to a commitment c = com(m; r):

-P: pick (m , r ) $ ← Z 2 q and send c = com(m ; r ). -V: send a challenge e $ ← Z q . -P: send d m = em + m and d r = er + r . -V: accept if com(m; r) e • com(m ; r ) = com(d m ; d r ).
Using a standard rewinding argument, we can extract a valid opening (m; r) ∈ Z 2 q of c from any (potentially malicious) prover P * which produces accepting proofs with non-negligible probability ε: run P * to get c , fork it, and run it on two different random challenges e, e , receiving (d m , d r ) and (d m , d r ). By a standard probability lemma (see the splitting lemma from [PS96,PS00]), (c , e, d m , d r ) and (c , e , d m , d r ) will both be accepting transcript with non-negligible probability Ω(ε 2 ). From the two accepting equations, one gets

c = com((d m -d m ) • (e -e ) -1 , (d r -d r )
• (e -e ) -1 ).

(1)

To adapt the protocol to com , we would need to modify the Σ-protocol such that it additionally guarantees that the extracted value m belongs to [-R, R]. This actually seems feasible at first sight if we agree to settle for a relaxed correctness and zero-knowledge guarantee: we only enforce correctness and (honest-verifier) zero-knowledge whenever m belongs to [-R , R ], for a bound R such that 2 λ+κ R ≤ R, where κ is a statistical security parameter for zero-knowledge, and λ is a statistical security parameter for soundness (we keep both separate for generality). Then, we can modify the protocol as follows:

-P: pick (m , r ) $ ← [-2 λ+κ R , 2 λ+κ R ] × Z q and send c = com(m ; r ). -V: send a challenge e $ ← [1, 2 λ ]. -P: send d m = em + m and d r = er + r . -V: accept if com(m; r) e • com(m ; r ) = com(d m ; d r ) and d m ∈ [-R, R].
Intuitively, relaxed correctness and relaxed statistical zero-knowledge follow from the fact that for

m ∈ [-R , R ] and e ∈ [1, 2 λ ], d m = em + m for m $ ← [-2 λ+κ R , 2 λ+κ R ] will be 2 -κ -close to uniform (in statistical distance) over [-R, R].
It remains to analyze whether we can extract from an accepting prover a valid witness for com . However, even though we restricted e and d m to be small, recall that the extracted value (Equation 1) is of the form m = (d m -d m ) • (e -e ) -1 mod q. That is, m is not an element of [-R, R] in general; rather, it is the product of an element in [-R, R] and the inverse modulo q of an element in [1, 2 λ ]. Therefore, this approach fails at binding the prover to a value m ∈ [-R, R].

We note that the failure of this approach -the impossibility of extracting values guaranteed to be short in general -is a well-known problem in the context of lattice-based cryptography. Indeed, standard Σ-protocol for proving knowledge of a short solution to a system of equation -i.e., a witness for the SIS problem -suffer from exactly the same limitation (see e.g. the discussions in [BCK + 14]). The standard solution is to restrict the challenge set to {0, 1} (to guarantee that the inverse of the difference between distinct challenges remains small), and to amplify soudness via parallel repetitions. However, in our context, this would lead to a very inefficient proof system. Unfortunately, finding a different proof system with much better efficiency seems to be a hard problem (especially in the single-proof setting).

Encoding Integers as mod-q Rationals

Instead, we follow a different approach by turning the problem around: rather than searching an efficient and sound proof system for the commitment com above, we seek to find a different construction of bounded integer commitment com such that the above efficient proof system -which is not sound because it only allows extracting fractions of small values modulo p -becomes a sound proof system for com (allowing to extract bounded integers committed with com). Abstracting out, we saw above that we can extract from a cheating prover a triple (y,

d, ρ) ∈ [-R, R] × [1, 2 λ ] × Z q such that c = com(y • d -1 mod q; ρ
). Our goal will be to find an appropriate choice of encoding Encode satisfying the following properties:

com(x; ρ) = com(Encode(x); ρ), such that a commitment to a value x with com can be seen as a commitment to some different value x = Decode(x ) with com.

-Extracting a tuple (y, d, ρ) ∈ [-R, R] × [1, 2 λ ] × Z q should correspond
to extracting a valid opening of com to some bounded integer x in an appropriate bounded range.

Looking ahead, we will need a few additional properties to hold for Encode if we want to build an efficient range proofs for com.

-First, we want Encode to satisfy some appropriate homomorphic properties. Informally, we want: Encode(-x) = -Encode(x), Encode(x + a) = Encode(x) + a, and Encode(a

• x) = a • Encode(x),
for a sufficiently small integer a. -Second, we want to be able to transfer a square decomposition from encodings modulo q to encoded integers: informally, proving a relation of the form x = i (x i ) 2 mod q where x = Encode(x) and x i = Encode(x i ) should guarantee that x =

x 2 i over the integers.

Our choice of encoding. It turns out that there is a choice of (randomized) encoding that satisfies all of the above constraints simultaneously. In hindsight, this encoding is quite simple and natural: we view any pair (y,

d) ∈ [-R, R] × [1, 2 λ ] as an encoding (y, d) = Encode(x) of the integer x = y d ∈ [-R, R],
where the fraction denotes standard division, and • denotes rounding to the nearest integer. Given this choice of encoding, com is defined as follows:

com(x): pick ρ $ ← Z q and output commitment c = com(x; ρ) and opening (x, 1, ρ). -com.Verify (c, x, (y, d, ρ)

): check that c = com(y • d -1 ; ρ), x = y/d , y ∈ [-R, R], and d ∈ [1, 2 λ ].
Some remarks are in order. First, observe that com(x) is defined exactly as com(x); that is, an honest commitment with com is just a normal commitment with com. This is because we can view any x ∈ [-R, R] as an encoding (x, 1) of itself (since x = x/1 ). The only difference is that we relax the verification to accept general openings (y, d) = Encode(x) of x. Second, the fact that extracting a triple (y, d, ρ) in the Σ-protocol corresponds to extracting a valid opening (w.r.t. com) of an integer in [-R, R] becomes trivially true. It remains to check two things:

1. com must remain binding and hiding; 2. com must satisfy some homomorphic properties that we outlined above. com is binding and hiding. That com is hiding follows immediatly from the fact that com is hiding. It remains to consider binding. Suppose that an adversary finds two valid openings (y, d, ρ) and (y , d , ρ )

in [-R, R] × [1, 2 λ ] × Z q to a commitment c; that is, c = com(y • d -1 mod q; ρ) = com(y • (d ) -1 mod q; ρ ). Since com itself is binding, we must have y • d -1 = y • (d ) -1 mod q. This last equation implies yd = y d mod q =⇒ yd = y d over Z =⇒ y/d = y /d ,
where the first implication holds as long as q is chosen large enough compared to R and 2 λ , i.e., q/2 > R • 2 λ . Properties of com. First, we check some basic homomorphic properties:

-If (y, d) encodes x = y/d , then (-y, d) encodes -x. -If (y, d) encodes x = y/d and a is an integer such that ya ≤ R, then com(x) a = com(ayd -1 ) is a valid commitment com(ax). -If (y, d) encodes x = y/d and a is an integer such that y + da ≤ R, then com(x) • com(a) = com(yd -1 + a) = com((y + da)d -1 ) is a valid commitment com(x + a) since (y + da)/d = y/d + a = y/d + a.
Second, in our most optimized range proof constructions, we will reduce the task of proving that x belongs to an interval [a, b] to the task of proving that x 0 = (x -a)(b -x) is positive. To show the latter, we will prove that there exists three integers (x 1 , x 2 , x 3 ) such that 4x 0 + 1 = 3 i=1 x 3 i ; such a decomposition exists (and can be found efficiently) if and only if x 0 ≥ 0 [Gro05]. Now, suppose we extracted encodings (y, d), ((y i , d) i≤3 ) to 4x 0 + 1 and (x 1 , x 2 , x 3 ) respectively, with the following guarantee:

yd -1 = 3 i=1 (y i d -1 ) 2 mod q.
Intuitively, this guarantee will be obtained by using a standard Σ-protocol to prove knowledge of a 3-square decomposition directly over commitments with com. The extracted encodings will all have a common d, because of the structure of the extraction procedure: d corresponds simply to the difference between two distinct challenges for which the prover produced an accepting transcript. The above equation can be rewritten yd = 3 i=1 y 2 i mod q, which necessarily holds over the integers (i.e., no overflow occurs) given that 3R 2 < q/2 and 2 λ R < q/2, since the values y and y i are bounded by R and d is bounded by 2 λ . From there, dividing both sides by d 2 over the rationals, we get that y/d can we written as a sum of three squares over Q. A simple technical lemma shows that this relation over Q actually suffices to guarantee x = y/d ∈ [a, b]; we omit details in this high level overview.

Note that in related work [FSW03], a similar encoding is used to allow for homomorphic computations with bounded rationals. However in our case, bounded rationals appear as an intermediate result as extracted value (y -y ) • (d -d ) -1 mod q of the proof of knowledge. Our encoding is for small integers, hence the rounding. Also, the work [LN17] uses the fact that the extracted value is unique to construct verifiable encryption schemes. Again, the application differs.

Instantiation in the Discrete Log Setting

Equipped with a method to build bounded integer commitment schemes which satisfy some necessary properties, we turn to the problem of instantiating the construction in different settings, and building a range proof from it. In the discrete logarithm setting, we set com to be the standard Pedersen commitment scheme: com(m; r) = g m h r where (g, h) are two random generators over a group where computing discrete logarithms is hard. As for the range proof, we rely on the efficient Σ-protocol of [CPP17], adapting it to prime order group (since the scheme is described over subgroups of Z n for an RSA modulus n in [CPP17]). This is a relatively standard Σ-protocol where the prover, given an opening (x, r) for a commitment c = g x h r , commits to three values (

x 1 , x 2 , x 3 ) such that 4(x -a)(b -x) + 1 = i x 2
i , and proves knowledge of openings to x, x 1 , x 2 , x 3 such that this relation is satisfied. We provide a detailed security analysis of the resulting protocol.

The scheme of [CPP17] already includes a standard optimization for Σ-protocols, which relies on a collision-resistant hash function to compress the first flow while preserving soundness. We introduce two important additional optimizations tailored to our setting.

First Optimization. Due to our use of a group with a large order, we can actually reduce the size of the random coins used in the Pedersen commitments, at the cost of relying on the short-exponent discrete logarithm assumption (DLSE). This improves the computational efficiency, but also reduces the communication when proving knowledge of an opening. Furthermore, relying on DLSE has an important consequence: while the protocol of [CPP17] has computational soundness (and statistical zero-knowledge), we get an alternative instantiation which satisfies statistical soundness (and computational zero-knowledge).

On getting range proofs with statistical soundness. This alternative instantiation is obtained by changing the commitment as follows:

To commit to m ∈ [-R, R], sample r $ ← [1, K] and output g m h r .
Here, R is a bound on the committed messages, and K is chosen such that the shortexponent discrete log assumption, with random exponent chosen from [1, K], is believed to hold. Applying DLSE, h r is indistinguishable from a uniformly random group element (using a standard search-to-decision reduction for DLSE in prime-order groups [KK04]). Hence, the scheme remains (computationally) hiding. Furthermore, g m h r is perfectly binding: the probability (over the random choice of s such that g s = h) that there exists (m, r, m , r ) with m = m such that m + sr = m + sr is negligible by the Schwartz-Zippel lemma and a union bound (when R, K are small enough).

Therefore, using our proof system with short randomness in the Pedersen commitments, with appropriate parameter adjustment to guarantee perfect binding, we obtain a range proof with statistical soundness. We note that this is an important feature: the impossibility of getting statistical soundness with Bulletproof is discussed in Section 4.6 of the Bulletproof paper [BBB + 18]. In anonymous transaction schemes, statistical soundness is more important than statistical zeroknowledge, since the former is crucial for avoiding indetectable creation of coins (which would render the currency useless), while the second is only necessary to guarantee anonymity (without which the currency remains usable). Not getting statistical soundness was generally believed to be inherent to efficient range proofs, since very compact commitments require computational soundness; our method shows that it is actually possible to get competitive range proofs with statistical soundness. Note that there is also a natural instantiation of our approach using ElGamal encryption as the underlying commitment scheme. This also yields a statistically sound range proof but it is less efficient than the variant of this work.

Second Optimization. The scheme of [CPP17] relies on standard "flooding" to achieve statistical zero-knowledge: the value e • m, where m ∈ [-R, R] is a secret value and e ≤ 2 λ is a challenge, is masked with a random m $ ← [1, 2 λ+κ R] to ensure that em + m will be 2 -κ -close in statistical distance to the uniform distribution over [1, 2 λ+κ R]. However, it turns out that our constraints are closely related to the constraints satisfied by several Σ-protocols in the lattice setting, which also deal with careful bounds on the size of secret values. Building upon this observation, we import a standard optimization of Σ-protocols in the lattice-setting, namely, the rejection-sampling method [Lyu12]. Using rejection sampling allows different tradeoffs between the group size, the number of repetitions of the underlying protocol, and the size of the masks used to hide secret values. We show that an appropriate choice of tradeoff allows to significantly reduce the communication complexity of our protocol.

Preliminaries

Notation. In this work, we generally perform calculations in Z/qZ with representatives Z q = [-q-1 2 , q-1 2 ] for an odd modulus q ∈ N, and we identify Z q with Z/qZ, unless stated otherwise. Inside of flooring a b or rounding a b = a b + 1 2 operations, we generally have a, b in Z with division over Q, i.e. we work with the representatives and not in Z/qZ.

For some randomized algorithm A with input x, we sometimes write y ← A (x; r) for its execution with explicit randomness r. If the randomness is not explicit, we write y ← A (x) and assume that the randomness was sampled accordingly. We also write s $ ← S for sampling s uniformly random from a finite set S or d $ ← D to sample d randomly according to a given probability distribution D. Further, we often assume that some public parameters, denoted by pp, and the security parameter, denoted by λ, are implicitly passed as input to algorithms if it is clear by context.

Throughout, we write integers a ∈ Z in lower case letters, vectors as a ∈ Z n with components a i , and matrices A ∈ Z m×n in bold upper case letters. Computations on vectors are performed component-wise, unless stated otherwise. For example, for vectors a = (a

i ) i=1..n , b = (b i ) i=1..n ∈ Z n and scalar y ∈ Z, we write c = a • b = (a i • b i ) i=1..n , y B = (y bi ) i=1..n and B y = (b y i ) i=1..n .
For some constant c ∈ Z, we let by c = (c) i=1..n the vector with all components equal to c.

We denote by |x| the absolute value of x ∈ R and by

• 1 , • 2 , • ∞ the norms defined as x 1 = i |x i |, x 2 = i x 2 i , x ∞ = max i |x i | for x ∈ R m .

Hash Functions

A (keyed) hash function H is of the form H: K × {0, 1} * → {0, 1} l .
The key (i.e. the first input) to H is usually implicit, and part of the public parameters. We require keyed hash functions to achieve collision-resistance against non-uniform adversaries.

Definition 1 (CRHF). Let H: K × {0, 1} → {0, 1} l be a hash function. We call H a collisionresistant hash function (CRHF), if for all PPT adversaries A there exists a negligible function negl such that

Pr k ← K; (m 0 , m 1 ) ← A (1 λ , k): m 0 = m 1 ∧ H(k, m 0 ) = H(k, m 1 ) ≤ negl(λ).
We generally let l = 2λ since there are black box attacks (for example generic birthday attacks) that break collision resistance in expected 2 l/2 accesses, so l ≥ 2λ is necessary for achieving λ bits of security.

Commitment Schemes

A commitment scheme com with message space M com , commitment space C com and opening space R com is a 3-tuple of PPT algorithms (Setup, Commit, Verify) such that Further, we require that com statisfies the correctness, binding and hiding properties defined below. Often, d consists of the randomness used in the commitment generation, but it can include other auxiliary information.

Definition 2 (Correctness of a Commitment Scheme).

A commitment scheme com is correct if for any pp

$ ← com.Setup(1 λ ), any message m ∈ M com and for (c, d) ← com.Commit pp (m), it holds that com.Verify pp (c, d, m) = 1 -negl(λ).

Definition 3 (Hiding Property of a Commitment Scheme). A commitment scheme com is hiding if for any PPT adversary

A , it holds that Pr   pp $ ← com.Setup(1 λ ), (m 0 , m 1 , st) ← A (pp), b $ ← {0, 1}, (c, d) ← com.Commit pp (m b ), : b = b b ← A (st, c)   ≤ 1 2 + µ(λ)
for some function µ(λ) = negl(λ).

Definition 4 (Binding Property of a Commitment Scheme).

A commitment scheme com is binding if for any PPT adversary A , it holds that Pr pp

$ ← com.Setup(1 λ ), (c, d 0 , d 1 , m 0 , m 1 ) ← A (pp) : m 0 = m 1 ∧ com.Verify pp (c, d, m 0 ) = com.Verify pp (c, d, m 1 ) = 1 ≤ µ(λ)
for some function µ(λ) = negl(λ).

(Homomorphic) Integer Commitment Schemes. In this work, we are interested in integer commitment schemes which allow to commit to an integer x ∈ Z. An integer commitment scheme has message space M com = Z and allows for proving relations, such as knowledge of an opening, in a zero-knowledge manner (see section 3.3). We also establish bounded integer commitment schemes (section 4.1) where the message space is M com = {x ∈ Z | |x| ≤ R} for some upper bound R. The crucial difference between message space M com = Z q and M com = {x ∈ Z | |x| ≤ R} is: The former can have additive homomorphism (over Z q ), but only binds to a representative of x ∈ Z q , not to an integer. The latter binds to a (bounded) integer, but has limited homomorphism (over Z).

Zero-Knowledge Proofs

We define zero-knowledge with setup GenCRS, which generates a common reference string (CRS) crs ← GenCRS(pp). In this work, we only require an unstructured CRS13 . Let R be a NP-relation over a set X defining a (pp-dependent) NP-language L = {x ∈ X | ∃w : R(pp, x, w) = 1}. For simplicity, we suppress the dependency on pp when it is clear. A zero-knowledge proof system for L is a protocol between a prover P and verifier V. We write tr ← P(s), V(t) for the transcript of an interaction where P (resp. V) has input s (resp. t) and implicit inputs 1 λ , pp, crs. We write b = P(s), V(t) for the verifier's verdict b. A proof system is public coin if the verifier's messages are uniformly random and independent of the prover's messages, and the verifier outputs b = Verify(x, tr) for a PPT algorithm Verify.

Due to rejection sampling, our schemes have non-negligible correctness error.

Definition 5 (Correctness). A proof system (GenCRS, P, V) for L has correctness error γ err , or is γ err -correct, if for every adversary A

Pr pp ← GenPP(1 λ ); crs ← GenCRS(pp); (x, w) ← A (pp, crs): P(x, w), V(x) = 1] ≥ 1 -γ err (λ)
We call (GenCRS, P, V) correct if γ err = negl.

To separate (statistical) simulation and knowledge errors from hardness assumptions as much as possible, we define zero-knowledge and knowledge extraction by means of adversary advantages.

Definition 6 (HVZK).

A simulator Sim for a public coin proof system (GenCRS, P, V) for L is a PPT algorithm with input a statement x for which (pp, x, w) ∈ R and implicit inputs 1 λ , pp, crs, and output a transcript tr. Let A be a stateful algorithm and let

Real A (λ) = Pr pp ← GenPP(1 λ ); crs ← GenCRS(pp); (x, w) ← A (pp, crs); tr ← P(x, w), V(x) ; b ← A (tr): b ∧ R(x, w) = 1 Ideal A (λ) = Pr pp ← GenPP(1 λ ); crs ← GenCRS(pp); (x, w) ← A (pp, crs); tr ← Sim(x); b ← A (tr): b ∧ R(x, w) = 1 Define the advantage of A by Adv hvzk A ,P,V (λ) = Real A (λ) -Ideal A (λ).
Then Sim (and by extension (GenCRS, P, V)) is honest verifier zero-knowledge with simulation error σ err = σ err (λ), if for all PPT A we have Adv hvzk A ,P,V ≤ σ err + negl.

Definition 7 (Knowledge error). Let (GenCRS, P, V) be a public coin proof system for L . Let Ext be an expected polynomial time oracle algorithm (with oracle steps counted as one step) with implicit inputs 1 λ , pp, crs. Let A be a (probabilistic) and P * be a deterministic algorithm.

Real A (λ) = Pr pp ← GenPP(1 λ ); crs ← GenCRS(pp); (x, s) ← A (pp, crs); tr ← P * (x, s), V(x) : Verify(x, tr) = 1 Ideal A (λ) = Pr pp ← GenPP(1 λ ); crs ← GenCRS(pp); (x, s) ← A (pp, crs); (tr, w) ← Ext P * (x,s) : Verify(x, tr) = 1 ∧ R(x, w) = 1 W.l.o.g. Ext let w = ⊥ if Verify(x, tr) = 1. The advantage of (A , P * ) is Adv ke A ,P * ,V (λ) = Real A (λ) -Ideal A (λ).
A proof system has knowledge error κ err , if for any PPT A , P * we have Adv ke A ,P * ,V ≤ κ err + negl.

Our definition of knowledge error is closely related to witness extended emulation [Lin03,GI08], which also requires that an extractor produces convincing transcripts. This property is trivial to achieve in our setting, but interferes with our definition of knowledge error. All of our proof systems are Σ-protocols. Definition 8. A Σ-protocol Σ for relation R is an interactive three-move protocol consisting of four PPT algorithms (Σ.Init, Σ.Chall, Σ.Resp, Σ.Verify) between prover P holding a witness w for the statement x ∈ L and verifier V such that: Moreover, Σ must satisfy correctness and HVZK. As usual, the algorithms have implicit inputs 1 λ , pp, crs.

-Σ.Init(1 λ , w, x) → (α,
The simulators for our Σ-protocols actually show special HVZK, that is, they work given any (adversarial) challenge γ. Letting Sim pick γ $ ← [0, C] yields standard HVZK. To prove knowledge extraction, we rely on k-special soundness.

Definition 9 (k-special soundness).

A k-special soundness extractor Ext is a PPT algorithm which takes as input a set of k accepting transcripts Γ = {(α, γ i , ω i ) | Σ.Verify(x, α, γ i , ω i ) = 1} i=1..k with fixed α and pair-wise distinct challenges γ i , and outputs a valid witness w ← Ext(Γ), i.e. R(w, x) = 1.

In security proofs, k transcripts will either yield a witness or break an assumption. Formally, we consider the language L ∨ L hard instead of L . We recall how to obtain k transcripts for a special-soundness extractor as in definition 9.

Remark 1 (Getting k transcripts). If the adversary's success probability is at least k/((C + 1)), this is easily solved in expected polynomial time. Just rewind and try fresh challenge. In expected constant rewinds, a second accepting challenge γ will be found. The probability that γ was not encountered before is at least 1/k. Since k = poly in expected polynomial time, k distinct transcript are found. Thus, we can assume w.l.o.g. that we have k transcripts as in definition 9.

Instead of relying on expected polynomial time, one can reduce to strict PPT by truncation while retaining inversely polynomial advantage, but this incurs a hard to quantify loss. Alternatively, by standard arguments, e.g. the forking lemma [PS00], k rewinds yield k accepting transcripts with probability at least ( ε 2 ) k and these are as in definition 9 with probability at least

(k-1)! (ε•(C+1)) k .
Definition 10 (Fiat-Shamir Transformation). The Fiat-Shamir transformation applied to a Σ-protocol replaces the verifier's random challenge by a hash, resulting in a non-interactive proof system. Concretely, the prover computes (α, st) ← Σ.Init(w, x), then γ = H(x, α) and ω ← Resp(st, γ). This results in a non-interactive proof π = (α, w), since a verifier can check Σ.Verify(x, α, γ, ω) by recomputing γ = H(x, α). Our Σ-protocols satisfy the property, that given x, γ, ω, the unique accepting α can be computed efficiently. Thus, an alternative, often shorter, non-interactive proof π = (γ, ω) is possible. Now, the verifier computes α, and checks γ = H(x, α) and Σ.Verify(x, α, γ, ω). Security can be proven if H is modelled as a random oracle (and C is superpolynomial). The technique can be extended to work with random aborts of the prover. [Lyu09]. x 2 i Further, the integers x i can be efficiently computed. In [PS19], the runtime of finding the decomposition was improved to O(log 2 (y)/log log(y)) multiplications.

Tools in the DLOG setting

Hardness Assumptions. First, we establish the hardness assumptions that our scheme in the DLOG setting is based on (see section 5). To avoid trusted setup, we assume a deterministic family G = G λ of cyclic groups with generator g λ and known order q λ , generated by a group generator (G λ , g λ , q λ ) = GenGrp(1 λ ). For notational simplicity, we leave GenGrp implicit in the rest of the work.

Definition 11 (S-Bounded DLSE and SEI Assumption). Consider a group G of order q with generator g. Let S < q. The S-bounded DLSE assumption holds if for all PPT A there is a negligible negl such that Pr z

$ ← {0..S -1}, z ← A (g z ): z = z ≤ negl(λ)
The S-bounded short exponent indistinguishability (SEI) assumption holds if for all PPT A there is a negligible negl such that

Pr z $ ← {0..S -1} : A (g z ) = 1 -Pr z $ ← Z ord : A (g z ) = 1 ≤ negl(λ)
Throughout this work, we generally set S = 2 2λ . Note that DLOG assumption is equivalent to the q-bounded DLSE assumption.

Tools. Now, we introduce some lemmas and a commitment scheme that we later on utilize for constructing the bounded integer commitment and range proof.

Lemma 2 ([KK04]

). Let G be a group of prime order q with generator g ∈ G. For S < q/2, the S-bounded DLSE and SEI assumptions are equivalent.

We consider a Pedersen commitment scheme [Ped92] with smaller openings in exchange for a computational (instead of statistical) hiding property.

Definition 12 (Pedersen Commitments with Short Openings.). Let G be a group of prime order q. The scheme Ped consists of a 3-tuple of PPT algorithms (Ped.Setup, Ped.Commit, Ped.Verify) such that -Ped.Setup(1 λ ): samples g, h $ ← G and outputs public parameters pp = (g, h), -Ped.Commit pp (x): samples d $ ← [0, 2 2λ ] for x ∈ Z q , sets c = g x h d and outputs the pair (c, d), -Ped.Verify pp (c, x, d): [Ped92]) still achieves computational hiding: Under SEI (or equivalently DLSE), we can replace the short random exponent d in h d with a full random d $ ← [0..q -1] in a hybrid game. Now g x h d is uniformly distributed, independent of x.

outputs 1 iff c = g x h d . Using d $ ← [0, 2 2λ ] instead of d $ ← [0, q -1] (as in

Tools in the Lattice setting

Hardness Assumptions Now, we state the required hardness assumptions for section 6. Note that we generally instantiate the distribution χ of the LWE assumption with a discrete Gaussian distribution defined further below.

LWE n,m,q,χ (Normal Form) Given a random matrix A ∈ Z (m-n)×n q and a vector b ∈ Z m-n q generated according to either of the following cases:

1. b = A • s + e where s $ ← χ m-n and e $ ← χ n 2. b $ ← Z m-n q distinguish which is the case. SIS n,m,q,β (Normal Form) Given a random matrix A ∈ Z n×(m-n) q , find a non-zero z ∈ Z m s.t. z ≤ β and I n A • z = 0.
Tools. Gaussian distributions and related lemmata introduced in section 3.7, such as rejection sampling, are standard tools in the lattice setting. Now, we state the commitment scheme from which we construct a bounded integer commitment scheme.

Definition 13 (Commitments with Relaxed Opening in the Lattice Setting.). The following commitment scheme was defined in [BDL + 18] and adapted to the standard LWE setting in [YAZ + 19]. Let q ∈ N be a large enough power of a prime and n ∈ N. Let l 1 , l 2 , C ∈ poly(λ) and σ ≥ 2l 2 /π be positive integers. We define l := l 1 + l 2 + n. Let T ∈ N such that T ≥ σ √ l. The commitment scheme with M com = Z n q is defined as follows:

-Lat.Setup(1 λ ): for A 1 $ ← Z l1×(l2+n) q , A 2 $ ← Z n×l2 q , sets A = I l1 A 1 0 n×l1 I n A 2 and outputs pp = A. -Lat.Commit pp (x): for x ∈ M com , samples r $ ← D l σ , sets c = A • r + ( 0 x
) and outputs the pair ( c, ( r, 1)).

-Lat.Verify pp ( c, x, ( r, f )): for x ∈ M com with the opening ( r, f

) ∈ Z l1+n+l2 × Z checks if f • c = A • r + f • ( 0 x) r ≤ T |f | ≤ 2C
Note that a commitment has bit-size (l 1 + n) • log(q). In the following, we extract the proof of security of Lat of [YAZ + 19] from the proof of security of their zero-knowledge scheme.

Lemma 3. The commitment scheme Lat is correct.

Proof. We have f = 1 ≤ 2C, by design c = A • r + ( 0 x) and using lemma 10 also with overwhelming probability r ≤ σ √ l 1 + l 2 + n ≤ T .

Lemma 4. The commitment scheme Lat is binding under the SIS l1,(l2+n+l1),q,β assumption for any β ≥ 4CT .

Proof. Given a SIS instance

A 1 ∈ Z l1×(l2+n) q , sample A 2 $ ← Z n×l2 q and set pp = A = I l1 A 1 0 n×l1 I n A 2 .
Assume an adversary given pp can output ( c, ( r 0 , f 0 ), ( r 1 , f 1 ), x 0 , x 1 ) such that m 0 = m 1 and Lat.Verify pp ( c, x 0 , ( r 0 , f 0 )) = Lat.Verify pp ( c, x 1 , ( r 1 , f 1 )) = 1, so:

f 0 • c = A • r 0 + f 0 • ( 0 x 0 ) ∧ f 1 • c = A • r 1 + f 1 • ( 0 x 1 ) =⇒ f 1 f 0 • c = f 1 A • r 0 + f 1 f 0 • ( 0 x 0 ) ∧ f 0 f 1 • c = f 0 A • r 1 + f 0 f 1 • ( 0 x 1 ) =⇒ f 0 A • r 1 + f 0 f 1 • ( 0 x 1 ) = f 1 A • r 0 + f 1 f 0 • ( 0 x 0 ) =⇒ A • (f 0 r 1 -f 1 r 0 ) + f 0 f 1 • ( 0 x 1 -x 0 ) = 0 =⇒ I l1 A 1 • (f 0 r 1 -f 1 r 0 ) = 0 So z = (f 0 r 1 -f 1 r 0
) is a solution to the SIS instance because additionally it holds that:

f 0 r 1 -f 1 r 0 ≤ f 0 r 1 + f 1 r 0 ≤ 2 • (2CT ) ≤ β
Lemma 5. The commitment scheme Lat is hiding under the LWE l2,l1+n+l2,q,Dσ assumption.

Proof. In summary, the security of the commitment scheme Lat relies on the LWE l2,l1+n+l2,q,Dσ assumption and the SIS l1,(l2+n+l1),q,β assumption with β ≥ 4CT .

On input of LWE instance (A, b) ∈ Z (l1+n)×l2 q × Z l1+n q , sample matrix R $ ← Z l1×n q . Set B = I l1 R A U + RA L 0 n×l1 I n A L , c = b U + R • b L b L for A = A U A L and b = b U b L . Since A is random, public parameter pp = B is

Tools in the Class Group Setting

We recap the definition of class groups and present the setting considered in this work. The class group assumptions in this setting are discussed in [BFS20].

Class Groups. A class group G = Cl(∆) of an imaginary quadratic order is the quotient group of fractional ideals by principal ideals of the group Q(∆) with ideal multiplication. It is defined by its discriminant ∆ which must satisfy ∆ ≡ 1 mod 4 and -∆ must be a prime. Note that the ∆ can be generated from public coins for a given security parameters λ. We can compute bounds of the order of the group L, U ∈ poly(λ) such that 2 L ≤ ord(G) ≤ 2 U .

Further as in [DF02], we split G in two subgroups G = U × H such that U and H only contain elements of order comprised of small and large prime factors respectively. In more detail, we compute

functions l G (•), C G (•) such that C G (λ) > l G (λ), l G is a polynomial in λ with ord(U ) < l G (λ)
and ord(H) only has prime factors larger than C G . We call elements u ∈ U C G (λ)-smooth and elements h ∈ H C G (λ)-rough. This split is necessary for a statistical argument in the proof of security of a range proof scheme in this setting. We will setup group elements as public parameters that are C G (λ)-rough which can be done by taking some random group element to the power of l G (λ)!. This is feasible since l G (λ) is polynomial in λ. Also, we assume that whenever an entity receives a group element it verifies the membership in protocols.

Note that there exists an efficient algorithm for computing square roots of arbitrary elements. Thus class groups can be used to commit to dyadic rationals a 2 k for a, k ∈ Z. Applying the encoding technique from section 4, we can map dyadic rationals to unique integers while retaining homomorphic properties. This gives rise to an unbounded integer commitment scheme without trusted setup described in section 7.

Lemma 6 (Random Group Elements). For given g ∈ Cl(∆), the statistical distance of the distributions U g and

{g x | x $ ← [0, 2 U • L]} is at most L -1 .
Proof. This follows similarly as in lemma 8 and we omit the details.

Assumptions. The following assumptions are believed to hold in class groups. Note that we adapted the version of [BFS20] slightly to exclude zero solutions.14 Definition 14 (ORD). The order (ORD) assumption holds for a given group G if for any PPT adversary A it holds that

Pr   (w, α) ← A (G) w ∈ G \ {1}, 0 = |α| < 2 poly(λ) : w α = 1   ≤ µ(λ)
for some function µ(λ) = negl(λ).

Definition 15 (r-fROOT). The r-fractional root (r-fROOT) assumption holds for group G if for any PPT adversary A it holds that

Pr      g $ ← G (α, β, u) ← A (G, g) 0 = |α| < 2 poly(λ) ∈ Z |β| < 2 poly(λ) ∈ Z u ∈ G : u β = g α ∧ β gcd(α, β) = r k for k ∈ N      ≤ µ(λ)
Note that the 2-fROOT assumption is believed to hold in the setting of class groups with imaginary quadratic order.

Definition 16 (SI). The subgroup indistinguishability (SI) assumption holds for group G if for any PPT adversary

A it holds that Pr g, h 0 $ ← G, h 1 $ ← g , b $ ← {0, 1}, b ← A (G, g, h b ) : b = b ≤ 1 2 + µ(λ)
This assumption was introduced in [BG10] and instantiated in RSA groups under the quadratic residuocity assumption (or the decisional composite residuocity assumption). It was also mentioned in [BFS20] and was slightly adapted to fit their setting in class groups.

Lemma 7 (Forcing Zero Exponents). Let g, h

$ ← G = Cl(∆). For any PPT adversary A it holds that

Pr (α, β) ← A (G, g, h) |α|, |β| < 2 poly(λ) : g α = h β ∧ α = 0 ≤ µ(λ)
under the (weak) ORD and SI assumption for some function µ(λ) = negl(λ).

Proof. Let A be a successful PPT adversary on the above problem and U ∈ poly(λ) be a bound on the order of the group G, so ord(G) < 2 U . We construct an adversary B on the ORD assumption.

B receives G from the challenger, samples g $ ← G, ν ∈ [0, 2 2U +λ ], sets h = g ν and provides (G, g, h) as input to A . In return, B receives α, β and answers with α -νβ to the ORD challenger.

By the SI assumption and lemma 6, g ν is indistinguishable from an uniformly random h ∈ G. Thus A will retain a non-negligible success rate and in the event of success, it holds that |α|, |β| < 2 poly(λ) , α = 0 and g α = h β . Thus, it holds that α -νβ = 0 mod ord(g) Note that B only reveals ν mod ord(g) to A . So the particular choice of ν ∈ Z is hidden and with overwhelming probability of 2 2U +λ /2 U , it holds that α -νβ = 0 in Z.

Tools for Zero-Knowledge

As a technical tool for achieving zero knowledge, our protocols use additive masking of the witness. We recall the tools for masking here.

Lemma 8 (Masking with the Security Parameter). For any C, B, L ∈ N and fixed

x ∈ [-B, B], γ ∈ [-C, C], the distributions U = U[0, BCL] and V = {m + γ • x | m $ ← [0, BCL]} have statistical distance at most 1/L.
Rejection sampling and Gaussian noise allow to use smaller masks.

Definition 17 (Discrete Gaussian Distributions, [YAZ + 19]

). The continuous Gaussian distribution over R m centered around v ∈ R m with standard deviation σ is defined by the den-

sity function ρ m v,σ ( x) = ( 1 √ 2πσ 2 ) m e -x-v 2 2 2σ 2
. The discrete Gaussian distribution over Z m centered around v ∈ Z m with standard deviation σ is defined as -

D m v,σ ( x) = ρ m v,σ ( x)/ρ m σ (Z m ), where ρ m σ (Z m ) = x∈Z m ρ m σ (x). We write D m σ ( x) = D m 0,σ ( x) for short. Lemma 9 (Relationship between norms). For v ∈ R m , the inequalities of norms, v ∞ ≤ v 1 ≤ √ N v 2 ≤ N v ∞ ,
For any k > 0 it holds that Pr[|z| > kσ | z $ ← D σ ] ≤ 2e -k 2 2 . -For any k > 1 it holds that Pr[ z 2 > kσ √ m | z $ ← D m σ ] < k m e m 2 (1-k 2 ) .
Lemma 11 (Theorem 4.6, [Lyu12]). Let V be a subset of Z m in which all elements have • 2 norms less than T , σ ∈ R such that σ = ω(T √ log m) and h : V → R a probability distribution. Define algorithms T (resp. S ) as follows:

1. v $ ← h 2. t $ ← D m v,σ (resp. t $ ← D m σ ) 3. output ( t, v) with probability min D m σ ( t) M •D m v,σ ( t)
, 1 (resp. with probability 1/M ) Then there exists a constant M = O(1) such that the output distributions of T and S are within statistical distance 2 -ω(log m)

M

. Moreover, the probability that T outputs something is at least

1-2 -ω(log m) M .
Note that if σ = αT for some α > 0, then M = e 13.3/α+1/(2α 2 ) , the output of algorithm T is within statistical distance 2 -128 /M of the output of S and the probability that T outputs something is at least

Integer Commitments from Rounding Fractions

In this section, we introduce bounded integer commitments and motivate the construction of range proofs based on these commitments.

Bounded Integer Commitment Scheme

We introduce a commitment scheme transformation that allows to commit to bounded integers.

The core feature of this transformation is its proof-friendliness: standard Σ-protocols for proving knowledge of a square decomposition (or, more generally, any low-degree polynomial relation) with the original commitment (over a field Z q ) can be re-interpreted (with minor adaptations) as Σ-protocols for proving knowledge of a square decomposition (resp. low-degree relation) over Z with respect to the transformed commitment scheme. In addition, the transformation preserves some homomorphic properties of the underlying scheme, which turns out to be crucial in the application to range proofs.

Definition 18 (The Transformation).

Let com be a commitment scheme with message space com.M com = Z n q and opening space com.R com . We define the commitment scheme com over parameters

U, C ∈ N such that U < q-1 2 with -com.M com = { x ∈ Z n | x ∞ ≤ U/C} -com.R com = {(d, γ, y) ∈ R com × Z × Z n | γ ≤ C, y ∞ ≤ U/C} as follows: -com.Setup(1 λ ): outputs pp ← com.Setup(1 λ ).
com.Commit pp ( x): computes (c, r) ← com.Commit pp ( x) and outputs (c, (r, 1, x)). -com.Verify pp (c, x, (r, γ, y)): sets z = y • γ -1 mod q and checks x = y γ , |γ| ≤ C, γ = 0, y ∞ ≤ U/C, com.Verify pp (c, z, r) = 1 as well as x = y γ , where division is performed in Q n . Lemma 12. The commitment scheme com is correct, binding and hiding.

The correctness and hiding properties follow directly from the security of com. The binding property can be argued similarly.

Let A be a PPT adversary breaking the binding property of com. We design a PPT adversary B that breaks the binding property of com with challenger C.

On receiving pp from the challenger C, B forwards pp to A and receives (c, (d 0 , γ 0 , y 0 ), ((d 1 , γ 1 , y 1 ), x 0 , x 1 ). B sets z i = y i • γ -1 i mod q and just forwards (c, d 0 , d 1 , z 0 , z i ) to C. If A is successful, both commitments verify correctly with respect to com and x 0 = x 1 . Thus by definition of com.Verify, the verification check for the sent openings are valid with respect to the scheme com. Note that

y i ∞ ≤ U/C, |γ i | ≤ C for i ∈ [0, 1]. So y i • γ i ∞ ≤ U ≤ q-1
2 . Assume for the sake of contradiction that z 0 = z 1 :

z 0 = z 1 =⇒ y 0 • γ 1 = y 1 • γ 0 mod q =⇒ y 0 • γ 1 = y 1 • γ 0 in Q =⇒ y 0 γ 0 = y 1 γ 1 in Q =⇒ y 0 γ 0 = y 1 γ 1 in Q
This contradicts x 0 = x 1 and thus the advantage of B is the same as A .

Arguing over the Integers. Now, we motivate how to perform proofs over the integers on the example Ped. Let Ped be the scheme obtained by the above transformation applied to Ped. Let C = 2 λ determine the challenge space, S = 2 2λ determine the size of the randomness and L = 2 λ be the masking overhead. Let 2 λ = C < U ∈ N and let q be prime with 2U < q. Let G be a group of order q. For clarity, we restate the scheme:

-Ped.Setup(1 λ ): outputs pp = (g, h) $ ← G 2 . -Ped.Commit(pp, x): samples r $ ← [0, S]
and outputs (c = g x h r , (r, 1, x)).

-Ped.Verify(pp, c, x, (r, γ, y)): checks g y•γ -1 h r = c as well as x = y γ , where the division is performed in Q, |γ| ≤ C, γ = 0 and |y| ≤ U/C.

The most essential protocol is the proof of knowledge of an opening. We now establish an unoptimized version in order to gain a basic understanding of the underlying arguments. The relation we prove is R = {(c, (x, (r, γ, y))) | Ped.Verify(c, x, (r, γ, y)) = 1}.

For the correctness property, we are only interested in honest openings, so γ = 1, y = x. The proof scheme follows the conventional strategy of blinding the witnesses (x, r) with a mask. We add a size check for the masked witness to ensure the shortness of the opening. Note that the message space of Ped is {x ∈ Z | x ≤ U/C} but we can only perform proofs for smaller x values because the commitments need to stay binding after the masking process. In more detail, we let B ∈ N such that 2BCL ≤ U/C and we allow for messages |x i | ≤ B. The following protocol proves knowledge of an opening.

-Init(c, (x ∈ [-B, B], r ∈ [0, S])): m $ ← [0, BCL], s $ ← [0, SCL]; outputs d = g m h s . -Chall(): outputs γ $ ← [0, C] -Resp(γ): sets z = m + γ • x, t = s + γ • r. Outputs (z, t) -Verify(d, γ, z, t): checks |z| ≤ BCL and g z h t = d • c γ .
The first verification check succeeds with overwhelming probability since the probability that the random m is too close to BCL is small. The second check succeeds due to

g z h t = g m+γ•x h s+γ•r = g m h s • (g x h r ) γ = d • c γ .
Further, lemma 8 also implies that z, t hide the witnesses x, r statistically and using d = g z h t • c -γ , a valid transcript can be computed for a given challenge γ. Thus, the scheme honest-verifier is zero-knowledge. The following soundness argument shows how to extract correct openings.

First, let (d, γ, z, t), (d, γ , z , t ) be two accepting transcripts with γ = γ . Without loss of generality, we assume that γ > γ. We denote z = z -z, t = t -t and γ = γ -γ. We know that g z -z h t -t = c γ -γ which directly implies g z/γ h t/γ = c. Thus, γ * = γ, r * = t/γ, y * = z and x * = y * γ * is a valid opening for c. Note that the size checks are satisfied:

|γ * | ≤ C, |y * | ≤ 2BCL ≤ U/C.
Note that we know that x * is short because γ * and y * are short, so the above protocol can already be seen as range proof that guarantees that the committed value lies in 2BCL]. Nonetheless, this is not very satisfying yet because the slackness of 2CL = 2 2λ+1 is very large. But the shortness of the extracted values can be used to argue in Z instead of Z q which opens the door for more sophisticated arguments.

On Retaining Homomorphism. If the original scheme is homomorphic, the transformation retains (restricted) homomorphic properties. Firstly, if the commitments are generated honestly, the homomorphic property is retained as long as the homomorphic calculation is performed inside the bound U/C of the scheme. In case of dishonest commitments, the scheme still retains a more limited form of homomorphic properties.

If the scheme com allows for addition of constants to the committed value, the homomorphic property is retained up to overflow over the bound U/C. To illustrate, let t ∈ Z n q be some constant and c a commitment to message m = y/γ with opening (r, γ, y). Note that c commits to y/γ modulo q with respect to com and we can use the homomorphic operations. We have ( y/γ) + t = y/γ + ( t • γ)/γ = ( y + t • γ)/γ mod q and y+ t•γ γ = y/γ + t = m + t. So the result of the homomorphic operation is actually exact because the additional operand does not introduce an additional error term. Note that for the opening to be correct, the norm y + t • γ ∞ needs to be smaller than U/C. So, enough space needs to be guaranteed to perform homomorphic operations. The analysis for retaining multiplicative homomorphic properties for small constants is similar.

In the case of additive and multiplicative homomorphisms between dishonest commitments, there are some small error terms and thus, the properties do not translate as directly. For homomorphic properties between dishonest commitments, the analysis is a bit more complicated and properties do not transfer directly. We illustrate this for the additive homomorphism. Let com be additively homomorphic, so there exists a function ⊕ for all commitments c 0 , c 1 to messages m 0 , m 1 ∈ com.M com with openings r 0 , r 1 respectively, it holds that:

c = com.Commit( m 0 + m 1 , r 0 ⊕ r 1 ) = c 0 ⊕ c 1 .
Let c 0 , c 1 be commitments with messages m 0 , m 1 and valid openings (r 0 , γ, y 0 ), (r 1 , γ, y 1 ) respectively with respect to the scheme com. We set c = c 0 ⊕ c 1 . Since the commitments c 0 and c 1 are valid commitments to messages y 0 /γ (q) and y 1 /γ (q) with respect to the scheme com, c is a commitment to y = ( y 0 + y 1 )/γ (q) with opening r 0 ⊕ r 1 . The bound and non-zero check for γ succeed by definition and if y 0 + y 1 ∞ < U/C, then y passes the check as well.

The commitment will commit to m = y0+ y1 γ , where the division is performed in R n . We can write yi γ = m i + µ i for -0.5 ≤ µ i < 0.5. With this, we have

m = m 0 + m 1 + µ 0 + µ 1 .
So the homomorphic calculation is correct, if µ 0 + µ 1 rounds to 0 for each component. This is not guaranteed for all possible openings, so the homomorphic property does not translate directly in the transformation without further care. Also, in case y 0 + y 1 is larger than U/C, the result of the homomorphic operation results in commitments that do not commit to the "desired" value. For example, let y 0 + y 1 = 1/3 mod q with (non-zero) representative of 1/3 > U/C. The opening (d 0 ⊕ d 1 , 3, 1) with message 0 will be a valid opening for the commitment. Thus, the use of homomorphic operations in com need to be performed with attention to the specific setting. For range proofs, the homomorphism with small constants can be used to prove the 3-square decomposition of the integer and the complications from multiplicative and the additive homomorphic error terms can be balanced out such that we can still prove the relation with the homomorphic property of the underlying schemes.

Ensuring Membership of an Interval. We use the 3 square decomposition in order to show membership of [0, B]. This can be extended to a range proof for interval [a, b] by setting B = b -a. Since com allows for addition of constants, the prover can show x -a ∈ [0, B] =⇒ x ∈ [a, b]. Note that the values still need to lie inside the given bounds.

We are using the 3 square decomposition to show that x ∈ [0, B]. Since the extracted x is a rounded fraction, we still need to ensure that the decomposition shows the desired range membership.

Lemma 13 (Three Square for Rounded Fractions

). Let n, d ∈ Z and x = n d , {x i } i=1..3 ∈ Q and B ≥ 2. Then: 1 + 4 n d B - n d = 3 i=1 x 2 i =⇒ x ∈ [0, B]. Proof. A simple calculation shows that n d ∈ [ 1 2 (B - √ B 2 + 1), 1 2 (B + √ B 2 + 1)].
This interval can further be bound as follows:

1 2 B + B 2 + 1 = 1 2 B 1 + 1 + 1 B 2 ≤ 1 2 B 1 + 1 + 1 B 2 = B + 1 2B
A similar computation for the left bound shows that the 3-squares decomposition implies

n d ∈ [-1 2B , B + 1 2B ]. Since B ≥ 2, we find n d ∈ [-1 4 , B + 1 4 ].
Rounding leads to the desired result. (In fact, this holds even for B = 1.) Further Properties. Our adapted commitment scheme and range proofs have additional useful properties.

Remark 2 (RP for com). For denominator γ = 1, com coincides with com. Under this precondition, our range proofs establish x ∈ [0, B] for also com-commitments.

Remark 3 (Positivity). Our proofs show x ∈ [0, B]. However, in many applications, proofs of positivity (x ≥ 0) suffice. That is, B could be made into a zero-knowledge threshold (used for masking only), so that for x > B no zero-knowledge guarantees hold. 15 This change is achieved by proving 1 + 4x = 3 i=1 x 2 i . Now, soundness guarantees x ∈ [0, q-1 2 ]. Remark 4 (Denominators). A closer look at soundness shows, that a denominator γ > 1 leads to a rejection with probability 1 -1 γ . Thus, the larger γ, the less likely will a (malicious) verifier succeed.

5 Range Proof in a DLOG Setting

Overview

In this section, we present the range proof in the setting of a group G with prime order q under the DLOG (or DLSE) assumption. 16 As basis, we use Pedersen commitments Ped, which we transform in a bounded rational commitment schemes Ped as in section 4.1. Recall that the difference of Ped and Ped is mostly in the interpretation of the committed values.

Our protocol reuses the structure of existing range proofs based on Pedersen commitments in the RSA setting (see [Lip03,Gro05,CPP17]). For a given commitment c = g x h r , the prover computes the square decomposition 1 + 4(b -x)x = i=1..3 x 2 i and lets x 0 = b -x. Thus, we prove 1 + 4x 0 x = i=1..3 x 2 i . Note that all x i are in the range [0, B]. The prover commits to c i = g xi h ri for some randomly sampled r i for i ∈ [1, 3], and sets c 0 = g b c -1 . For a proof of knowledge of x i , he computes mask commitments d i = g mi h si (and an additional "garbage" term d), and sends them to the verifier. After receiving the challenge γ, the prover reveals z i = m i + γx i and t i = s i + γr i and the verifier can check whether the equation g zi h ti = c γ i d i holds (and an equation for the square decomposition). 17 The verifier checks the proof of knowledge and accepts only if z i and t i are small. As usual, if the prover can answer two different challenges γ, γ, openings can be extracted. These openings are x i = zi-zi γ-γ with short nominator and denominator, and they satisfy the square decomposition (or DLOG is broken). This shows soundness (for Ped openings), Furthermore, as we sketched in the introduction, when small exponents are used for the masking term h y , and by adjusting the parameters, soundness can actually be proven statistically. In our parameter choice, however, we will optimize for efficiency and focus on computational soundness.

For zero-knowledge, the witness is blinded by the masks m i . Since the m i 's must be small (hence are not uniform in Z q ), we do not get perfect zero-knowledge. However, x i +m i still statistically hides x i . This is enough to establish (statistical) zero-knowledge by the usual "simulation by execution in reverse". The construction and proof is somewhat complicated by using small exponents for the masking term h y , which consequently must be masked itself.

Parameters

Let pp = (g, h, q) be the public parameters of the commitment scheme Ped in group G with order q, let H : {0, 1} * → {0, 1} 2λ be a collision resistant hash function, and let [0, B] be the range with B ≥ 2. Let [0, C] be the challenge set. Let S be the size of small exponents in the SEI assumption, and let L be the growth factor of masked intervals due to additive noise, that is, masking [0, B] results in [0, BL]. We define U = 32B 2 C 2 L 2 and note that it serves as an upper bound for the integers appearing in the security proof. In particular, we require U < q-1 2 . The prover shows that he knows x, r committed in c = g x h r = Ped.Commit(x; r) and that x ∈ [0, B]. (Other commitments are interpreted as Ped)

Scheme

The scheme RP Log follows the structure of the line of work [Lip03, Gro05,CPP17]. We adapt the scheme to the DLOG setting and apply our encoding technique.

-RP Log .Init(c = g x h r , x ∈ [0, B], r ∈ [0, S]): 1. compute x i s.t. 4x(B -x) + 1 = 3 i=1 x 2 i 2. Set r 0 = -r, x 0 = B -x 3. Set c 0 = c -1 g B 4. Set ∀i ∈ [1, 3] : r i $ ← [0, S], c i = g xi h ri 5. Set ∀i ∈ [0, 3] : m i $ ← [0, BCL], s i $ ← [0, SCL], d i = g mi h si 6. Set σ $ ← [0, 4SBCL], d = h σ c 4m0 i=1..3 c -mi i 7. Set ∆ = H({d i } i=0..3 , d) 8. Outputs {c i } i=1..3 , ∆ -RP Log .Chall(): outputs γ $ ← [0, C] -RP Log .Resp(γ):
1. Sets ∀i ∈ [0, 3] :

z i = m i + γ • x i , t i = s i + γ • r i 2. Sets τ = σ + γ( i=1..3 x i r i + 4x 0 r 0 ) 3. Outputs {z i , t i } i=0..3 , τ -RP Log .Verify({c i } i=1..3 , ∆, γ, {z i , t i } i=0..3 , τ ): 1. Compute c 0 = c -1 g B 2. Compute ∀i ∈ [0, 3] : f i = g zi h ti c -γ i 3. Compute f = h τ • g γ • c 4z0 • i=1..3 c -zi i 4. Check ∆ = H({f i } i=0..3 , f ) 5. Check z i ∈ [0, BC(L + 1)]
Note that any interval [0, T ], where term T contains S, may be replaced by [0, max(q -1, T )], as these masks only serve zero-knowledge and do not affect soundness, hence wraparound is not a problem. In particular, the scheme is correct, sound and HVZK if S = q -1.

Theorem 1. The scheme RP Log is perfectly correct, i.e. has correctness error 0.

Proof. The three-square decomposition {x i } i=1..3 can be efficiently computed by lemma 1. We have x, x 0 , . . .

x 3 ∈ [0, B], γ ∈ [0, C], m i ∈ [0, BCL],
and hence z i = γx i + m i ∈ [0, BC(L + 1)]. Thus, the size check for z i never fails. Also for i ∈ [0, 3] :

F i = g zi h ti c -γ i = g mi+γ•xi h si+γ•ri (g xi h ri ) -γ = g mi h si (g xi h ri ) γ (g xi h ri ) -γ = d i
and further:

f = h τ • g γ • c 4z0 • i=1..3 c -zi i = h τ • g γ • c 4z0 • g -γ i=1..3 x 2 i • h -γ i=1..3 ri•xi • i=1..3 g -ximi • h -ri•mi = h τ • g γ • c4z 0 • g -γ•(4x(B-x)+1) • h -γ i=1..3 ri•xi • i=1..3 c -mi i = h τ • g γ • (g 4x h 4r ) m0+γ•x0 ) • g -γ•(4x(B-x)+1) • h -γ i=1..3 ri•xi • i=1..3 c -mi i = h τ • c 4m0 • g γ•(4x(B-x)+1) • h γ•4rx0 • g -γ•(4x(B-x)+1) • h -γ i=1..3 ri•xi • i=1..3 c -mi i = h τ • h γ•(4r0x0- i=1..3 ri•xi) • c 4m0 • i=1..3 c -mi i = h σ • c 4m0 • i=1..3 c -mi i = d
Theorem 2. The proof system RP Log is HVZK with simulation error 9/L. If S = q -1, this holds against unbounded adversaries. More precisely, for every HVZK adversary A , there is a SEI adversary B with roughly the same running time as A , such that Adv hvzk

A ≤ 9/L + 4Adv sei B .
Proof. First, recall that S = q -1, then Adv sei B = 0. Hence SEI is unconditionally secure and the simulation error holds against unbounded adversaries. With this, we turn to the general security reduction.

We modify the distribution of valid transcripts in four indistinguishable steps such that the last game does not require a witness as input. The simulator Sim ZK defined by game 4 fulfills the requirements of the zero-knowledge definition.

Game 1:

Outputs an unmodified transcript from an interaction of an honest verifier and prover from the definition:

-Compute x i s.t. 4x(B -x) + 1 = 3 i=1 x 2 i -Set r 0 = -r, x 0 = B -x -Set c 0 = c -1 g B -Set ∀i ∈ [1, 3] : r i $ ← [0, S], c i = g xi h ri -Set ∀i ∈ [0, 3] : m i $ ← [0, BCL], s i $ ← [0, SCL], d i = g mi h si -Set σ $ ← [0, 4SBCL], d = h σ c 4m0 i=1..3 d -mi i -Set ∆ = H({d i } i=0..3 , d) -∀i ∈ [0, 3] : z i = m i + γ • x i , t i = s i + γ • r i -τ = σ + γ( i=1..3 x i r i -4x 0 r 0 ) -Outputs {{c i } i=1..3 , ∆, {z i , t i } i=0..3 , τ } for given γ ∈ [0, C], c = g x h r , x ∈ [0, B], r ∈ [0, S].

Game 2:

Rewrites the mask commitments {d i } i=1..3 , d as in the verification check.:

-Compute x i s.t. 4x(B -x) + 1 = 3 i=1 x 2 i -Set r 0 = -r, x 0 = B -x -Set c 0 = c -1 g B -Set ∀i ∈ [1, 3] : r i $ ← [0, S], c i = g xi h ri -Set ∀i ∈ [0, 3] : m i $ ← [0, BCL], s i $ ← [0, SCL] -Set σ $ ← [0, 4SBCL] -∀i ∈ [0, 3] : z i = m i + γ • x i , t i = s i + γ • r i -τ = σ + γ( i=1..3 x i r i -4x 0 r 0 ) -Set ∀i ∈ [0, 3] : d i = g zi h ti c -γ i -Set d = h τ • g γ c 4z0 • i=1..3 c -zi i -Set ∆ = H({d i } i=0..3 , d) -Outputs {{c i } i=1..3 , ∆, {z i , t i } i=0..3 , τ } for given γ ∈ [0, C], c = g x h r , x ∈ [0, B], r ∈ [0, S].
Claim. Game 1 and Game 2 are identically distributed.

Proof. As shown in the correctness proof, it holds that

g mi h si = g zi h ti c -γ i for i ∈ [0, 3] and h σ d m0 a i=1..3 d -mi i = h τ • g γ c 4z0 • i=1..3 c -zi i .

Game 3:

Removes the dependency on x in the zero-knowledge witnesses t i , z i .τ for i ∈ [0, 3]:

-compute x i s.t. 4x(B -x) + 1 = 3 i=1 x 2 i -Set r 0 = -r, x 0 = B -x -Set c 0 = c -1 g B -Set ∀i ∈ [1, 3] : r i $ ← [0, S], c i = g xi h ri -∀i ∈ [0, 3] : z i $ ← [0, BCL], t i $ ← [0, SCL] -τ $ ← [0, 4SBCL] -Set ∀i ∈ [0, 3] : d i = g zi h ti c -γ i -Set d = h τ • g γ c 4z0 • i=1..3 c -zi i -Set ∆ = H({d i } i=0..3 , d) -Outputs {{c i } i=1..3 , ∆, {z i , t i } i=0..3 , τ } for given γ ∈ [0, C], c = g x h r , x ∈ [0, B], r ∈ [0, S].
Claim. Game 2 and Game 3 have statistical distance at most 9/L.

Proof. The claim follows from the bounds

0 ≤x i ≤ B, 0 ≤r i ≤ S, -4 • BS 2 ≤ -4x 0 r 0 ≤ i=1..3 x i r i -4x 0 r 0 ≤ i=1..3 x i r i ≤ 4 • BS
and our choice of masking. Namely, lemma 8 asserts a statistical distance of L -1 per application of masking.

Game 4:

Removes the dependency on x from the commitments:

-Set c 0 = c -1 g B -∀i ∈ [0, 3] : z i $ ← [0, BCL], t i $ ← [0, SCL] -τ $ ← [0, 4SBCL] -Set ∀i ∈ [1, 3] : r i $ ← [0, S], c i $ ← g 0 h ri -Set ∀i ∈ [0, 3] : d i = g zi h ti c -γ i -Set d = h τ • g γ c 4z0 • i=1..3 c -zi i -Set ∆ = H({d i } i=0..3 , d) -Outputs {{c i } i=1..3 , ∆, {z i , t i } i=0..3 , τ } for given γ ∈ [0, C], c = g x h r .
Claim. Game 3 and Game 4 are indistinguishable under the hiding property of the commitment scheme Ped.

Proof. We provide an algorithm B breaking the hiding property of Ped using a distinguisher A of Game 3 and Game 4. First, B sets up the parameters of the range proof with the pp = (g, h) received from the hiding challenger C . Then it computes

x i s.t. 4x(B -x) + 1 = 3 i=1 x 2
i and sends m 0 = (x 1 , x 2 , x 3 ) and m 1 = (0, 0, 0) to C . It then constructs the transcript of a proof as before utilizing the received commitments {c i } i=1..3 and sends the transcript to A . After receiving b from A it forwards the bit to the challenger C . Now, if challenger committed to m 0 , the output of B is distributed as in game 3 and otherwise as in game 4. Thus if A has non-negligible advantage, B breaks the hiding property of the commitment scheme. Note that we argue utilize the hiding property on vectors of messages which is implied by the hiding property of definition 3 for a constant vector size.

Theorem 3. Suppose L ≥ 32. The range proof RP Log for [0, B] is 2-special sound with knowledge error 1 (C+1) under DLOG and CRHF assumptions.

More precisely, for every adversary A with strict running time T there are adversaries B1, B2 with expected running time roughly 2T and

Adv ke A ≤ 1 (C+1) + Adv dlog B 1 + Adv crhf B 2 .
Proof. Assume we have two accepting transcripts for distinct challenges γ = γ with witnesses z i , t i , τ and zi , ti , τ respectively. Without loss of generality, say γ > γ. We show that either we obtain a valid witness, or we break DLOG or collision resistance. By collision resistance of H, we have d = f = f and ∀i ∈ [0, 3] :

d i = f i = fi . Denote by a the difference of a -ã for a ∈ {z i , t i , τ }. From f i = fi we find g zi h ti c -γ i = g zi h ti c -γ i ⇐⇒ g zi h ti = c γ i ⇐⇒ g zi/γ h ti/γ = c i .
Thus for all i ∈ [1, 3], we have valid openings x i = z i /γ and r i = t i /γ for commitment c i . For c 0 , we obtain c = g (γ•B-z0)/γ h -t0/γ and therefore x 0 = z 0 /γ and r 0 = t 0 /γ is an opening to c -1 g B . Moreover x = B -z 0 /γ = B -x 0 is the committed value in c. Now we turn to the square decomposition. We have

f = f =⇒ h τ • g γ • c 4z0 = i=1..3 c zi i =⇒ h τ • g γ • g 4(B-z0/γ)z0 • h 4r•z0 = i=1..3 g xi•zi h ri•zi =⇒ g γ • g 4(B-z0/γ)z0 • i=1..3 g -xi•zi = h -4r•z0 • h -τ • i=1..3 h ri•zi =⇒ g γ+4(B-z0/γ)z0- i=1..3 xi•zi = h -4r•z0-τ + i=1..3 ri•zi .
Under the DLOG assumption (or statistically, when the exponent of h remains small enough), this forces

γ + 4(B -z 0 /γ)z 0 - i=1..3 x i • z i = 0 mod q =⇒ γ + 4(B -z 0 /γ)z 0 = i=1..3 z i 2 /γ mod q =⇒ γ 2 + 4(γ • B -z 0 )z 0 = i=1..3 z i 2 mod q
The final equality holds over the integers, because all values are small enough so that there is no wrap-around. More precisely: Let K = BC(L + 1) be the maximal (accepting) value of |z i |.

For the right hand side,

|z i | ≤ |z i | + | zi | ≤ 2K and hence i=1..3 z i 2 ≤ 16K 2 ≤ U < q-1 2 .
Rewrite the left hand side as γ 2 + 4γBz 0 -z 0 2 . Shortness follows from |γ|B ≤ K and thus

K 2 + 8K 2 + 16K 2 ≤ 25K 2 ≤ U < q-1
2 . Here we use that 25K 2 = 25(BC(L + 1)) 2 ≤ 32(BCL) 2 = U since L ≥ 32.

Since the equality holds over the integers, after dividing by γ 2 it holds over Q.

Using z 0 = γ(B-x), we see that γ 2 + 4γx(γB -γx) = 3 i=1 γ 2 x 2 i and hence 1 + 4x(B -x) = 3 i=1 x 2 i for x = B -z0
γ . Now, lemma 13 finishes the proof. (Note that we extracted a valid opening for c.)

Optimizations

We discuss some optimizations to either reduce the proof size or the group size.

Rejection sampling for smaller group size. In RP Log , we hide the values γ • x i ∈ [0, BC] by an additive uniformly random mask z ∈ [0, BCL]. So the masking has an overhead of log(L) bits. By using rejection sampling for masking, as used in the lattice setting, this overhead can be traded for a (small) correctness error. For this, we apply lemma 11 instead of lemma 8. That is, we choose the mask from a discrete Gaussian distribution with large enough standard deviation σ x , and the prover aborts in Resp with (small) probability.

More concretely: Let the parameters for rejection sampling be standard deviation σ x = α • BC and M = e 13.3/α+1/(2α 2 ) for some α. Let k = √ 2λ and let L = kα . Then the probability that the mask m ← D σx is too large (and causes verification to abort) is O(2e -k 2 /2 ) = negl(λ) by lemma 10. The protocol is adapted as follows 18 :

-In Init, sample m i ← D σx for i ∈ [0, 3] (instead of m i ← [0, BCL ]).
-In Resp, abort with probability 1 -min

D σx (z i ) M •Dγ•x i ,σx (zi) , 1 for i ∈ [0, 3], -In Verify, check |z i | ≤ BC(L + 1) for i ∈ [0, 3] instead of z i ∈ [0, BC(L + 1)].
Since |m i | ≤ BCL (and thus |z i | ≤ BC(L + 1)) with overwhelming probability, the completeness is mostly affected by aborting in Resp. For the concrete value α = 256 which implies M ≈ 1.05, the abort probability is very small (roughly 0.05). The statistical distance between honest masking and "simulated" masked values is at most δ = 2 -120 , by lemma 11. Using this property the HVZK simulator is easily adapted and achieves simulation error 4δ + 5L -1 . (Note that s i and σ are sampled as before.) The soundness proof uses L but is otherwise unchanged.

To achieve non-negligible completeness, the protocol needs to be repeated, increasing computation and communication. For the Fiat-Shamir transformation, only computation increases.

Lastly, note that 2U = 32(BCL ) 2 is a lower bound on the group size q. With rejection sampling, we can choose smaller L , and hence smaller q. One can use rejection sampling for the masks σ and s i as well, but these do not affect the group size, only the communication (and the simulation error). More concretely, let σ r = α • SCL and further modify the protocol as follows:

-In Init choose s i ← D σr for i ∈ [0, 3].
-In Resp abort with probability 1 -min

D σr (t i ) M •Dγ•r i ,σr ti) , 1 for i ∈ [0, 3].
This results in a size of |t i | ≤ SCL . Also applying this to σ yields |τ | ≤ 4SBCL .

Soundness amplification for smaller group size. The soundness error of the scheme is 1/(C + 1), and since C affects U and hence the group size, decreasing it allows smaller groups. However, to achieve negligible soundness error, multiple iterations are required, namely λ/log(C) iterations for a soundness error of 2 -λ . Note that the commitments c i only need to be sent in the first repetition and can be reused in the following ones.

Efficiency

Now, we discuss the concrete efficiency of the (optimized) construction. For this we instantiate the parameters as follows:

B ∈ {2 32 , 2 64 }, C = 2 λ , L = 2 λ , S = 2 2λ , L = 256 √ 2λ .
Note that the group size is 64(BCL) 2 or, using rejection sampling for masking x i , 64(BCL ) 2 .

Optimized Non-Interactive Range Proof with Standard Soundness. An entire proof of the scheme consists of elements {c i } i=1..3 , ∆, {z i , t i } i=0..3 , τ . The proof sizes for ranges 32 and 64 bit are summarized in Table more detailed comparison with Bulletproof is given in Table 1 in the introduction, for λ ∈ {80, 128}. They were computed with a Python script presented in appendix B. The following remarks of section section 5.4 were applied on the scheme: -Rejection sampling for m i , s i , σ, -Fiat-Shamir transformation for non-interactivity.

Since z i ∈ [0, BCL ] with overwhelming probability, we calculate with this bound as opposed to the one from the scheme. Note that we use a challenge size of λ bits but for all examples, a standard group size can be achieved by utilizing a smaller challenge and repeating the proof the corresponding number of times. For U = 32(BCL ) 2 the proof size in bit is 3(log(2U )) + λ/log(C) (2λ + 4(log(BCL ) + log(SCL )) + log(4SBCL ))

Concrete parameteres and proof sizes are given in the introduction in table 1.

Computational Efficiency. We count the computational efficiency of the optimized non-interactive range proof in multiplications of group elements. Multiplications in elliptic curves are generally expensive, whereas discrete Gaussian sampling and the computation of the 3 square decomposition are comparatively insignificant, since they have a O(1) and expected O(B 2 /log(B)) complexity respectively [MW17,PS19]. The decomposition algorithm takes on average 30 ms for 500 bit values [PS19], thus accounting for the decrease in input size the decomposition will take less than 1 ms on average for 32 or 64 bit ranges 19 . Additionally, the proof might have to be aborted and rerun in case the constant M of lemma 11 is not chosen overwhelmingly close to 1. This can be ensured in exchange for slightly larger witnesses (and thus a slight increase in group size). The total probability of a rerun is about 65% with our chosen parameters of the optimized range proof. Thus, the expected number of group operations is about 1.54 of group operations of a single successful run. Note that if we only apply rejection sampling on the masks {m i } i=0..3 , the protocol needs to be repeated with a probability of 18% while keeping the same group size.

An exponentiation with a k-bit value costs on average 1.5 • k multiplications and we count inverting separately. Further, in order to speedup the calculation of a Pedersen commitment c = g x h r , we utilise the following trick. Let us assume that x > r without loss of generality. We set c = (gh) r • g x-r . Thus, the commitment is computed in 1.5 • x + 1 multiplications. Lastly, we also assume that B < λ. We disregard other possible optimizations for verification.

-The prover has to perform 2.31 • (4 log B + 8 log S + 6 log C + 7 log L ) + 30 multiplications and 1.54 inversions. -The verifier has to perform 4.5 log B + 7 log S + 13 log C + 9 log L + 10 multiplications and 6 inversions.

6 Range Proof in a Lattice Setting

Overview

We now establish a range proof protocol in the lattice setting. The setup and scheme mainly rely upon the techniques from [YAZ + 19]. In the lattice setting, we naturally deal with vectors x ∈ Z n q . Because our technique requires a large modulus q, performing one range proof at a time would waste a significant amount of space. Thus, we look at a more general batch setting, where a commitment to x ∈ Z n is given and we desire to prove x i ∈ [0, B i ] for B ∈ Z n . We write shortly x ∈ [0, B] for this statement.

We use the commitment scheme Lat defined in definition 13 and its corresponding bounded integer commitment scheme Lat as basis for the proof. The proof of knowledge of an opening of a

Lat commitment c = A • r + ( 0 x) for x ∈ [0, B], r $ ← D l
σ is performed by masking the witnesses via z = m + γ • x and t = s + γ • r and sending a commitment d = A • s + ( 0 m) of the masks in order to allow to verify the relation. Here, γ is a short challenge, m ∈ Z n q hides γ • x and the mask s is sampled from a discrete Gaussian distribution such that t is short enough to suffice as opening for the commitment and γ • r is hidden according to lemma 11.

The verifier checks the relation via A • t + ( 0 z) = d + γ • c and the binding property is retained if the verifier checks that t is indeed short. In the soundness proof, the extractor can extract the opening of the commitments via x = ( z -z) • (γ -γ) -1 and r = ( t -t) • (γ -γ) -1 given transcripts τ, τ of the proof with distinct challenges γ, γ .

For our integer commitment technique, we further require the vector z to be short. Since x will be short component-wise, we can simply verify that z is short if m is chosen short but large enough to hide γ • x according to lemma 8. In summary, with the above techniques we can show that we know openings of the commitment c ← Lat.Commit( x), c i ← Lat.Commit( x i ). We still need to prove the relation

4 x( B -x) + 1 = 3 i=1 x 2 i (2)
for x ∈ [0, B] and appropriate vectors x i . We utilize a commitment to x 0 = B -x which can be computed homomorphically. Now, the equation eq. ( 2) can be rewritten as follows:

4 x x 0 + 1 - 3 i=1 x 2 i = 0 (3)
Since the commitments are not sufficiently homomorphic to check the relation eq. ( 3) directly, we need to show the relation in a different manner. In our proof, we utilize a standard technique in lattice-based zero-knowledge proofs that allows to check the verification using the masked witnesses

z i = m i + γ • x i .
The core observation is that since z i contains x i , we can try to check the equation by replacing x i with z i in eq. ( 3). A simple calculation shows that if we also replace 1 with γ 2 and B with γ Bb, and further interpret the vector

f = 4 • z z 0 + γ 2 - i=1..3 z 2 i as polynomial f = f 2 γ 2 + f 1 γ + f 0 ∈ Z q [γ]
, the leading coefficient f 2 is equal to the left side of eq. ( 3). Since f can be computed by the verifier, it suffices that the prover proves that f is a polynomial of degree 1. This can be done by committing to the garbage terms f 0 and f 1 in c f = Lat.Commit( f 1 ; r f ) and d f = Lat.Commit( f 0 ; s f ) respectively. Now if the prover sends ( c f , d f ) and t f = s f + γ • r f to the verifier, he can verify whether indeed Lat.Commit( f ; t f ) = d f + γ c f using the additive homomorphic properties of Lat. This check ensures that f is a polynomial of degree 1. Revealing t does not reveal either opening if s is sampled by a discrete gaussian distribution according to lemma 11. Since the sampled s is short enough to suffice as opening for the commitment, the binding property is guaranteed. The commitments c f , d f are sent in the first step and the polynomial f only has 3 roots. Since γ has to be one of them and it is chosen at random by the verifier in the next step, the prover can not cheat. Note that in the proof, we denote f as z 4 in order to simplify the notation. This concludes the proof of eq. ( 2) and we can extract the witnesses of the commitments via

x i = ( z i -z i ) • (γ -γ) -1
, where γ -γ and z i -z i are short. Since the extracted elements are short, the decomposition holds over the integers and subsequently, lemma 13 yields x ∈ [0, B] after rounding.

Note that we chose this lattice setting due to complications when applying this technique to ring lattices (see appendix A for further details).

Parameters

Let n ∈ N and B ∈ Z n with B ≥ 2. Let l 1 , l 2 , C ∈ poly(λ) and l := l 1 + n + l 2 . Further, let √ l • (σ rej + C • σ) and let q = q e 0 for some prime q 0 and e ∈ N + . Let A ← Lat.Setup(1 λ ).

Further, let U = 32B 2 C 2 L 2 < q-1 2 for B = B ∞ and L ∈ N.
Hereby, the values q, n, l 1 , l 2 , C, σ, T are the parameters of the commitment scheme Lat and Lat. In addition, the value U is the size requirement parameter of the scheme Lat. The value σ rej is the standard deviation of the Gaussian distribution D σrej used to mask the opening via rejection sampling with constant M (see lemma 11). The vector B defines the range [0, B i ] for each performed range proof. The values B, L are bounds on the range and masking overhead respectively.

Scheme

The setup and scheme uses techniques from [YAZ + 19] but is adapted to proving the statement 1 + 4 x( B -x) = 3 i=1 x 2 i for x ∈ [0, B] and appropriate vectors x i .

-RP Lat .Init( c = A • r + ( 0 x), x ∈ [0, B], r $ ← D l σ ): 1. compute x i s.t. 4 x( B -x) + 1 = i=1..3 x 2 i 2. Set r 0 = -r, x 0 = B -x and c 0 = ( 0 B) -c 3. Set ∀i ∈ [0, 3] : m i $ ← [ 0, BCL] 4. Set x 4 = 4 • m 0 ( B -2 x 0 ) -2 • i=1..3 x i m i and m 4 = -4( m 0 ) 2 -i=1..3 ( m i ) 2 5. Set ∀i ∈ [1, 4] : r i $ ← D l σ 6. Set ∀i ∈ [0, 4] : s i $ ← D l σrej 7. Set ∀i ∈ [1, 4] : c i = A • r i + ( 0 x i ) 8. Set ∀i ∈ [0, 4] : d i = A • s i + ( 0 m i ) 9. Output { c i } i=1..4 , { d i } i=0..4 -RP Lat .Chall(): Output γ $ ← [-C, C] -RP Lat .Resp(γ):
1. Sets ∀i ∈ [0, 3] :

z i = m i + γ • x i 2. Set ∀i ∈ [0, 4] : t i = s i + γ • r i
3. For all i ∈ [0, 4] : abort with probability 1 -min

D l σ rej ( ti) M •D l 2 +n+l 1 γ r i ,σ rej ( ti) , 1 4. Outputs { z i } i=0..3 , { t i } i=0..4 -RP Lat .Verify({ c i } i=1..4 , { d i } i=0..4 , γ, { z i } i=0..3 , { t i } i=0..4 ): 1. Check ∀i ∈ [0, 4] : t i ≤ 2 √ l • (σ rej + C • σ) 2. Check ∀i ∈ [1, 3] : z i ∈ [ 0, BCL] 3. Set c 0 = ( 0 B) -c 4. Set z 4 = 4 • z 0 (γ B -z 0 ) + γ 2 -i=1..3 z 2 i 5. Check ∀i ∈ [0, 4] : A • t i + ( 0 z i ) = d i + γ • c i Note that we check z i ∈ [ BCL] instead of z i ∈ [ BC(L + 1)],
since rejection sampling already brings non-perfect completeness with certain parameter choices. This introduces an additional completeness error of 4/L. Theorem 4. The scheme RP Lat is correct with correctness error 1 -(1/M ) 5 + 10(2 l e -3l/2 ) + 4/L.

Proof. The three-square decomposition {x i } i=1..3 can be efficiently computed by lemma 1. We show that each check of the verifier is confirmed if both parties are honest. By definition of σ and lemma 11, the algorithm outputs something with probability 1 -(1/M ) 5 . For all i ∈ [0, 4], we have r i ≤ 2σ √ l with probability 1 -5(2 l e -3l/2 ) and thus

t i ≤ 2σ rej √ l + 2Cσ √ l = 2 √ l • (σ rej + Cσ)
with the same probability by lemma 10. Also, for i ∈ [0, 3] it holds that:

A • t i + ( 0 n z i ) = A • ( s i + γ • r i ) + ( 0 m i + γ • x i ) = (A • s i + ( 0 n m i )) + γ(A • r i + ( 0 x i )) = d i + γ • c i
By lemma 8, it holds that z i ∈ [0, BCL] for i ∈ [1, 3] with probability 1/L and because 4 x( B-x)+ 1 = i=1..3 x 2 i holds by construction, we have:

A • t 4 + ( 0 z 4 ) = A • (γ • r 4 + s 4 ) + ( 0 4 • z 0 (γ B -z 0 ) + γ 2 - i=1..3 z 2 i ) = (A • s 4 ) + ( 0 m 4 )) + γ • (A • r 4 + ( 0 z 4 )) = d 4 + γ • c 4
Theorem 5. Suppose L ≥ 16. Then RP Lat for [0, B] satisfies 3-special soundness with soundness error 2 2C+1 under the SIS l1,l,q,4CT assumption (and additionally the CRHF assumption if a hash function si used for compressing the first flow).

Proof. Assume that a PPT adversary can interactively produce three valid transcripts with challenges γ, γ , γ and witnesses [ t i , z i , t 4 ], [ t i , z i , t 4 ] and [ t i , z i , t 4 ] for i ∈ [0, 3]. We denote by a, a the difference of a -a, a -a respectively for a ∈ { t i , z i , t y }. Also, we assume without loss of generality that γ > 0, γ > 0. First, for all i ∈ [0, 4] it holds that:

A • t i + ( 0 z i ) = d i + γ • c i ∧ A • t i + ( 0 z i ) = d i + γ • c i ∧ A • t i + ( 0 z i ) = d i + γ • c i =⇒ A • t i + ( 0 z i ) = γ • c i ∧ A • t i + ( 0 z i ) = γ • c i =⇒ A • t i + γ( 0 z i /γ) = γ • c i ∧ A • t i + γ( 0 z i /γ) = γ • c i Additionally, we have t i ≤ t i + t i ≤ 4 √ l • (σ rej + C • σ) and equally t i 2 ≤ 4 √ l • (σ rej + C • σ).
Thus for i ∈ [1, 4], the commitments c i commits to message x i = z i /γ with opening ( t i , γ) and because of the binding property of Lat also

x i = z i /γ.
Similarly, we set x 0 = z 0 /γ = z 0 /γ which would be committed in c 0 if it were interpreted as Lat commitment. This shows that c is a commitment to message x = (γ • B -z 0 )/γ = B -z 0 /γ with opening ( t i , γ, γ • B -z 0 ). Note that the openings are small enough, i.e.

γ • B -z 0 ∞ ≤ 2CB + BCL ≤ 3BCL ≤ U/C, |γ| ≤ C.
Because of the binding property of Lat also x = B -z 0 /γ . All that is left to check is that x is indeed in the desired bounds. Denoting

µ i = z i -γ • x i for [i ∈ [0, 3],
we have:

z i -µ i = z i -z i + γ • x i = z i + γ • x i = γ • x i + γ • x i = (γ -γ) • x i + γ • x i = γ • x i , z i -µ i = z i -z i + γ • x i = z i + γ • x i = γ • x i + γ • x i = (γ -γ) • x i + γ • x i = γ • x i .
And with that, we can identify vectors x i in z 4 :

z 4 = 4 • z 0 (γ B -z 0 ) + γ 2 - i=1..3 z 2 i = 4 • (γ x 0 + µ 0 )(γ B -(γ x 0 + µ 0 )) + γ 2 - i=1..3 (γ x i + µ i ) 2 = 4[γ x 0 (γ B -γ x 0 -γ µ 0 ( B -2 x 0 ) -µ 0 2 ] + γ 2 - i=1..3 [(γ x i ) 2 + 2c x i µ i + µ 2 i ] = γ 2 [4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + γ[4 µ 0 ( B -2 x 0 ) -2 i=1..3 x i µ i ] -4 µ 2 0 - i=0..3 µ 2 i Setting φ = 4 µ 0 ( B -2 x 0 ) -2 i=1..3 x i µ i and ψ = -4 µ 2 0 -i=0..3 µ 2 i ,
we equally obtain:

z 4 = γ 2 [4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + γ φ + ψ z 4 = (γ ) 2 [4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + γ φ + ψ z 4 = (γ ) 2 [4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + γ φ + ψ
Further since z 4 /γ = z 4 /γ, we obtain:

z 4 -z 4 = ((γ ) 2 -γ 2 )[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + (γ -γ) φ ∧ z 4 -z 4 = ((γ ) 2 -γ 2 )[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + (γ -γ) φ =⇒ z 4 /γ = (γ + γ)[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + φ ∧ z 4 /γ = (γ + γ)[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] + φ =⇒ (γ + γ)[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] = (γ + γ)[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] =⇒ (γ -γ )[4 x 0 ( B -x 0 ) + 1 - i=1..3 x 2 i ] = 0 =⇒ 4 x 0 ( B -x 0 ) + 1 = i=1..3 x 2 i =⇒ 4 z 0 (γ B -z 0 ) + γ 2 = i=1..3 z i 2 This implies that 4 z 0 (γ B -z 0 ) + γ 2 ≥ 0 in Q n and further that x ∈ [0, B].
In more detail, we

show that both sides of the equation are short which implies that it holds over the integers. We set K = (BCL). For the right side, it holds that

i=1..3 z i 2 ∞ ≤ 3 • (2BCL) 2 = 12K 2 ≤ U ≤ q-1 2 . Similarly, 4 z 0 (γ B -z 0 ) + γ 2 ∞ ≤ 8K 2 + 16K 2 + K 2 ≤ 32K 2 ≤ U . Thus z 0 (γ B -z 0 ) + γ 2 ≥ 0 in
Q n and lemma 13 yields that x = z/γ ∈ [0, B] Theorem 6. The scheme RP Lat is HVZK under the LWE l2,l,q,σ with simulation error 4/L.

Proof. We show that the scheme is zero-knowledge by modifying an honest transcript, given the challenge γ, in 4 indistinguishable steps into a transcript that does not require the witnesses.

Game 1:

Outputs an unmodified transcript from an interaction of an honest verifier and prover from the definition:

-compute x i s.t. 4 x( B -x) + 1 = i=1..3 x 2 i -Set r 0 = -r, x 0 = B -x and c 0 = ( 0 B) -c -Set ∀i ∈ [0, 3] : m i $ ← [ 0, BCL] -Set z 4 = 4 • m 0 ( B -2 x 0 ) -2 • i=1..3 x i m i and m 4 = -4( m 0 ) 2 -i=1..3 ( m i ) 2 -Set ∀i ∈ [1, 4] : r i $ ← D l σ -Set ∀i ∈ [0, 4] : s i $ ← D l σrej -Set ∀i ∈ [1, 4] : c i = A • r i + ( 0 x i ) -Set ∀i ∈ [0, 4] : d i = A • s i + ( 0 m i ) -set ∀i ∈ [0, 3] : z i = m i + γ • x i -set ∀i ∈ [0, 4] : t i = s i + γ • r i -for all i ∈ [0, 4] : abort with probability 1 -min D l σ rej ( ti) M •D l 2 +n+l 1 γ r i ,σ rej ( ti) , 1 -outputs {{ c i } i=1..4 , { d i } i=0..4 , { z i } i=0..3 , { t i } i=0..4 } for given γ ∈ [-C, C], c ← Lat.Commit( x; r), x, r.

Game 2:

Rewrites the mask commitments as in the verification check:

-compute x i s.t. 4 x( B -x) + 1 = i=1..3 x 2 i -Set r 0 = -r, x 0 = B -x and c 0 = ( 0 B) -c -Set ∀i ∈ [0, 3] : m i $ ← [ 0, BCL] -Set z 4 = 4 • m 0 ( B -2 x 0 ) -2 • i=1..3 x i m i and m 4 = -4( m 0 ) 2 -i=1..3 ( m i ) 2 -Set ∀i ∈ [1, 4] : r i $ ← D l σ -Set ∀i ∈ [0, 4] : s i $ ← D l σrej -set ∀i ∈ [0, 3] : z i = m i + γ • x i -set ∀i ∈ [0, 4] : t i = s i + γ • r i -Set z 4 = 4 • z 0 (γ B -z 0 ) + γ 2 - i=1..3 z 2 i -Set ∀i ∈ [1, 4] : c i = A • r i + ( 0 x i ) -set ∀i ∈ [0, 4] : d i = A • t i + ( 0 n z i ) -γ • c i -for all i ∈ [0, 4] : abort with probability 1 -min D l σ rej ( ti) M •D l 2 +n+l 1 γ r i ,σ rej ( ti) , 1 -outputs {{ c i } i=1..4 , { d i } i=0..4 , { z i } i=0..3 , { t i } i=0..4 } for given γ ∈ [-C, C], c ← Lat.Commit( x; r), x, r.
Claim. Game 1 and game 2 are identify distributed.

Proof. The equalities are shown in the correctness proof.

Game 3:

Removes the dependency on the witness r i in the zero-knowledge witnesses t i for i ∈ [0, 4]:

-compute x i s.t. 4 x( B -x) + 1 = i=1..3 x 2 i -Set r 0 = -r, x 0 = B -x and c 0 = ( 0 B) -c -Set ∀i ∈ [0, 3] : m i $ ← [ 0, BCL] -Set z 4 = 4 • m 0 ( B -2 x 0 ) -2 • i=1..3 x i m i and m 4 = -4( m 0 ) 2 -i=1..3 ( m i ) 2 -set ∀i ∈ [0, 4] : t i $ ← D l σrej -Set ∀i ∈ [1, 4] : r i $ ← D l σ -set ∀i ∈ [0, 3] : z i = m i + γ • x i -Set ∀i ∈ [1, 4] : c i = A • r i + ( 0 x i ) -set ∀i ∈ [0, 4] : d i = A • t i + ( 0 n z i ) -γ • c i -for all i ∈ [0, 4] : abort with probability 1 -1/M -outputs {{ c i } i=1..4 , { d i } i=0..4 , { z i } i=0..3 , { t i } i=0..4 } for given γ ∈ [-C, C], c ← Lat.Commit( x; r), x, r.
Claim. Game 2 and game 3 are statistically indistinguishable.

Proof. We define subgames 2.i for i ∈ [-1, 4], where subgame 2.(-1) is identical to game 2 and subgame 2.i is identical to subgame 2.(i -1) for i ∈ [0, 4] but the vector t i is sampled from D l σrej and in the abortion check, the subgame aborts with probability 1 -1/M . Now, the adjacent subgames only differ in the form of a rejection sampling simulation simulation as in lemma 11 as shown in the following.

Let i ∈ [0, 4] and let A be an adversary that can distinguish subgame 2.(i-1) and subgame 2.i. We construct an adversary B distinguishing between the algorithms in lemma 11. Let h be the v), aborted ∈ {0, 1} be the output of either algorithm T or S of lemma 11, i.e. we assume if the algorithm aborts it outputs aborted = 1 and ( t, v) is invalid. The distinguisher B proceeds as in subgame 2.3 but it aborts if aborted = 1 and it instead sets t i = t and r i = v • γ -1 which is possible if γ = 0. Note that if γ = 0 the games are identically distributed if not-aborted and thus indistinguishable since the abortion probability is negligible. Now, if ( t, v), aborted is sampled as in T , the distribution is identical to subgame 2.3 and otherwise the distribution is identical to subgame 2.4. This concludes the claim.

distribution of v = γ • r i , i.e. γ ∈ [-C, C], r i $ ← D l σ . Then v ≤ T := 2pσ √ l 2 + n + l 1 by lemma 10 and thus σ rej = ω(T √ log l 2 + n + l 1 ). Let ( t,

Game 4:

Removes the dependency on the witness x i in the zero-knowledge witnesses z i for i ∈ [0, 3]:

-compute x i s.t. 4 x( B -x) + 1 = i=1..3 x 2 i -Set r 0 = -r, x 0 = B -x and c 0 = ( 0 B) -c -set ∀i ∈ [0, 3] : z i $ ← [ 0, BCL] -Set ∀i ∈ [0, 3] : m i = z i -γ • x i -Set z 4 = 4 • m 0 ( B -2 x 0 ) -2 • i=1..3 x i m i and m 4 = -4( m 0 ) 2 -i=1..3 ( m i ) 2 -set ∀i ∈ [0, 4] : t i $ ← D l σrej -Set ∀i ∈ [1, 4] : r i $ ← D l σ -Set z 4 = 4 • z 0 (γ B -z 0 ) + γ 2 -i=1..3 z 2 i -Set ∀i ∈ [1, 4] : c i = A • r i + ( 0 x i ) -set ∀i ∈ [0, 4] : d i = A • t i + ( 0 n z i ) -γ • c i -for all i ∈ [0, 4] : abort with probability 1 -1/M -outputs {{ c i } i=1..4 , { d i } i=0..4 , { z i } i=0..3 , { t i } i=0..4 } for given γ ∈ [-C, C], c ← Lat.Commit( x; r), x, r.
Claim. Game 3 and Game 4 are statistically indistinguishable.

Proof. The claim follows directly from lemma 8 applied on each coordinate and since 0 ≤ x i ≤ 2 B .

Game 5:

Removes the dependency on x i in the commitment to c i :

-Set c 0 = ( 0 B) -c -set ∀i ∈ [0, 3] : z i $ ← [ 0, BCL] -set ∀i ∈ [0, 4] : t i $ ← D l σrej -Set ∀i ∈ [1, 4] : r i $ ← D l σ -Set z 4 = 4 • z 0 (γ B -z 0 ) + γ 2 -i=1..3 z 2 i -Set ∀i ∈ [1, 4] : c i = A • r i + ( 0 0) -set ∀i ∈ [0, 4] : d i = A • t i + ( 0 n z i ) -γ • c i -for all i ∈ [0, 4] : abort with probability 1 -1/M -outputs {{ c i } i=1..4 , { d i } i=0..4 , { z i } i=0..3 , { t i } i=0..4 } for given γ ∈ [-C, C], c ← Lat.Commit( x; r), x, r.
Claim. Game 4 and Game 5 are indistinguishable under the hiding property of the commitment scheme Lat.

Proof. We define subgames 4.i for i ∈ [0, 4], where subgame 4.0 is identical to game 4 and subgame 4.i is identical to subgame 4.(i-1) for i ∈ [1, 4] but the the commitment c i = A • r i + ( 0 0) commits to 0 instead of x i .

For i ∈ [1, 4], we provide an algorithm B breaking the hiding property of Lat using a distinguisher A of subgame 4.(i-1) and subgame 4.i. First, B sets up the parameters of the range proof with the pp = B received from the hiding challenger C . Then it proceeds as in game 4.(i-1), with the adaption of c i = c for the received vector c from C on input m 0 = z 4 and m 1 = 0. Next, it sends the computed transcript to A . After receiving b from A it forwards the bit to the challenger C . Now, if challenger committed to m 0 , the output of B is distributed as in game subgame subgame 4.(i-1) and otherwise as in subgame 4.i. Thus if A has non-negligible advantage, B breaks the hiding property of the commitment scheme.

Optimizations

Rejection Sampling for z i . In the above protocol, we mask the committed values x i with a mask m i and set z i = m i + γ • x i . The mask m i is chosen such that γ • x i is statistically blinded and that the resulting masked witness is kept short. In general, we can use the rejection sampling technique (lemma 11) that is utilized for blinding the small randomness γ • r i to also blind γ • x i .

Note that x i has length n and thus M x = e 13.3 log(n) + 1 2 log 2 (n) . For a low correctness error, M needs to be minimized. For example n ≥ 140 results in a correctness error of at most 31% for all x i . If n < 140, we can group the vectors into χ = x 0 .. x 4 into a single one and blind this vector via rejection sampling. Thus, length n ≥ 140 for n ≥ 35 and the correctness error is small enough in practice.

In the case of n ≥ 140, the maximal size of the blinded vector is γ

• x i ∞ ≤ BC. Thus γ • x i 2 ≤ BC
√ n by lemma 9. According to lemma 10, we require 2 n e -3n 2 = negl(λ) in order for the bound to apply with overwhelming probability. This already holds for n ≥ 109 for λ = 128. Further, we require that σ x ≥ nBC, where σ x is the standard deviation for the discrete Gaussian distribution for rejection sampling. Under these parameters, the overhead of the masking process is L = 2n 3/2 .

In the case of 35 ≤ n < 140, we group x i in χ and apply a single rejection sampling operation. As above, we obtain the masking overhead L = 2(n ) 3/2 . For even lower batch sizes n, we can adapt the approach of the DLOG setting and sample each value separately with a sufficiently large α.

Since the maximal size of z i determines the necessary size of the modulus and thus this technique reduces the size of the scheme further. Essentially, we can set U = 32BCL .

Utilizing a Hash Function. In order to avoid sending the mask commitments d i , the prover can utilize a collision resistant hash function H : {0, 1} * → {0, 1} 2λ to fix its choice in Init. Concretely, the scheme is adapted as follows:

-Instead of outputting { d i } i=0..4 in Init, the prover sets ∆ = H({ d i } i=0..4 ), -Instead of checking ∀i ∈ [0, 4] : A • t i + ( 0 z i ) = d i + γ • c i in Verify, the verifier sets f i = A • t i + ( 0 z i ) -γ • c i and checks that ∆ = H({ f i } i=0..4 ) holds.
The collision resistance of H forces f i = d i and because ∆ was sent in Init, the prover can not cheat because he does not know the challenge yet. This technique was also used in section 5 to which we refer for details on the proof of security. Because the hash function has an image of only 2λ bits and sending 4 commitments requires (l 1 + n) log(q) bits, the size of the range proof is reduced by (l 1 + n)(2 log(B) + 4λ + 6) -2λ bit.

Non-Interactive Zero Knowledge Proof. Using the Fiat-Shamir transformation (definition 10), the scheme RP Lat or RP * Lat can be transformed into a non-interactive range. This also removes the requirement of sending the challenge and thus saves C bits of communication.

Efficient Repetitions. If the value C -1 is not negligible, the protocol needs to be repeated for N = λ log(C) rounds in order to achieve negligible soundness error. In repetitions, the values { x i } i=1..3 were already computed and committed to in { c i } i=1..3 and thus, the prover can avoid sending them again in the following repetitions. This saves (N -1) • 3(l 1 + n) log(q) bits in the proof.

Efficiency

The entire proof consists of elements { c i } i=1..4 , { d i } i=0..4 , γ, { z i } i=0..3 , { t i } i=0..4 and requires N = λ log(C) repetitions. We compute concrete parameters, including the size of the proof, with the script provided in appendix B. The following modifications from section 6.4 were applied:

-Hash function to avoid sending the mask commitments, -Avoid resending commitments c i in repetitions, For the range proof, we use the same structure as in section 5. That is, the range proof is group based, honest commitments are Pedersen commitments and the encoding uses rounding. The main technical contribution of the range proof is the proof of soundness. Again, the argument from [DF02] can be transferred to our setting, we just need to account for the additional denominator 2 k of the dyadic rationals. As before, our encoding then ensures that x ∈ [0, B].

Parameters

Let G be a class group Cl(∆). Further, let L, U be polynomial bounds with 2 L ≤ ord(G) ≤ 2 U and let l G (•), C G (•) be functions with C G (λ) > l G (λ), and l G polynomial in λ. We also define ρ = l G (λ)! for better readability. Let U, H be subgroups of G such that G = U × H where ord(U ) < l G (λ) and all prime factors ord(H) are bigger than C G (•). Let B ≥ 2, C, L be bounds for the range, challenge size and masking overhead resepectively. We set S = 2 U +λ and sample random group elements g, h that are C G (λ)-rough. Lastly, let H be a collision resistant hash function. Note that since the order of the group is unknown by assumption, there is no need for lower bounds of the order in this setting.

Scheme

We define the integer commitment scheme CG over class group group G = Cl(∆) with message space M com = Z. Essentially, we apply the encoding technique to the commitment scheme of [DF02] in order to deal with dyadic numbers in class groups without trusted setup.

The scheme is thus defined as follows:

-CG.Setup(1 λ ): outputs pp = (g, h) with randomly chosen C G (λ)-rough group elements g, h,21 -CG.Commit pp (x): samples r ← [0, 2 U +λ ], computes c = g x h r , sets d = (x, 0, r) and outputs (x, d), -CG.Verify pp (c, x, (y, , r)): verifies that the following checks pass:

c = g y 2 h r 2 , x = y 2 .
Note that the first verification check is possible because square roots are efficiently computable in class groups with imaginary order.

Note that r ← [0, S] is analogous to the DLOG setting with short exponents of size S = 2 U +λ . (Beware that U here and U in section 5 are unrelated.) Lemma 14. The commitment scheme CG is correct.

Proof. For every (g.h) ← CG.Setup(1 λ ), (c = g x h r , (x, 0, r)) ← com.Commit(x), it holds that 1 • g x h r = c and x = x 1 .

Lemma 15. The commitment scheme CG is hiding under SI assumption.

Proof. First, by the SI assumption the game is indistinguishable from a hiding game where the public parameters are chosen from the same subgroup. Since the exponent is chosen with at least λ bits more than the upper bound of the group, the element h r is statistically overwhelmingly close to a uniformly random group element of that subgroup by lemma 6. Since h r blinds the value depending on x of the commitment, namely g x , the commitment resembles a random group element of that subgroup. Indeed, the statistical distance of g x h r to a random group element is at most 2 -λ .

Lemma 16. The commitment scheme CG is binding under the ORD and SI assumption.

3. Outputs {z i , t i } i=0..3 , τ -RP CG .Verify({c i } i=1..3 , ∆, γ, {z i , t i } i=0..3 , τ ):

1. Compute c 0 = c -1 g B 2. Compute ∀i ∈ [0, 3] : Proof. This follows similarly as in theorem 1.

f i = g zi h ti c -γ i 3. Compute f = h τ • g γ • c 4z0 • i=1..3 c -zi
Theorem 8. Suppose L ≥ 32. The scheme RP CG fulfills soundness under the SI, ORD, 2-fROOT and CRHF assumptions with soundness error 1/ G (λ).

Recall that G = C + 1 by definition.

Proof. We assume we have two accepting transcripts for distinct challenges γ = γ with witnesses z i , t i , τ and zi , ti , τ respectively. Without loss of generality, say γ > γ. First, by the collision resistance of the hash function H, we have d = f = f and ∀i ∈ [0, 3] : d i = f i = fi . We denote by a the difference of a -ã for a ∈ {z i , t i , τ }. The proof of opening is similar to the argument from [DF02] (lemma 1, case 2), but adapted to the class group setting without trusted setup. We shorten some arguments and refer to the original paper for details. First, look at the following case: Assumption: ∃ i : zi γ • 2 i , ti γ • 2 i ∈ Z By the SI assumption and lemma 6, a successful PPT adversary will stay successful for g $ ← G, h ← g ν for ν ∈ [0, 2 2U +λ ] if g is C G (λ)-rough. This happens with probability at least 1/l G (λ). We assume that this is indeed the case. Thus:

f i = fi =⇒ g zi h ti c -γ i = g zi h ti c -γ i =⇒ g zi h ti = c γ i =⇒ g zi+ν•ti = c γ i
We set α i = z i + ν • t i and β i = γ. We argue that α i = 0 with overwhelmingly probability. First, a part of α i , precisely ν, is unknown to the adversary22 . Thus, the claim holds if t i = 0. If we assume the contrary, we have g zi = c γ i . Now, the 2-fROOT assumption yields a contradictions, since we assumed that there is no i : zi γ • 2 i , ti γ • 2 i ∈ Z. Thus, the 2-fROOT assumption implies that βi gcd(αi,βi) = 2 i , i ∈ N. Thus it holds that: γ 2 i = gcd(α i , γ) = gcd(α i , γ 2 i ).

So γ

2 i | z i + ν • t i . Because the concrete choice of ν is unknown to the adversary, it holds that γ 2 i | z i and γ 2 i | t i with a probability at least overwhelmingly close to 1 2 . In more detail, this can be argued as follows: Because of the assumption, γ 2 i does not divide z i and t i at the same time. Let q be some prime factor of γ 2 i such that q j is the maximal q-power dividing γ 2 i and at least one of z i and t i is non-zero modulo q j . If q j divides t i , it would also have to divide z i , contradicting the assumption. Thus t i = 0 mod q j . Note that if we write ν = n + m • ord(g), the only information the adversary receives about ν is n determined by h. So based on the above, it holds that:

ν • t i + z i = n • t i + m • ord(g) • t i + z i = 0 mod q j
Further since q ≤ γ < C λ and g is C G (λ)-rough, it holds that ord(g) = 0 mod q. For the adversary, the choice if m is now uniformly random among at least 2 2U +λ 2 U = 2 U +λ values. The equation has at most q j-1 solutions and the distribution of m is statistically close to uniform in Z q j , the probability that m satisfies the above equation is overwhelmingly close to 1/q < 1/2. So after rewinding the adversary a few times, we can check that the assumption does not hold (otherwise we could solve the 2-fROOT problem using A ).

Thus we can now safely assume for the rest of the proof that it holds that there exists an i such that zi γ • 2 i , ti γ • 2 i ∈ Z. Note that the smallest such i can be computed since the denominator γ is bounded in size. We now set µ i := g

- z i γ h - t i
γ c i which is computable since square roots can be computed efficiently in this setting. Because of the identity g zi h ti = c γ i , it holds that µ i vanishes after taking it to the power of γ = 0 as shown in the following computation:

µ γ i = g -zi h -ti c γ i = 1.
Thus it follows that µ i = 1 with overwhelming probability by the ORD assumption and we can define the opening for c i as follows:

y i := z i γ • 2 i , r i := t i γ • 2 i , x i := y i 2 i .
Now c i opens to message x i with opening (y i , i , r i ) since the verification passes:

c i • g - y i 2 i h - r i 2 i = 1 =⇒ c i = g y i 2 i h r i 2 i
Further, the message x = b -x 0 and opening (2 0 B -y 0 , 0 , -r 0 ) opens the commitment c correctly as can be verified using the identity c 0 = c -1 g B as follows:

c = c -1 0 g B = g B- y 0 2 0 h - r 0 2 0 = g 2 0 B-y 0 2 0 h - r 0 2 0
Lastly, we argue that x is indeed in the specified range. We obtain similarly as in the proof of theorem 3: Because 2 i divides γ for all i ∈ [0, 3] we can use lemma 7, and we obtain 4z 0 (B -y0 2 0 ) + γ = i=1..3 z i y i ≥ 0. After dividing out γ, we obtain:

f = f =⇒ h τ • g γ • c 4z0 • i=1..3 c -zi i = h τ • g γ • c z0 a • i=1..3 c -zi i =⇒ h τ • g γ • c 4z0 = i=1..3 c zi i =⇒ h τ • g γ • g 4z0(B-
1 + 4 y 0 2 0 (B -

y 0 2 0 ) = i=1..3 z i 2 ≥ 0
By lemma 13, this implies y0 2 0 ∈ [0, B] as claimed.

Theorem 9. The scheme RP CG is honest-verifier zero-knowledge under the hiding property of the commitment scheme CG.

Proof. This follows similarly as in theorem 2 and thus we ommit the details.

Remarks

On avoiding the indistinguishability assumption. The SI assumption is necessary to avoid avoid a trusted setup where g, h are chosen in the same subgroup but with hidden exponent. We could also use only one group element g ∈ G and define a (honest) commitment to x with randomness r as g x r where denotes bitwise concatenation. The disadvantage of this definition is that homomorphic operations are limited because the randomness can overflow into the committed value. Since our goal was to avoid scaling parameters, we chose the Pedersen format for our commitment scheme.

-

  com.Setup(1 λ ): outputs public parameters pp, -com.Commit pp (x): computes a commitment c ∈ C com to x ∈ M com with its opening d ∈ R com and outputs the pair (c, d), -com.Verify pp (c, x, d): verifies the commitment c ∈ C com to x ∈ M com with the opening d ∈ R com and outputs a bit b ∈ {0, 1}

  st): On input of statement and witness (x, w) with R(x, w) = 1, outputs a first message α and a state st. -Σ.Chall(1 λ ) → γ: Draw challenge γ uniformly from the set of challenges [0, C]. -Σ.Resp(st, γ) → ω: On input of previous state st and challenge γ, outputs a response ω. -Σ.Verify(x, α, γ, ω) → b: On input statement x and transcript α, γ, ω, accepts (b = 1) or rejects (b = 0).

Fig. 1 .ω

 1 Fig. 1. The execution of a Σ-protocol between a prover and a verifier.Prover(w,x)Commit to the mask of the witness (α, st) ← Init(1 λ , w, x)

  distributed as in Lat.Setup and in case of b = A • s + e for s $ ← D l2 σ and e $ ← D l1+n σ , c is distributed as a commitment to x and otherwise a random element of Z l1+n q .

  σ ≥ 2l 2 /π and σ rej ≥ 2C • √ l • log(l) • σ be positive integers. Let M = e

i 4 .

 4 Check ∆ = H({f i } i=0..3 , f ) 5. Check z i ∈ [0, BC(L + 1)]Theorem 7. The scheme RP CG is correct.

Table 1 .

 1 Comparison between the optimized range proof of Section 5.4 and Bulletproof [BBB+ 18] for various choices of security parameter λ and log of interval size β. Proof size and group size are in Bytes, prover and verifier work are counted as a number of group multiplications, rounded to two decimal places. See the paragraph "detailed comparison with Bulletproof" for the details on our computations.

	(β, λ)		proof size	prover work	verifier work	Group size
	(32, 80)	This Work Bulletproof	339 380	4.6k 92k	2.4k > 15k	32 20
	(32, 128)	This Work Bulletproof	501 608	7k 150k	3.7k > 25k	44 32
	(64, 80)	This Work Bulletproof	383 420	4.9k 180k	2.6k > 31k	40 20
	(64, 128)	This Work Bulletproof	545 672	7.3k 290k	3.8k > 49k	52 32

https://web.getmonero.org/resources/moneropedia/bulletproofs.html

https://github.com/BeamMW/beam

https://cointelegraph.com/news/cryptocurrency-grin-follows-through-with-anticipatedjuly-17-mainnet-hardfork

There have been several recent follow up works [HKR19,AC20] to Bulletproof, which expand the set of relations captured by the framework, but do not translate into concrete improvements on the size of the range proofs produced by this framework.

While it is theoretically possible to use a very large random integer as RSA modulus, without relying on a trusted party to compute a product of safe primes, this approach is completely impractical due to the very large group size and amount of computation, see the discussion on RSA-UFO in [LM19].

https://z.cash/technology/paramgen/

Since our bounded integer commitment scheme requires the committed values to remain into a bounded range, we actually require slightly larger group size compared to Bulletproof to achieve the same security level; this is accounted for in our concrete comparison and will be covered in details in the technical overview.

Note that the distinction between structured and unstructured random strings is crucial in real-world applications: the former unavoidably requires either a trusted third party, or a secure distributed setup. However, the latter can be instantiated in the real-world using standard heuristic "nothing-up-my-sleeve" methods.

This refers to excluding that α = 0 in the following assumptions. This condition is not checked in the definitions of [BFS20] but assumed to be true in the reductions between common RSA group assumptions, namely the adaptive root assumption and the strong RSA assumption, and the order and fractional root assumption. Further, the problems in the given assumptions would be trivial if α = 0 was accepted as solution.

In fact, masking and hence zero-knowledge degrades gracefully in the size of x.

The optimization of the Pedersen commitment scheme with short exponents relies on the SEI, which for relevant ranges is equivalent to DLSE.

In the scheme, we use a hash function to avoid having to send the mask commitments to the verifier to save space.

For more details on the technique and the proof of security, we refer to the range proof in the lattice setting of section 6. It uses rejection sampling for masking the randomness of the commitment scheme.

The average runtime was calculated as follows: 30ms • (64 2 /log2(64))/(500 2 /log2(500)).

This can be achieved by taking them to the power of l G (λ)!. Note that this procedure is still polynomial in λ due to the way l G (•) was defined.

This is explained in a similar argument further below.

Acknowledgments

We thank Muhammed Esgin for helpful comments, especially concerning the choice of parameters and for pointing out a calculation error in a previous version of this work in the lattice setting.

-Rejection sampling to mask x i , While choosing the parameters, we need to make sure that SIS l1,l,q,4CT and LWE l2,l,q,Dσ are hard to solve in practice. We adapt the approach of [YAZ + 19] for estimating the hardness of the SIS and LWE problem. In more detail, we use similar parameters for the commitment scheme and inspect the root Hermite factor (RHF) [GN08] for the respective lattice problems. To achieve 80 and 128 bit security, the corresponding RHF are 1.0048 and 1.0035 respectively. The RHF of SIS n,m,q,β and LWE n,m,q,Dσ are 2 log 2 (β) 4n log(q) and 2 log 2 (α/5.31) 4n log(q)

respectively for α = σ • √ 2π/q. The results are summarized for a range [0, B] of 32 and 64 bits in table 2. We choose C = 2 20 , C = 2 16 for λ = 80, λ = 128 respectively. Further, we choose (l 1 = 2655, l 2 = 2830), (l 1 = 3180, l 2 = 3620), (l 1 = 3120, l 2 = 3420), (l 1 = 3760, l 2 = 4510) for (λ = 80, B = 2 32 ), (λ = 128, B = 2 32 ), (λ = 80, B = 2 64 ), (λ = 128, B = 2 64 ) respectively.

Note that while [YAZ + 19] only considers a range of 1000 bits, this range is not very common in practical applications. We stress that even though our proof is amortized over a large number of range proofs for optimal use of space, the intervals defined by B do not need to be equal component-wise.

Unbounded Integer Commitments

In this section, we apply our technique to obtain range proofs in the class group setting.

Overview

The previously established commitment scheme of section 4.1 requires the parameters, especially the size of the underlying algebraic structure, to be scaled with the size of the committed integers. In this section, we establish a commitment scheme and an accompanying range proof in the class group setting without scaling parameters. The core difference to the Z q setting is that class groups allow us to commit to unbounded dyadic rationals a 2 k directly, and we have a canonical choice of representatives and absolute value for Z[1/2], unlike Z q , since there is no wrap-around to account for. Thus, the parameters of the commitment scheme do not need to be adapted to commit to larger integers, and our encoding (i.e. rounding) applies directly.

We take the commitment scheme of [DF02] as basis for our integer commitment.

[DF02] establishes an integer commitment in the form of Pedersen commitments in the RSA and class group setting, but with trusted setup. In this setting, square roots can not be efficiently computed and thus the denominator 2 k of the dyadic rational will be 1 and the commitments commit to integers directly. The arguments of [DF02] can be translated to class groups without trusted setup with some slight adaptions. 20 Thus, we again work with a form of Pedersen commitments. Our encoding maps a dyadic rational a 2 k to a 2 k . 20 In [DF02], there occurs an element of low order in the opening of a commitment. Note that the low order element is not necessary since it can not be produced efficiently under the ORD assumption in our setting.

Proof. This follows directly from lemma 7. In more detail, let A be a successful PPT adversary on the binding property of CG. We construct an adversary B on the game from lemma 7 as follows.

On input (G, g, h), the adversary B forwards pp = (g ρ , h ρ ) to A and receives (c, d 0 , d 1 , m 0 , m 1 ) such that m 0 = m 1 and c commits to m 0 , m 1 with opening (y 0 , 0 , r 0 ), (y 1 , 1 , r 1 ) respectively. B outputs

Due to the success condition of A , with non-negligible probability it holds that m i = yi 2 i for i ∈ [0, 1] and:

So we need to show that α = 0. So assume for the sake of contradiction that α = 0:

This contradiction concludes the proof.

Properties

This scheme has the same homomorphic properties as the bounded integer commitment scheme from section 4.1 with underlying additively homomorphic commitment scheme, without the risk of wrap-around. Essentially, it allows for multiplication and addition of constants and retains a limited form of an additive homomorphism, i.e. for commitment c 0 , c 1 to x 0 , x 1 the resulting commitment c 0 • c 1 will either commit to x 0 + x 1 or x 0 + x 1 + 1. Note that in case the commitments are generated honestly, the first case will hold.

Further, for a given security parameter, the parameters do not need to be scaled to the size of the committed integers while allowing for an untrusted setup.

Range Proof

For consistency with DLOG, we use B, C, L and S. As noted before, we let S = 2 U +λ . Since the group order in unknown, we have no restrictions on B, C, L, and choose L = 2 λ for strong security guarantees. However, our security proof requires challenges in [0, G -1], so we let C = G -1.

Supplementary Material

A Remark on the Ring LWE setting.

We simplify the setting and keep the details minimal, so we might skip some necessary properties of the ring R or other entities. At first, we present the basics for Ring LWE and Ring SIS and for understanding the advantage of the setting and then detail the problem of our approach in the setting.

The Ring LWE and Ring SIS problems are now defined over the ring R q . So for a random matrix

. Similarly, the Ring SIS problem asks to find a short solution z for A • z = 0. The commitment scheme of [BDL + 18] has the same structure as presented in definition 13, i.e. c = A • r + ( 0 x) for some matrix A and short vector r with entries in R q . Also, it has a relaxed opening in the form of

The structure of the zero-knowledge scheme for proving knowledge of the opening of a commitment is similar, since most needed results for the zero-knowledge can directly be translated to the different setting. For example lemma 10 and lemma 11 can just be applied on the coefficients of the polynomials which leads to identical statements. This also applies for the general structure of the range proof, only that the vectors in Z q are now vectors of polynomials in R q . The big difference is that multiplication is defined over the Ring R q and this allows for some optimizations.

An important optimization is the way the challenge space C for zero-knowledge schemes can be defined. [LS18] shows that short, non-zero elements in R q can be inverted. So setting C = {γ ∈ R q | γ short} and keeping #C ≥ 2 λ allows for proofs with negligible soundness error in one round. Since γ -γ = 0 will be short and thus invertible in R q for γ, γ ∈ C, the challenge difference can thus be used as (part of the) opening for the commitment scheme.

Further, using the NTT coefficient representation of f ∈ R q allows for efficiently proving relations in Z d q . We now assume that q ≡ 1 mod 2d. This can be generalized in order to have a slightly different vector representation in Z q . We refer to [ENS20] for more details on the NTT transformation. We identify f with its NTT representation f ∈ Z d q , where fi = f [r i ] and r i is the i-th primitive 2d-th root of unity. This representation has the convenient property that a multiplication f • g of two vectors f, g ∈ R q corresponds to a component-wise multiplication of f • ĝ. This also holds for component-wise addition. This allows us to prove the relation 4(x -a)(b -x) + 1 = 3 i=1 x 2 i in R q and retain the relation component-wise in the respective NTT vectors in Z d q . The problem is that despite γ ∈ C being short, there is no guarantee that γ is also short in Z d q . Thus we can not argue in the same way as in the standard lattice setting, where we necessarily use the fact that γ ∈ [-p, p] is short for proving that x ∈ [a, b + 1]. So in order to utilize the same range proof technique in the Ring LWE setting, we have to find a challenge space C such that elements γ ∈ C are simultaneously short in R q and their NTT representation ĉ is short in Z d q . Note that γ -γ invertible for γ, γ ∈ C is not sufficient. That is because the binding property of the commitment relies on γ -γ being short in the proof of soundness in a zero-knowledge scheme.

If C has this desired property, the verification of shortness of the masked witnesses z i = m + γ • x can directly be performed for ẑi and we could construct a range proof with the techniques introduced in this work.

B Script For Proof Size Computation

Proof Size in the DLOG Setting In the following, we supply the Python scripts that were used to calculate the proof sizes. First, we present the script used to compute the concrete proof size and determine the parameters of the scheme RP * Log defined in section 5. The following modifications to RP Log were applied:

-Rejection sampling for m i , s i , σ, -Fiat-Shamir transformation for non-interactivity. -Avoid resending commitments c i in repetitions. -----------------------------------------------# ------------------Parameters ------------------# ----------------------------------------------- -----------------------------------------------# -----------------Scheme Size ------------------# -----------------------------------------------c

Proof Size in the Lattice Setting We provide the Python script used to compute the concrete proof size and parameters of the lattice scheme RP * Lat of section 6. It checks whether the necessary hardness assumptions are fulfilled by the chosen parameters. The following optimizations from section 6.4 were used:

-Hash function to avoid sending the mask commitments. -Avoid resending commitments c i in repetitions.

-Rejection sampling to mask x i .

Listing 1.2. The Python script used to determine the parameters and compute proof size of the optimized non-interactive version of RP * Lat established in section 6 from math import c e i l , s q r t , pi , exp import math -----------------------------------------------# ------------------Parameters ------------------# ----------------------------------------------- # standard deviations a l p h a = c e i l ( q * alpha_mod ) sigma = c e i l (max( s q r t ( 2 * l 2 / p i ) , 2 * * ( q -a l p h a ) / s q r t ( 2 * p i ) ) ) s i g m a _ r e j = c e i l ( 2 * ( 2 * * C) * s q r t ( l ) * l o g ( l ) * sigma )

# Bound of the randomness of the commitment scheme T = 4 * s q r t ( l ) * ( s i g m a _ r e j +2 * * C+sigma ) # RHF for the commitment scheme 's SIS assumption SIS_RHF = g e t _ r h f _ s i s ( l 1 , l , q , 4 * ( 2 * * C) * T) # RHF for the commitment scheme 's LWE assumption LWE_RHF = get_rhf_lwe ( l 2 , l , q , sigma ) # RHF needs to be smaller than the required RHF i f LWE_RHF >= req_RHF or q > l 2 or SIS_RHF >= req_RHF : print ( " Required RHF : " + FAIL + s t r ( req_RHF ) + ENDC) print ( " LWE RHF :

" + s t r (LWE_RHF) ) print ( " SIS RHF :

" 2 6 5 5 ,3 1 8 0 ] ,[ 3 1 2 0 ,3 7 6 0 ] ] l 2 s = [ [ 2 8 3 0 ,3 6 2 0 ] ,[ 3 4 2 0 ,4 5 1 0 [ bit ]: {: -9} " . format (B) ) print ( "" ) compute_proof_size ( s e c p a r , l 1 , l 2 , C, B, r h f , alpha_mod , n ) print ( " ----------------------------------------" )