Removing the Strong RSA Assumption

from Arguments over the Integers

Geoffroy Couteau, Thomas Peters, and David Pointcheval

ENS, CNRS, INRIA, PSL Research University, Paris, France

Abstract. Committing integers and proving relations between them is an essential ingredient in many
cryptographic protocols. Among them, range proofs have shown to be fundamental. They consist in
proving that a committed integer lies in a public interval, which can be seen as a particular case of
the more general Diophantine relations: for the committed vector of integers x, there exists a vector of
integers w such that P (x, w) = 0, where P is a polynomial.
In this paper, we revisit the security strength of the statistically hiding commitment scheme over the
integers due to Damgård-Fujisaki, and the zero-knowledge proofs of knowledge of openings. Our first
main contribution shows how to remove the Strong RSA assumption and replace it by the standard RSA
assumption in the security proofs. This improvement naturally extends to generalized commitments and
more complex proofs without modifying the original protocols.
As a second contribution, we design an interactive technique turning commitment scheme over the
integers into commitment scheme modulo a prime p. Still under the RSA assumption, this results in
more efficient proofs of relations between committed values. Our methods thus improve upon existing
proof systems for Diophantine relations both in terms of performance and security. We illustrate that
with more efficient range proofs under the sole RSA assumption.

Keywords. Public-key cryptography, Commitment schemes, Interactive arguments of knowledge, Zero-

knowledge proofs, RSA assumption.

1 Introduction
Commitment Schemes. Commitments are one of the most fundamental and widely used tool
in cryptography. A commitment scheme allows a committer C holding a secret value s to send a
commitment c of s to a verifier V , and later on to open this commitment to reveal the value s. Such
a commitment should hide the committed value s to the verifier, but binds the committer in opening
only s. A famous example of commitment scheme, that perfectly hides its input, is the Pedersen
commitment scheme [Ped92], whose binding property relies on the discrete logarithm assumption:
let G be a group of prime order p with two generators (g, h). To commit to m ∈ Zp , C picks at
random r ∈ Zp and sends c = g m hr .
Okamoto and Fujisaki introduced the first integer commitment scheme [FO97], which was later
generalized in [DF02]. Unlike classical commitment schemes, an integer commitment scheme allows
C to commit to any m ∈ Z. Intuitively, this is done by committing to m in a group Zτ of unknown
order τ , where division by units cannot be performed in general.

Interactive Proofs of Knowledge. An interactive proof of knowledge is a two-party protocol

in which a prover P wants to convince a verifier V of his knowledge of some values satisfying a
public statement. It should be knowledge-extractable, which means that an extractor can get values
satisfying the statement when interacting with a successful prover, and zero-knowledge, which means
that no information about these values leaks to the verifier (except that they satisfy the statement).
Such proofs of knowledge are useful in many cryptographic constructions. Commitment schemes
are a core component of zero-knowledge proofs of knowledge. In particular, integer commitment
schemes have been extensively used in various interactive protocols involving zero-knowledge proofs
of knowledge.
 2

Assumptions for Proofs on Integer Commitments. The binding property of the Damgård-
Fujisaki commitment scheme relies on the hardness of factoring composite integers. Even though the
intractability of factoring is widely considered as a mild computational assumption, the knowledge-
extractability of the proofs using these commitments relies on the Strong-RSA assumption [BP97,
FO97], which is a much stronger assumption than the classical RSA assumption. This assumption
states that, given a composite integer n and a random element u ∈ Z∗n , it is hard to find a pair (v, e)
such that u = v e mod n. Unlike the RSA assumption [RSA78], where the exponent e > 1 is imposed,
there are exponentially many solutions to a given instance of the Strong-RSA problem, the problem
is thus easier to solve. However, these commitments still provide the best solution to prove relations
over integers.

Range Proof. The most widespread reason to work over the integers is to prove that a committed
value x lies in a public integer range Ja ; bK. Indeed, working over the integers allows to show that
x − a and b − x are positive by decomposing them as sum of four squares, following the well-
known Lagrange’s result. Lipmaa [Lip03] was the first to propose such a method by relying on a
commitment over the integers. As a consequence, the knowledge extractability of his range proof
requires the Strong-RSA assumption.

1.1 Our Contribution

First, we revisit the Damgård-Fujisaki integer commitment scheme and show that the security of
arguments of knowledge of openings can be based on the standard RSA assumption, instead of
the Strong-RSA assumption. In the reduction, we use the rewinding technique in another way than
in [DF02] as well as the splitting lemma [PS96, PS00]. Our result extends to any protocols involving
arguments or relations between committed integers which first prove the knowledge of the inputs
before proving that the relations are satisfied. This implies that the security of numerous protocols,
such as two-party computation [JS07, CPP15], e-cash [CHL05], e-voting [Gro05], secure generation
of RSA keys [JG02, DM10, HMRT12], zero-knowledge primality tests [CM99a], password-protected
secret sharing [JKK14], and range proofs [Lip03], among many others, can be proven under the
RSA assumption instead of the Strong-RSA assumption at no computational cost. In addition, we
believe that the ideas on which our proof relies could be used in several other constructions whose
security was proven under the Strong-RSA assumption, and might allow to replace the Strong-RSA
assumption by the standard RSA assumption as well.
Second, we revisit a commitment scheme which was formally introduced in [Gen04]: c = g m Rπ mod
n, for a message m ∈ Zπ and R ∈ Z∗n . It is perfectly hiding, and the binding property relies on the
RSA assumption (with modulus n, exponent π, and challenge g). We prove, as for the Damgård-
Fujisaki commitment scheme, that the security of an argument of knowledge of an opening can also
be based on the classical RSA assumption. Therefore, we identify an interesting property that is sat-
isfied by this commitment, which corresponds informally to the possibility to see this commitment
scheme either as an integer commitment scheme (i.e., c = g m hr mod n), or, after some secret has
been revealed, as a commitment scheme over Zπ for some prime π (i.e., c = g m Rπ mod n). Without
additional assumption, we show how the unpredictability of π allows improving the efficiency of zero-
knowledge arguments over the integers as the knowledge of the order π is delayed in the protocol.
This method allows to save communication and greatly reduces the work of the verifier, compared
with a classical zero-knowledge argument for the same statement. We illustrate our method on range
proofs [Lip03], a zero-knowledge argument of knowledge of an input to a commitment such that the
input belongs to some public interval.
 3

Taken together, our contributions allow us to enhance both the security, by removing the
Strong-RSA assumption, and the efficiency of numerous cryptographic protocols relying on integer
commitment schemes.

1.2 Related Works

The Damgård-Fujisaki commitment scheme [FO97,DF02] is the only known homomorphic statistically-
hiding commitment scheme over the integers. Arguments of knowledge over the integers were studied
in [Lip03, KTY04, CCT07].
Range proofs were introduced in [BCDv88]. They are a core component in numerous cryp-
tographic protocols, including e-cash [CHL05], e-voting [Gro05], private auctions [LAN01], group
signatures [CM99b], and anonymous credentials [CL01], among many others. There are two classical
methods for performing a range proof:
– Writing the number in binary notation [BCDv88, Gro11] or u-ary notation [CCs08], committing
to its decomposition and performing a specific proof for each of these commitments For example,
membership to J0 ; 2` K is proven in communication O(`/(log ` − log log `)) in the protocol of
[CCs08], and in communication O(`1/3 ) in the protocol of [Gro11] (only counting the number of
group elements).
– Using an integer commitment scheme [Bou00, Lip03, Gro05].
Note that protocols such as [CFT98] do also allow to prove that a committed integer x lies in a given
interval J0 ; aK up to an accuracy parameter δ: actually only membership to J0 ; (1 + δ)aK is proved.
Eventually, several papers have proposed signatures based on the standard RSA assumption [HW09,
HJK11,BHJ+ 13] as alternatives to classical signature schemes based on the Strong-RSA assumption.
Our work is in the same vein than these papers, replacing the Strong-RSA assumption by the RSA
assumption in arguments over the integers. However, note that we do not actually propose a new
argument system to get rid of the Strong-RSA assumption, but rather show that the security of the
classical argument system is implied by the RSA assumption. As a consequence, the schemes using
arguments over the integers do not need to be modified to benefit from our security analysis.

1.3 Organization
Section 2 introduces the necessary background for what follows, and namely some useful facts on
the RSA groups. Section 3 recalls the Damgård-Fujisaki commitment scheme, its properties, and
the argument of knowledge of [DF02]. A new security proof of the latter, under the standard RSA
assumption, is given in details in Section 4. Section 5 illustrates some extensions of our result.
First, we show how one can commit to vectors at once with generalized commitments. And then,
we show how one can make range proofs under the standard RSA assumption. Section 6 revisits the
commitment scheme of [Gen04] and shows how, by switching from the previous commitment to this
one, we can get a new interactive proof system for performing zero-knowledge arguments over the
integers, that is more efficient. Eventually, Section 7 illustrates our method on range proofs, with
concrete efficiency comparisons.
For the sake of completeness, in the Appendix A we exhibit a flaw in the optimized version of
Lipmaa’s range proof [Lip03, Annex B]. We then propose a fix as well as security proof.

2 Backgrounds
Throughout this paper, κ denotes the security parameter. An algorithm is efficient when it runs in
polynomial time in the (implicit) security parameter κ. A positive function f is negligible if for any
 4

polynomial p there exists a bound B > 0 such that, for any integer k ≥ B, f (k) ≤ 1/|p(k)|. An
event depending on κ occurs with overwhelming probability when its probability is at least 1 − ε(κ)
for a negligible function ε.

2.1 Notations
Given a finite set S, the notation x ←R S means a uniformly random assignment of an element of S
to the variable x, then for any s ∈ S we have PrS [x = s] = 1/#S where #S denotes the cardinality
of S. When an element s is represented by an integer, |s|b is the bit-length of the integer, and |s|
denotes its absolute value (or norm). Bold variables denote vectors. For a vector x = (x1 , · · · , x` ),
g x denotes (g x1 , · · · , g x` ) and kxk∞ = max1≤i≤` |xi |.
The integer range Ja ; bK stands for {x ∈ Z | a ≤ x ≤ b}. For any integers a ≤ b, the statistical
distance
Pb between two uniform distributions, Pa over Ua = J1 ;P
aK and Ub = J1 ; bK respectively, is given
by i=1 | PrUa [x = i] − PrUb [x = i]| = i=1 (1/a − 1/b) + bi=a+1 1/b = 2(b − a)/b.

2.2 Commitment Scheme

We first recall the basic definition of a commitment scheme on the message space M . This is an
essential primitive in cryptography, that is used to lock a value in a box, so that the sender cannot
change at the opening time (the binding property) but still the receiver has no information about
the value before the opening (the hiding property). A non-interactive commitment scheme is defined
by three algorithms (Setup, Commit, Verify):
– Setup(1κ ), generates the public parameters pp, which also specifies the message space M , the
commitment space C , the opening space D, and the random source R;
– Commit(pp, m; r), given the message m ∈ M and some random coins r ∈ R, outputs a
commitment-opening pair (c, d). When there is no ambiguity, we will abuse the notation (c, d) ←R
Commit(m), for pp and r ←R R;
– Verify(pp, c, d, m), outputs a bit whose value depends on the validity of the opening (m, d) with
respect to the commitment c.
A commitment scheme must be
Correct. For any public parameters pp ←R Setup(1κ ), any message m ∈ M , and any random coin
r ∈ R, if (c, d) ← Commit(pp, m; r), then we necessarily have Verify(pp, c, d, m) = 1.
Hiding. No probabilistic polynomial-time adversary A , that is first given pp ←R Setup(1κ ), can
distinguish commitments on two messages (m0 , m1 ) of its choice. The commitment scheme is
said statistically hiding if the indistinguishability holds even for unbounded adversaries.
Binding. No probabilistic polynomial-time adversary A can open a commitment c on two different
messages m0 6= m1 . The commitment scheme is said statistically binding if this is infeasible even
for unbounded adversaries.
A commitment scheme can also be homomorphic, if for a group law ⊕ on the message space M ,
from pp, (c0 , d0 ) ← Commit(pp, m0 ; r0 ) and (c1 , d1 ) ← Commit(pp, m1 ; r1 ), one can generate c and d
so that Verify(pp, c, d, m0 ⊕ m1 ) = 1.

2.3 Interactive Proof Systems

We now recall the second tool we will use in this paper, the zero-knowledge proofs of knowledge,
and their variants.
 5

Zero-Knowledge Proofs and Arguments. Let R be an NP-relation over a set X defining an

NP-language L = {x ∈ X | ∃w, R(x, w) = 1}, where a w such that R(x, w) = 1 is called a witness
for the statement x ∈ L .
A zero-knowledge proof of knowledge (ZKPoK) for a relation R and a word x ∈ X is an interactive
protocol hP(w), V i(x ∈ L ) between a prover P holding a witness w for the statement x ∈ L , and a
verifier V , both modeled as interactive probabilistic polynomial-time Turing machines. The purpose
of a ZKPoK is for P to convince V of its knowledge of some witness w of the statement x ∈ L ,
without revealing any information about this witness. More formally, let ViewV [hP(w), V i(x ∈ L )]
be the view of V during the execution of the interactive protocol (i.e., all the messages it received
when interacting with P). A ZKPoK must be:
Correct. For every x ∈ L , if P knows a witness w, and both P and V behave honestly,
hP(w), V i(x ∈ L ) is accepted by V with overwhelming probability.
Knowledge Extractable. For any prover P’ which succeeds in convincing V of x ∈ L with non-
negligible probability, there exists a simulator SimKE , running in expected polynomial time,
which extracts a witness w for x ∈ L from P’.
Zero-Knowledge: For any verifier V ’, there exists a simulator SimZK such that for every x ∈ L ,
SimZK (x) and ViewV 0 [hP(w), V 0 i(x ∈ L )], where w is a witness for x ∈ L , are indistinguish-
able.
If the knowledge-extractability holds only for a computationally-bounded P 0 , the protocol is a
zero-knowledge argument of knowledge (ZKAoK). If the verifier is restricted to being honest in the
zero-knowledge property, the proof is an honest-verifier zero-knowledge proof.

Zero-Knowledge Arguments from Diophantine Relations. A Diophantine set S ⊆ Zk is a

set of vectors over Zk defined by a representing polynomial PS (X, W ) with X = (X1 , · · · , Xk ) and
W = (Y1 , · · · , Y` ), i.e. a set of the form S = {x ∈ Zk | ∃w ∈ Z` , PS (x, w) = 0} for some polynomial
PS . It was shown in [DPR61] that any recursively enumerable set is Diophantine. An interesting
class for cryptographic applications is the class D of Diophantine sets S such that each x ∈ S has
O(1)
at least one witness w satisfying kwk∞ ≤ kxk∞ . It is widely conjectured that D = NP, as D
contains several NP-complete problems, and it was shown in [Pol03] that if co-NLOGTIME ⊆ D,
then D = NP. The class D was introduced in [AM76] and its cryptographic relevance was pointed
out in [Lip03]. For example, the set Z+ of positive integers is in D, as by a well-known result of
Lagrange, it can be defined as Z+ = {x ∈ Z | ∃(w1 , w2 , w3 , w4 ) ∈ Z4 , x − (w12 + w22 + w32 + w42 ) = 0}.
In addition, each wi is of bounded size |wi | ≤ |x|.
Lipmaa [Lip03] has shown that zero-knowledge arguments of membership to a set S ∈ D, with
representing polynomial P over k-vector inputs and `-vector witnesses, can be constructed using an
integer commitment scheme, such as [DF02]. The size of the argument (the communication between
P and V ) depends on k, `, and deg(P ), the degree of P . As noted in [Lip03], intervals, unions of
intervals, exponential relations (i.e., set of tuples (x, y, z) such that z = xy ) and gcd relation (i.e.,
set of tuples (x, y, z) such that z = gcd(x, y)) are all in D, with parameters (k, ` and deg(P )) small
enough for cryptographic applications.

2.4 RSA Group Structure

In this paper we focus on Z∗n for a strong RSA modulus n = pq where p, q are distinct safe primes.
That means that p = 2p0 + 1 and q = 2q 0 + 1 for two other primes so that p, p0 , q, q 0 are all distinct,
and ϕ(n) = 4p0 q 0 . We write a = b mod n to specify that a = b in Zn and we write a ← [b mod n] to
affect the smallest positive integer to a so that a = b mod n.
 6

By GenMod(1κ ), we denote a probabilistic efficient algorithm that, given the security parameter
κ, generates a strong RSA modulus n and secret parameters (p, q) of at least κ bits each with the
specification that n = pq. In the following, we write (n, (p, q)) ←R GenMod(1κ ). We will sometimes
abuse the notation n ←R GenMod(1κ ) to say that the modulus n has been generated according to
this distribution.

The RSA Assumption. The RSA assumption states, informally, that given an exponent e prime
to ϕ(n), it is hard for any probabilistic polynomial-time algorithm to find the e-th root modulo n of
a random y ←R Z∗n . More formally, let Pn be the subset of Zn of elements prime to ϕ(n). The RSA
assumption does in fact refer to a class of assumptions, depending of the distribution D n over Pn
from which the exponent e is drawn.

D n -RSA Assumption [RSA78]. For n ←R GenMod(1κ ) and e ←R D n , it is hard for any proba-
bilistic polynomial-time algorithm to find the e-th root modulo n of a random y ←R Z∗n . The
triple (n, e, y) is the RSA instance.

Various flavours of the RSA assumption are standard in the literature. In particular, the RSA as-
sumption with a fixed small exponent (the most common being 65537) is widely used in practical
implementations. In theoretical papers, it is common to consider the RSA assumption for exponents
picked from the uniform distribution over Pn (see [HW09] for example). In this paper, we use a
flavour of the RSA assumption which is somewhat intermediate between these two standard vari-
ants: we will consider the RSA assumption for exponents picked from the uniform distribution over
J3 ; aK ∩ Pn for a value a polynomial in κ (hence, we consider random small exponents). To simplify
the notations, we will denote a-RSA this variant of the RSA assumption1 .

Other Computational Assumptions. Other famous computational assumptions over RSA groups
are the intractability of the factorization and the Strong-RSA assumption:

Integer Factorization Assumption. It states that finding a non-trivial factor of n ←R GenMod(1κ )

is hard for any probabilistic polynomial-time algorithm.
Strong-RSA Assumption [BP97, FO97]. It lets the choice of e to the algorithm: It states that,
for n ←R GenMod(1κ ), this is hard to find the e-th root modulo n, for a random y ←R Z∗n , for
any probabilistic polynomial-time algorithm, for an exponent e > 1 of its choice.

It is well-known that breaking the integer factorization assumptions allows to break both the RSA
and the Strong-RSA assumption. From the definition, it is clear that the Strong-RSA assumption gives
more degree of freedom to the adversary, so it is way stronger. Indeed, for the RSA assumption, the
exponent is not chosen by the adversary, but can be fixed in any way in advance by the challenger.

Properties of Strong RSA Groups. One can note that in groups modulo n, where n = pq is a
strong RSA modulus, p and q are Blum primes: p = q = 3 mod 4. If we denote QRn the subgroup
of the squares, QRn = {a ∈ Z∗n | ∃b ∈ Z∗n , a = b2 mod n}, this is a cyclic subgroup of Z∗n of order
ϕ(n)/4 = p0 q 0 .
Proposition 1. The following facts hold:
1. −1 6∈ QRn ;
2. any square h ∈ QRn has four square roots, with exactly one in QRn ;
1
It should be noted that in our proof, the bound a will depend on the success probability of the adversary.
 7

3. for a random element h ∈ QRn , finding a square root of h is equivalent to factoring the modulus
n;
4. for random elements g, h ∈ QRn , finding non-zero integers a, b such that g a = hb mod n is
equivalent to factoring the modulus n;
0
5. for an RSA instance (n, e, y), finding x ∈ Z∗n and e0 prime to e such that xe = y e mod n is
equivalent to finding an e-th root of y modulus n.

Proof. Let us briefly explain why these facts hold, using the Jacobi symbol function Jn (x) = Jp (x) ×
Jq (x) in Z∗n , as the extension of the Legendre symbol on Z∗p for prime p, Jp (x) = (x)(p−1)/2 , which
determines whether x is a square or not in Z∗p . Since p and q are Blum primes, Jp (−1) = Jq (−1) = −1,
and so Jn (−1) = 1, but −1 is not in QRn , hence the Fact 1. The four square roots of 1, in Z∗n are
1 and −1, both with Jacobi symbol +1, but respectively (+1, +1) and (−1, −1) for the Legendre
symbols in Z∗p and Z∗q , and α, and −α, both with Jacobi symbol -1, but respectively (+1, −1) and
(−1, +1) for the Legendre symbols in Z∗p and Z∗q . As a consequence, given a square h ∈ QRn , and a
square root u, the four square roots are u, −u, and αu, −αu, one of which being in QRn , since the
four kinds of Legendre symbols are represented. This leads to the Fact 2.
For Fact 3, if one chooses a random u ∈ Z∗n and sets h = u2 mod n, Jn (u) is completely hidden.
Another square root v has probability one-half to have Jn (v) = −Jn (u). This means that u2 =
v 2 mod n, but u 6= ±v mod n. Then, gcd(u − v, n) gives a non-trivial factor of n.
For Fact 4, if one chooses a random u ∈ Z∗n and a large random scalar α and sets h = u2 mod n
and g = hα mod n, h is likely a generator of QRn , and then g a = hb mod n means that m = b − aα
is a multiple of p0 q 0 , the order of the subgroup of the squares. Let us note m = 2v · t, for an odd
t, then p0 q 0 divides t: let us choose a random element u ∈ Z∗n , with probability close to one-half,
Jn (u) = −1, and so Jn (ut ) = −1 while ut is a square root of 1. As in the proof of the previous
Fact 3, we can obtain a non-trivial factor of n.
0
Eventually, for Fact 5, using Bézout relation ue + ve0 = 1, then xve = y ve = y 1−ue mod n. So
y = (xv y u )e mod n.

3 Commitment of Integers Revisited

In [FO97], Okamoto and Fujisaki proposed a statistically-hiding commitment scheme allowing com-
mitment to arbitrary-size integers. Their commitment was later generalized in [DF02]. It relies on the
fact that when the factorization is unknown, it is infeasible to know the order of the sub-group QRn
of the squares in Z∗n , where n is a strong RSA modulus. Hence, the only way for a computationally-
bounded committer to open a commitment is to do it over the integers.
In addition, [FO97] gave an argument of knowledge of an opening of a commitment and proved
that the knowledge extractability of the argument is implied by the Strong-RSA assumption. A flaw
in the original proof was later identified and corrected in [DF02]. We will revisit the argument of
knowledge of an opening due to Damgård-Fujisaki [DF02] and provide a new proof for its knowledge
extractability, in order to remove the requirement of the Strong-RSA assumption. Our proof requires
the standard RSA assumption only, with an exponent randomly chosen in a polynomially-bounded
set.

3.1 Commitments over the Integers

Description. Let us recall the commitment of one integer m:

– Setup(1κ ) runs (n, (p, q)) ←R GenMod(1κ ), and picks two random generators g, h of QRn . It
returns pp = (n, g, h);
 8

– Commit(pp, m; r), for pp = (n, g, h), a message m ∈ Z, and some random coins r ←R J0 ; nK,
computes c = g m hr mod n, and returns (c, d) with d = r;
– Verify(pp, c, d, m) parses pp as pp = (n, g, h) and outputs 1 if c = ±g m hd mod n and 0 otherwise.
One should note that an honest user will always open such that c = g m hd mod n. But the knowledge-
extractability of the next ZKAoK of opening cannot exclude the change of sign. In this description,
we provide a trusted setup algorithm. But as we see below, the guarantees for the prover (the hiding
property of the commitment) just rely on the existence of α such that g = hα mod n. For the verifier
to be convinced, one can just let him generate the parameters (n, g, h), and prove the existence of
such an α to the prover.

Security Analysis. The above commitment scheme is obviously correct. The hiding property relies
on the existence of α such that g = hα mod n (they are both generators of the same subgroup QRn ),
and so, for any m0 ∈ Z,
0 0
c = Commit(pp, m; r) = g m hr = hr+αm = h(r+α(m−m ))+αm
0 0
= g m hr+α(m−m ) = Commit(pp, m0 ; r0 ),

with r0 ← [r + α(m − m0 ) mod p0 q 0 ], that is smaller than n and follows the same distribution
than r. The binding property relies on the Integer Factorization assumption: indeed, from two
different openings m0 , d0 , m1 , d1 for a commitment c, with d1 > d0 , the validity checks show that
g m0 hd0 = ±g m1 hd1 mod n, and so g m0 −m1 = ±hd1 −d0 mod n. Since g and h are squares, and −1
is not a square, necessarily g m0 −m1 = hd1 −d0 mod n. The Fact 4 from Proposition 1 leads to a
non-trivial factor of n.

3.2 Zero-Knowledge Argument of Opening

Let us now study the argument of knowledge of a valid opening for such a commitment. The common
inputs are the public parameters pp and the commitment c = g x hr mod n, together with the bit-
length kx of the message x, that is then assumed to be in J−2kx ; 2kx K, while r ∈ J0 ; nK and x are
the private inputs, i.e. the witness of the prover. We stress that kx is chosen by the prover, since
this reveals some information about the integer x, while r is always in the same set, whatever the
committed element x is.

Description of the Protocol. The protocol works as follows:

Initialize: P and V decide to run the protocol on input (pp, κ, c, kx );
Commit: P computes d = g y hs mod n, for randomly chosen y ←R J0 ; 2kx +2κ K and s ←R J0 ; 2|n|b +2κ K,
and sends d to the V ;
Challenge: V outputs e ←R J0 ; 2κ K;
Response: P computes and outputs the integers z = ex + y and t = er + s;
Verify: V accepts the proof and outputs 1 if ce d = g z ht mod n. Otherwise, V rejects the proof and
outputs 0.
In the rest of this section, we prove this protocol is indeed a zero-knowledge argument of knowledge
of an opening. Which means it is correct, zero-knowledge, and knowledge-extractable.

Correctness. First, the correctness is quite obvious: if c = g x hr mod n, with z = ex + y and

t = er + s, we have g z ht = (g x hr )e · g y hs = ce d mod n.
 9

Zero-Knowledge. For the zero-knowledge property, in the honest-verifier setting, the simulator
Sim (that is SimZK in this case) can simply do as follows:
1. Sim chooses a random challenge e ←R J0 ; 2κ K;
2. Sim chooses random responses z ←R J0 ; 2kx +2κ K and t ←R J0 ; 2|n|b +2κ K;
3. Sim sets d = g z ht c−e mod n.
The simulated transcript is the tuple (d, e, (z, t)), where the elements follow the distribution D3 from
Figure 1, while the real transcript follows the distribution D0 .

y ←R J0 ; 2kx +2κ K, s ←R J0 ; 2|n|b +2κ K,

D0
e ←R J0 ; 2κ K, z = xe + y, t = re + y, d = g y hs mod n
z ←R Jxe ; 2kx +2κ + xeK, t ←R Jre ; 2|n|b +2κ + reK,
D1
e ←R J0 ; 2κ K, d = g z−xe ht−re mod n
z ←R Jxe ; 2kx +2κ + xeK, t ←R Jre ; 2|n|b +2κ + reK,
D2
e ←R J0 ; 2κ K, d = g z ht c−e mod n
z ←R J0 ; 2kx +2κ K, t ←R J0 ; 2|n|b +2κ K,
D3
e ←R J0 ; 2κ K, d = g z ht c−e mod n

Fig. 1: Distributions for the Zero-Knowledge Property

However, it is clear that D0 = D1 = D2 , while the distance between D2 and D3 is the sum
of the distances between the distributions of z and t, respectively in Z2 = Jxe ; 2kx +2κ + xeK and
Z3 = J0 ; 2kx +2κ K, and T2 = Jre ; 2|n|b +2κ + reK and T3 = J0 ; 2|n|b +2κ K:

2kx +2κ
X+xe
∆z = | Pr[z ←R Z2 : z = Z] − Pr[z ←R Z3 : z = Z]|
Z=0
xe−1
X 2kx +2κ
X+xe
−kx −2κ
= 2 + 2−kx −2κ = 2 · xe · 2−kx −2κ ≤ 2 · 2kx +κ · 2−kx −2κ
Z=0 Z=2kx +2κ +1

that is bounded by 2 · 2−κ . Similarly, ∆t ≤ 2 · 2−κ . Hence the statistical zero-knowledge property,
since the real distribution D0 and the simulated distribution D3 have a negligible distance bounded
by 2−κ+2 .

Knowledge-Extractability. The last property is the most intricate, and this is the one that
required the Strong-RSA assumption in the original proof of Damgård and Fujisaki [DF02]. In the
next section, we present a detailed proof of the following theorem:

Theorem 2. Given a prover P’ able to convince a verifier V of its knowledge of an opening of c

for random system parameters pp = (n, g, h) with probability greater than ε within time t, one either
breaks the RSA assumption with expected time upper-bounded by 256t/ε3 , or extracts a valid opening
with expected time upper-bounded by 16t/ε2 .

4 Proof of Theorem 2

Since this proof is the main technical contribution of the paper, with many practical applications,
we provide it in details. We start with some preliminaries, and then discuss various cases.
 10

4.1 Preliminaries
The proof will make use of the splitting lemma [PS96, PS00], that we recall below:
Lemma 3. Let A ⊂ X × Y such that Pr[(x, y) ∈ A] ≥ ε. For any ε0 < ε, if one defines B =
(x, y) ∈ X × Y | Pry0 ∈Y [(x, y 0 ) ∈ A] ≥ ε − ε0 , then it holds that:


(i) Pr[B] ≥ ε0 (ii) ∀(x, y) ∈ B, Pr

0
[(x, y 0 ) ∈ A] ≥ ε − ε0 (iii) Pr[B | A] ≥ ε0 /ε.
y ∈Y

In the proof, we will consider an adversary with a random tape R who succeeds with some
probability ε in any run of the full argument. Our proof will make use of rewinding: we will rewind
the adversary several times to get several transcripts of the protocol for the same random tape
R, and various challenges. The purpose of the splitting lemma is therefore to get a bound on the
probability of getting valid transcripts when we fix R and run the adversary on various challenges.

4.2 Detailed Proof

Let us suppose the extractor Sim (that is SimKE in this case) is given a 4/ε-RSA challenge (n, e, u),
which means that the exponents e is randomly chosen prime to ϕ(n) but also in the set [1, 4/ε]. It
sets h ← u2 mod n and g ← hα mod n for a random exponent α ←R Zn2 . It sets pp = (n, g, h).
Note that as u is random in Z∗n , (g, h) are actually distributed as in the real protocol. We consider
an adversary A that provides a convincing proof of knowledge of an opening of c (an accepted
transcript) with probability ε, with the parameters (pp = (n, g, h), κ, c, kx ).
Note that the probability distribution of a protocol execution is D = (R, e), where R is the
adversary’s random tape that determines d, and e is the random challenge from the honest verifier.
Then, we can assume that on a random pair (R, e0 ), its probability to output an accepted transcript
(d, e0 , z0 , t0 ) is greater than ε. We apply the splitting lemma with ε0 = ε/2 for the distribution
D = {R}×{e}: after one execution, with probability greater than ε, we obtain an accepted transcript
(d, e0 , z0 , t0 ). In such a case, with probability greater than 1/2, R is a good random tape, which means
that another execution with the same R but a random challenge e1 will lead to another accepted
transcript (d, e1 , z1 , t1 ) with probability ε0 = ε/2. Note that since R is kept unchanged, d is the
same. Globally, with probability greater than ε2 /4, after 2 executions of the protocol, one gets two
related accepted transcripts: (d, e0 , z0 , t0 ) and (d, e1 , z1 , t1 ).
Without loss of generality, we may assume e0 ≥ e1 . Writing e01 ← e0 − e1 , z10 ← z0 − z1 , and
0 0 0
t01 ← t0 − t1 , the two valid tuples lead to the relation ce1 = g z1 ht1 mod n.
Then, with our adversary A and a rewind, with random (R, e0 , e1 ), we have at least one of the
two statements below that is true after a first execution of A with (R, e0 ) and a rewind with (R, e1 ):
– Statement 1. one gets two related accepted transcripts (d, e0 , z0 , t0 ) and (d, e1 , z1 , t1 ), and e01
divides both z10 and t01 (with above notations) with probability greater than ε2 /8;
– Statement 2. one gets two related accepted transcripts (d, e0 , z0 , t0 ) and (d, e1 , z1 , t1 ), and e01
does not divide both z10 and t01 (with above notations) with probability greater than ε2 /8.

Statement 1: One gets two related accepted transcripts and e01 divides both z10 and
t01 with probability greater than ε2 /8. Sim simply outputs the pair of integers (x1 , r1 ) ←
(z10 /e01 , t01 /e01 ). If e01 is odd, and thus prime to ϕ(n), we have c = g x1 hr1 mod n. However, if e01 = 2v ρ
v
for an odd ρ and v ≥ 1, (c−1 g x1 hr1 )2 = 1 mod n: from the Fact 2 from Proposition 1, (c−1 g x1 hr1 )2 =
1 mod n:
– either c−1 g x1 hr1 = ±1 mod n, and so c = ±g x1 hr1 mod n (valid opening);
 11

– or we have a non-trivial square root of 1 modulo n, which leads to the factorization of n (see
Proposition 1). As the RSA assumption is stronger than the factorization, when we solve the
factorization, we can compute the solution to the RSA challenge.

Statement 2: One gets two related accepted transcripts and e01 does not divide both z10
and t01 with probability greater than ε2 /8. We first show that, with reasonable probability, e01
does not divide αz10 + t01 either (this is exactly the case 2 from [DF02]). The intuition behind this
argument is that the only information that A can get about α is from g = hα mod n. However,
this leaks only α mod p0 q 0 , while α was taken at random in Zn2 : all the information on its most
significant bits is perfectly hidden. We recall below the proof given by Damgård and Fujisaki, for
completeness.
Let Q be a prime factor of e01 and j be the integer such that Qj divides e01 but Qj+1 does not
divide e01 , and at least one of z10 or t01 is non-zero modulo Qj . Since e01 does not divide both z10 and
t01 , so such a pair (Q, j) does necessarily exist. Actually, if Qj divides z10 , as it divides e01 , it must
also divide αz10 + t01 and therefore t01 , which was excluded (at least one of z10 or t01 is non-zero modulo
Qj ). Therefore, z10 6= 0 mod Qj .
We can write α = [α mod p0 q 0 ] + λp0 q 0 for some λ. Let us denote µ = [α mod p0 q 0 ]. The tuple
(n, g, h) uniquely determines µ, whereas λ is perfectly unknown to the prover. As Qj divides e01 , it
also divides αz10 + t01 :
αz10 + t01 = λz10 p0 q 0 + µz10 + t01 = 0 mod Qj .
Note that p0 q 0 6= 0 mod Q, since p0 and q 0 are κ-bit primes and the challenges are less than 2κ .
And from the view of the adversary, λ is uniformly distributed in Zn , while it should satisfy the
above equation. But since this equation has at most gcd(z10 p0 q 0 , Qj ) solutions, which is a power
of Q (and at most Qj−1 ), and since n is larger than Qj by a factor (far) bigger than 2κ , the
distribution of λ mod Qj is statistically close to uniform in ZQj , and the probability that λ satisfies
the above equation is bounded by 1/Q − 2−κ ≤ 1/2, independently of the actions of A . Hence, when
Statement 2 holds (the global probability is greater than ε2 /8), e01 cannot divide αz10 + t01 more than
half the time. As a consequence, we necessarily have a stronger statement
One gets two related accepted transcripts and e01 does not divide αz10 + t01 with
probability greater than ε2 /16.
This allows Sim to solve an RSA instance, which is the difference with the original proof. Let
β1 = gcd(e01 , αz10 + t01 ). Since e01 does not divide αz10 + t01 , we necessarily have 1 ≤ β1 < e01 . Let
Γ1 ← e01 /β1 and F1 ← (αz10 + t01 )/β1 : F1 /Γ1 is the irreducible fraction form of (αz10 + t01 )/e01 and
e01 ≥ Γ1 > 1. We now consider the following statements, among which at least one holds:
– Statement 2.a. One gets two related accepted transcripts, e01 does not divide αz10 + t01 , and
Γ1 ≤ 8/ε with probability at least ε2 /32;
– Statement 2.b. One gets two related accepted transcripts, e01 does not divide αz10 + t01 , and
Γ1 > 8/ε with probability at least ε2 /32.

Statement 2.a: One gets two related accepted transcripts, e01 does not divide αz10 + t01 ,
and Γ1 ≤ 8/ε with probability at least ε2 /32. If Γ1 ≤ 8/ε, since β1 < e01 , we must have
0 0 0
Γ1 ∈ J2 ; 8/εK. Let us recall we have (e01 , z10 , t01 ) so that ce1 = g z1 ht1 mod n and β1 = gcd(e01 , αz10 + t01 )
with 1 < Γ1 = e01 /β1 ≤ 8/ε.
So we have e01 = β1 Γ1 and αz10 + t01 = β1 F1 for relatively prime integers Γ1 and F1 . Since
0 0 0 0 0 0
h = u2 mod n, we have ce1 = u2(αz1 +t1 ) mod n, which reduces to cΓ1 = ce1 /β1 = ±u2(αz1 +t1 )/β1 =
 12

±u2F1 mod n, unless one finds a non-trivial square root of 1 modulo n (which allows to solve any
RSA instance modulo n, see above). We now consider two additional statements, among which at
least one holds:
– Statement 2.a.1. One gets two related accepted transcripts, e01 does not divide αz10 + t01 ,
Γ1 ≤ 8/ε, and Γ1 = 2a with a ≥ 1, with probability at least ε2 /64.
a a−1
We thus have, with probability ε2 /64, an odd k1 such that c2 = u2F1 mod n: c2 and uF1 are
two square roots of the same value. Since no information leaks about the actual square roots
a−1
{u, −u} known for h, nor for hF1 mod n, so c2 6= ±uF1 mod n with probability 1/2, which
leads to the factorization of n with probability 1/2 (see Proposition 1). Hence, we solve the RSA
challenge with probability at least ε2 /128.
– Statement 2.a.2. One gets two related accepted transcripts, e01 does not divide αz10 + t01 ,
Γ1 ≤ 8/ε, and Γ1 = 2a v with a ≥ 0 and an odd v > 1, with probability at least ε2 /64.
It thus holds, with probability ε2 /64 (unless one finds a non-trivial square root of 1 modulo
n, which allows to solve any RSA instance modulo n, see above), that C v = u2F1 mod n, for
a
C = ±c2 and gcd(v, 2F1 ) = 1, since v | Γ1 and v is odd. Using the Fact 5 from Proposition 1,
one gets the v-th root of u modulo n, for v ∈ J3 ; 8/εK ∩ Pn . Since our simulation that uses
the RSA challenge (n, u, e) does not leak any information about e, then v = e with probability
greater than ε/4, if the exponent e is randomly chosen in J2 ; 8/εK ∩ Pn (this set being exactly
the set of odd integers smaller than 8/ε, it contains approximately 4/ε elements). Hence, we
solve an RSA challenge with probability at least ε2 /64 × ε/4 = ε3 /256.

Statement 2.b: One gets two related accepted transcripts, e01 does not divide αz10 + t01 ,
and Γ1 > 8/ε with probability at least ε2 /32. When Γ1 > ε/8, the simulator rewinds the
protocol once more, with a third challenge e2 . Let us consider all the possible challenges e2 for this
rewinding (independently of any success). Among all the possible challenges e2 , and so the differences
e02 = |e0 − e2 |, the number of differences that Γ1 divides is at most (2κ + 1)/Γ1 < 8(2κ + 1)/ε. A
given e02 appears with probability at most 2/2κ (since 0 ≤ e02 ≤ max{e0 , 2κ − e0 }). Therefore, the
probability that Γ1 divides e02 for a random e2 is less than ε/4. Recall that, from the splitting lemma
(with a good R), one gets a third related accepted transcript with probability greater than ε/2.
Hence globally, we get three related accepted transcripts, such that e01 does not divide αz10 + t01 ,
Γ1 > 8/ε, and Γ1 does not divide e02 , with probability at least ε3 /128.
As above, for the third transcript (d, e2 , z2 , t2 ), we assume e0 ≥ e2 , and define e02 ← e0 − e2 ,
z20 ← z0 − z2 (otherwise we change the signs). We also define β2 = gcd(e02 , αz20 + t02 ). Note that we
do not require that e02 does not divide αz20 + t02 . We also set Γ2 ← e02 /β2 and F2 ← (αz20 + t02 )/β2 :
F2 /Γ2 is the irreducible fraction form of (αz20 + t02 )/e02 . Since Γ2 divides e02 , it cannot be equal to Γ1 .
0 0 0 0 0 0
Since these are all accepted transcripts, so ce1 = g z1 ht1 mod n and ce2 = g z2 ht2 mod n, and then
0 0 0 0 0 0 0 0 0 0
ce1 e2 = g e2 z1 he2 t1 = g e1 z2 he1 t2 mod n. This leads, for ∆z = e02 z10 − e01 z20 and ∆t = e02 t01 − e01 t02 , to
0 0 0 0 0 0 0 0
g ∆z = g e2 z1 −e1 z2 = he1 t2 −e2 t1 = h−∆t mod n.
If ∆z = ∆t = 0, then it holds that z20 /e02 = z10 /e01 and t02 /e02 = t01 /e01 :
F2 αz 0 + t0 z0 t0 z0 t0 αz 0 + t0 F1
= 2 0 2 = α · 20 + 20 = α · 10 + 10 = 1 0 1 = .
Γ2 e2 e2 e2 e1 e1 e1 Γ1
Since they are both the irreducible notations of the same fraction, we necessarily have Γ1 = Γ2 and
F1 = F2 , which contradicts the above remark that Γ2 6= Γ1 . Hence, the pair (∆z , ∆t ) is non-trivial,
which leads to the factorization of n with probability 1/2, from the Fact 4 from Proposition 1.
Overall, we get a solution to the RSA challenge with probability at least ε3 /128 × 1/2 = ε3 /256
(after getting the factorization).
 13

Overall Success Probability. All in all, if Statement 2 is true, we get a solution to the RSA
challenge with probability at least ε3 /256. On the other hand, if Statement 1 holds, there are two
complementary situations: either we get a valid opening with probability at least ε2 /16, or we get a
non-trivial square root of 1 modulo n with probability at least ε2 /16. Overall, we either get a valid
opening with probability at least ε2 /16, or we solve an RSA challenge modulo n with probability at
least ε3 /256.

5 Classical Extensions and Applications

We revisit the natural implications of the commitment scheme of Section 3 and its argument of
knowledge. More precisely, we generalize the results of previous sections while we commit to vectors of
integers. Then, we also show the security of Lipmaa’s range proofs [Lip03] under the RSA assumption
to illustrate how the result of Section 4 extends to more general arguments over the integers.

5.1 Generalized Commitment of Integers

The following commitment scheme allows committing to a vector of integers (m1 , . . . , m` ) with a
single element of the form c = g1m1 · · · g`m` hr mod n:
– Setup(1κ , `) runs (n, (p, q)) ←R GenMod(1κ ), and picks ` + 1 random generators (g1 , . . . , g` , h)
of QRn . It returns pp = (n, g1 , . . . , g` , h);
– Commit(pp, m; r), for pp = (n, g1 , . . . , g` , h), a vector m = (m1 , . . . , m` ) ∈ Z` , and some random
coins r ←R J0 ; nK, computes c = g1m1 · · · g`m` hr mod n, and returns (c, d) with d = r;
– Verify(pp, c, d, m) parses pp as pp = (n, g1 , . . . , g` , h) and outputs 1 if c = ±g1m1 · · · g`m` hd mod n
and 0 otherwise.
Again, the above commitment scheme is obviously correct. The hiding property relies on the existence
of αi such that gi = hαi mod n for i = 1, . . . , `, and so
P
c = Commit(pp, m; r) = g1m1 · · · g`m` hr = hr+ αi mi
P
αi (mi −m0i ))+
P
αi m0i m0 m0 P
αi (mi −m0i )
= h(r+ = g1 1 · · · g` ` hr+
= Commit(pp, m0 ; r0 ),

for any m0 = (m01 , . . . , m0` ) ∈ Z, with r0 ← [r + αi (mi − m0i ) mod p0 q 0 ], that is smaller than n.
P
The binding property relies on the Integer Factorization assumption: indeed, from two different
openings (m, d) and (m0 , d0 ) for a commitment c, with d0 > d, the validity checks shows that
m0 m0 0
g1m1 · · · g`m` hd = g1 1 · · · g` ` hd modP
n, and so, if one has chosen βi such that gi = g βi mod n, for a
0 0
random square g, then one knows g βi (mi −mi ) = hd −d mod n. The Fact 4 from Proposition 1 leads
to the conclusion.
To avoid a trusted setup, one can note that the guarantees for the prover (the hiding property)
just rely on the existence of αi such that gi = hαi mod n for i = 1, . . . , `. The well-formedness of
the RSA modulus is for the security guarantees against the verifier. It is important for him that the
prover cannot break the RSA assumption. So the setup can be run by the verifier, with an additional
proof of existence of αi such that gi = hαi mod n for i = 1, . . . , ` to the prover.

5.2 Zero-Knowledge Argument of Opening

An argument of knowledge of an opening of a commitment c = g1x1 · · · g`x` hr mod n in the general case
can be easily adapted from the normal case leading to a transcript of the form (d, e, (z1 , . . . , z` , t))
 14

with d = g1y1 · · · g`y` hs , and ce d = g1z1 · · · g`z` ht mod n. As above, the knowledge-extractor rewinds the
execution for the same d, but two different challenges e0 6= e1 . Doing the quotient of the two relations,
0 z0 z0 0
d cancels out: ce = g11 · · · g` ` ht mod n. Let us assume that one would have set gi = g ai hbi mod n,
we would have
0 0 0 0
P P
ce = g ai zi h bi zi +t mod n.
UnderPthe RSA assumption, the above Statement 1 (from the proof, in Section 4) holds: e0 divides
0
P 0 0
both ai z1 and bi zi + t with non-negligible probability. Since the coefficients ai ’s and bi ’s are
random, this means that e0 divides all the zi0 ’s and t0 . Hence, one can set µi = zi0 /e0 , for i = 1, . . . , `
and τ = t0 /e0 , and c = ±g1µ1 · · · g`µ` hτ mod n is a valid opening of c, unless one finds a non-trivial
square-root of 1 modulo n.

5.3 Efficient Range Proofs from RSA

We show that Lipmaa’s range proof [Lip03] also benefits from our technique as the Strong-RSA
assumption can also be avoided in the security analysis.

Range Proof from Integer Commitment Scheme. Let c = g x hr mod n be a commitment of

a value x and Ja ; bK be a public interval. As the commitment is homomorphic, one can efficiently
compute a commitment ca of x − a and a commitment cb of b − x from c. To prove that x ∈ Ja ; bK,
this is enough to show that ca and cb commit to positive values. Let us focus on the proof that
ca = g x−a hr mod n commits to a positive value, sincePthe same method applies for cb . To do so,
the prover computes (x1 , x2 , x3 , x4 ) such that x − a = 4i=1 x2i . By a famous result from Lagrange,
such a decomposition exists if and only if x − a ≥ 0. Moreover, this decomposition can be efficiently
computed by the Rabin-Shallit algorithm [RS86], for which Lipmaa [Lip03] also suggested some
optimizations. The prover commits to (x1 , x2 , x3 , x4 ) in (c1 , c2 , c3 , c4 ), where ci = g xi hri mod n for
each i = 1 to 4. Now, the prover proves his knowledge ofPopenings x − a, x1 , x2 , x3 , x4 (along with
random coins r, r1 , r2 , r3 , r4 ) of ca , c1 , c2 , c3 , c4 satisfying 4i=1 x2i = x − a over the integers.
The reason allowing to solely rely on the RSA assumption in the range proof comes from the fact
that the first part of the argument reduces to an argument of knowledge of openings x1 , x2 , x3 , x4 of
c1 , c2 , c3 , c4 while the remaining part simply ensures the relation 4i=1 Q x2i = x−a toPhold. Indeed, once
P
the witnesses are extracted, this is implied by the representation ca = 4i=1 cxi i hr− xi ri mod n which
can be seen as generalized commitment scheme with basis (c1 , c2 , c3 , c4 , h) from which the opening
cannot change. Therefore, the argument can be seen as five parallel arguments of knowledge, the
fifth one being an argument of knowledge for a generalized commitment, where the opening for the
last argument is the vector of the openings for the other arguments. A formal proof of an optimized
version of this protocol under the intractability of the RSA assumption is presented in Appendix A.

Extension. Since most of the arguments of knowledge of a solution to a system of equations over the
integers [CCT07] can be split into parallel arguments of knowledge of values assigned to the variables
and a proof of membership (in the language composed of all the solutions of the system), which is
expressed as representations corresponding to generalized commitments, our analysis extends to all
“discrete-logarithm relation set” (see [KTY04]): the description of the protocol is unchanged but the
security only relies on the standard RSA assumption.

6 Commitment with Knowledge-Delayed Order

Arguments of knowledge of openings for the Damgård-Fujisaki commitment scheme can rely on the
RSA assumption rather than the Strong-RSA assumption. In this section, we show that this scheme
 15

can be efficiently combined with another RSA-based commitment scheme which, as far as we know,
was proposed by Gennaro [Gen04]: we show how Damgård-Fujisaki commitments (which are homo-
morphic over the integers) can be converted into Gennaro commitments (which are homomorphic
over Zπ for some prime π). We rely on this feature to design a method to improve the efficiency of
zero-knowledge arguments over the integers on several aspects, by allowing the players to perform
some of the computations over Zπ rather than over the integers. We then illustrate our technique
on the famous example of range proofs.

6.1 RSA-based Commitments with Known Order

We recall the homomorphic commitment scheme over Zπ of [Gen04]. The order of the commitment
is a known prime π > 2κ .

Description of the Generalized Commitment Scheme. Let us describe the commitment of

vectors of integers (m1 , . . . , m` ):
– Setup(1κ ) runs (n, (p, q)) ←R GenMod(1κ ), and picks ` random generators g1 , . . . , g` of QRn .
Then, it picks a random prime π ∈ J2κ+1 ; 2κ+2 K, and returns pp = (n, g1 , . . . , g` , π);
– Commit(pp, m; r), for pp = (n, g1 , . . . , g` , π), a vector m = (m1 , . . . , m` ) ∈ Z`π , and some random
coins r ←R Zn , computes c = g1m1 · · · g`m` rπ mod n, and returns (c, d) with d = r;
– Verify(pp, c, d, m) parses pp as pp = (n, g1 , . . . , g` , π) and outputs 1 if c = g1m1 · · · g`m` rπ mod n,
and 0 otherwise.
The above commitment scheme is obviously correct. The hiding property relies on the bijectivity
of the π-th power modulo n (as π is prime): for any message m0 = (m01 , . . . , m0` ) ∈ Z`π , we have
m0 m0 m −m0 m −m0 m −m0 m −m0
c = g1 1 · · · g` ` × g1 1 i · · · g` ` i × rπ mod n. By noting s the π-th root of g1 1 i · · · g` ` i , c =
Commit(pp, m0 ; rs). The binding property uses an extension of the Fact 5 from Proposition 1: if one
has chosen βi such that gi = u2βi , for a challenge RSA u ∈ Z∗n , two distinct openings (m, r) 6= (m0 , s)
m0 m0
satisfy g1m1 · · · g`m` rπ = g1 1 · · · g` ` sπ mod n, and so (s/r)π = u2a mod n, where a = βi (mi −m0i ) =
P
a1 π + a0 , with 0 ≤ a0 < π. Let us note α and β the integers such that απ + β2a0 = gcd(π, 2a0 ) = 1,
and output u0 := uα−2a1 β · (s/r)β mod n, then

uπ0 = uαπ−2a1 βπ · (s/r)βπ = u1−2(a0 +a1 π)β · u2aβ = u mod n.

This breaks the RSA assumption with exponent π.

Homomorphic-Opening. In addition, this commitment scheme is homomorphic in Zπ : given

m0 m0
c = g1m1 · · · g`m` rπ mod n and d = g1 1 · · · g` ` sπ mod n with known openings, we can efficiently open
the commitment c · d mod n to m̄ = (m̄1 , . . . , m̄` ), with m̄i = mi + m0i mod π for 1 ≤ i ≤ `, and
Q (m +m0 )÷π
a random coin rs gi i i mod n, where a ÷ b is the quotient of the Euclidean division. We
emphasize this property to be essential to avoid working with long integers in the arguments of
knowledge of an opening: the prover can “reduce” its openings since π is known.

Argument of Opening. Given pp = (n, g1 , . . . , g` , π) and c = g1x1 · · · g`x` rπ mod n, with witness
(x1 , . . . , x` , r), we can describe a standard argument of knowledge of an opening:
Initialize: P and V decide to run the protocol on input (pp, κ, c);
Commit: P computes d = g1y1 · · · g`y` sπ , for yi ←R Zπ , and s ←R Z∗n , and sends d to V ;
Challenge: V outputs e ←R J0 ; 2κ K;
 16

Response: P computes ki , zi , t such that exi + yi = ki π + zi , with 0 ≤ zi < π, and t = g1k1 · · · g`k` ·
re s mod n. P outputs (z = (zi )i , t);
Verify: V accepts the proof and outputs 1 if, for each i, 0 ≤ zi < π, and ce d = g1z1 · · · g`z` tπ mod n.
Otherwise, V rejects the proof and outputs 0.
Completeness and zero-knowledge are straightforward. Then, let us focus on the knowledge-extractability:
0 z −z 0 z −z 0
From two related valid transcripts, for the same d, we get as usual ce−e = g11 1 · · · g` ` ` ·
(t/t0 )π mod n. Since the prime π > 2κ ≥ |e − e0 |, the simulator can compute α(e − e0 ) + βπ = 1 and
we have
0 α(z −z 0 ) α(z −z 0 )
c1−βπ = cα(e−e ) = g1 1 1 · · · g` ` ` · (t/t0 )απ mod n.
Then, for α(zi − zi0 ) = li π + x0i with 0 ≤ x0i < π, and T = cβ · g1l1 · · · g`l` · (t/t0 )α mod n, we have a
valid opening (x01 , . . . , x0` , T ) of c.

6.2 Commitment with Knowledge-Delayed Order

The above commitment scheme with known prime order π can temporarily pass itself off as a
commitment scheme of Section 3 with hidden order.

Description of the Commitment Scheme. The verifier sets up the parameter pp of the commit-
ment scheme with hidden order but hides a prime order π in pp during this execution. To guarantee
the hiding property, in the setup the verifier also adds a proof that g = hα mod n for some α.
– Setup(1κ ) runs (n, (p, q)) ←R GenMod(1κ ), and picks h0 ←R QRn and a random prime π ∈
J2κ+1 ; 2κ+2 K. Then, it picks ρ ←R J0 ; n2 K, relatively prime to π, and sets g ← hρ0 mod n and
h ← hπ0 mod n. Finally, it returns pp = (n, g, h) and keeps sk = (π, h0 ). Actually, we have
hρ = g π mod n. So, if one sets α = ρ · π −1 mod ϕ(n), one has g = hα mod n, and proves it;
– Commit(pp, m; r) parses pp as above and commits to m ∈ Z by picking r ←R Zn and computing
c = g m hr mod n. It returns (c, r);
– Verify(pp, c, m, r) parses pp = (n, g, h) and outputs 1 if c = ±g m hr mod n and 0 otherwise;
– Reveal(pp, sk) returns sk = (π, h0 );
– Adapt(pp, sk, c, m, r) first parses sk = (π, h0 ) and checks whether h = hπ0 mod n. Then, it adapts
the opening by computing m = kπ + m̄ for 0 ≤ m̄ < π and t = g k hr0 mod n. It outputs (m̄, t);
– Verify0 (pp, π, c, m̄, t) outputs 1 if c = g m̄ tπ mod n, and 0 otherwise.
0
This construction easily extends to commitments of vectors. Note that from g m̄ tπ = c = g m̄ t0 π mod
n, with m̄ 6= m̄0 mod π, setting h0 = y 2 from an RSA challenge (n, y) of exponent π > 2κ , we obtain
0
y 2ρ(m̄−m̄ ) = (t0 /t)π mod n, with 2ρ(m̄ − m̄0 ) 6= 0 mod π, which leads to the π-th root of y modulo
n (using Fact 5 from Proposition 1).

Switching between Commitments. Let com denote the Damgård-Fujisaki integer commitment
scheme, such that com(m; r) = g m hr mod n, and comπ denote the Gennaro commitment scheme,
such that comπ (m; r) = g m rπ mod n. On the one-hand, only com leads to proof of relations over
the integers. On the other hand, comπ leads to much more efficient proofs of relation modulo π.
The above commitment with knowledge-delayed order allows generating pp = (n, g, h) so that c =
com(m; r) = g m hr mod n can be switched into
c = comπ (rπ (m); g qπ (m) hr0 ), (1)
where qπ (m) and rπ (m) denote the quotient and remainder of the euclidean division of m by π.
This switching allows to keep some good properties over the integers and working modulo π since
pp gives no information about π until the verifier reveals (π, h0 ).
 17

6.3 Improving Zero-Knowledge Arguments over the Integers

The commitment with knowledge-delayed order provides a new technique to zero-knowledge argu-
ments for statements over the integers, while working modulo π. This technique leads to more efficient
membership arguments, with a lower communication and a smaller verifier computation (some part
of the cost is delegated to the prover). We restrict our attention to statements that can be expressed
as membership to a set S ∈ D. The protocol we describe is honest-verifier zero-knowledge. At the
end of the section we recall standard methods to get full-fledged zero-knowledge.

Membership Argument for D. Given S ∈ D, let PS be a representing polynomial with k-vector

input and `-vector witness. We assume P and V agreed on a bound t such that each x ∈ S has a
witness w such that kwk∞ ≤ kxkt∞ (S ∈ D, so there is always such a t. As shown in [Lip03], t < 2
is sufficient for most cryptographic applications).
Let x be a secret vector held by P, and w be a witness for x ∈ S, meaning that PS (x, w) = 0.
Zero-knowledge argument for polynomial relations over committed inputs usually demands commit-
ting to intermediate values, and proving additive and multiplicative relationships with the inputs,
see e.g. [BS02]. To prove a multiplicative relationship z = xy between values (x, y, z) commit-
ted in (cx , cy , cz ), P proves knowledge of inputs (x, y, z) and random coins (rx , ry , rz ) such that
cx = g x rxπ mod n, cy = g y ryπ mod n, and cz = cyx rzπ .
We almost follow this principle except that we use the commitment scheme of Section 6.2 to
switch from com to comπ once P proved knowledge of both x and w over the integers. Proving
PS (x, w) = 0 over the integers is then replaced by proving PS (x, w) = 0 modulo π.

Argument of knowledge of the inputs and witnesses.

1. V runs the setup from the Section 6.2, which generates pp = (n, g, h) and sk = (π, h0 ): this
defines com : (x; r) 7→ g x hr mod n. It additionally proves the existence of α such that g =
hα mod n;
2. P picks random coins (rx , rw ) and commits to (x, w) with (rx , rw ) as (cx , cw ) ← (com(x; rx ),
com(w; rw ));
3. P performs a ZKAoK{(x, w, rx , rw ) | cx = g x hrx ∧ cw = g w hrw }, we thereafter refer to ZK1 ,
with V . If the argument fails, V aborts the protocol.

Argument of knowledge of (x0 , w0 ) such that PS (x0 , w0 ) = 0 mod π.

1. V reveals (π, h0 ) to P who checks whether h = hπ0 mod n or not, to switch to comπ . Let
(x0 , w0 ) = (rπ (x), rπ (w)) = (x, w) mod π.
2. P performs a ZKAoK{(x0 , w0 , Rx , Rw )}, we thereafter refer to ZK2 , such that (cx , cw ) =
(comπ (x; Rx ), comπ (w; Rw )) and PS (x, w) = 0 mod π. Note that (cx , cw ) are now seen as
commitments over Zπ , using the fact that com(x; rx ) = comπ (rπ (x); Rx ) and com(w; rw ) =
comπ (rπ (w); Rw ), with appropriate (Rx , Rw ). If the argument succeeds, V returns accept.
Theorem 4. Under the RSA assumption, the above protocol is a statistical zero-knowledge argument
of knowledge of openings of (cx , cw ) to vectors of integers (x, w) such that PS (x, w) = 0: which
proves that x ∈ S.
Proof. The intuition behind Theorem 4 is that ZK1 proves that P knows (x, w) in (cx , cw ), and ZK2
proves that PS (x, w) = 0 mod π for a κ-bit prime π which was revealed after (x, w) were committed.
Hence, P knew vectors of integer (x, w) such that PS (x, w) = 0 mod π for a random κ-bit prime
π. This has a negligible probability to happen unless PS (x, w) = 0 holds over the integers, since
PS is a polynomial. The full proof consists of the three properties: correctness, zero-knowledge, and
knowledge-extractability.
 18

Correctness. It easily follows from the correctness of ZK1 and ZK2 : if P knows (x, w, rx , rw )
such that (cx , cw ) = (com(x; rx ), com(w; rw )) and PS (x, w) = 0, then the argument of knowledge
of (x, rx ) such that cx = com(x; rx ) will succeed, and it holds that (cx , cw ) = (comπ (x mod
π; v qπ (x) h̃rx ), comπ (w mod π; v qπ (x) h̃rx )). Moreover, as PS is a polynomial, the modular reduction
applies, and leads to PS (x mod π, w mod π) = PS (x, w) = 0 mod π.

Zero-Knowledge. It also follows from the zero-knowledge of ZK1 and ZK2 , and the hiding property of
the commitments. Let SimZK be the following simulator: one first generates dummy commitments
(cx , cw ), which does not make any difference under the hiding property, and runs the simulator of
ZK1 . Once (π, h0 ) is revealed, SimZK runs the simulator of ZK2 .
Since the commitment is statistically hiding, ZK1 is our statistically zero-knowledge argument
of knowledge of opening from Section 3 and ZK2 is an argument of relations on commitments with
known order π (since h = hπ0 mod n) that is possible in statistical zero-knowledge, the full protocol
is statistically zero-knowledge.

Knowledge Extractability. Let P’ outputing a convincing argument with probability ε, i.e. P’

succeeds in ZK1 and ZK2 with probability greater than ε.
Under the RSA assumption, there is an extractor of ZK1 which computes (x, w, rx , rw ) such
that cx = g x hrx and cw = g w hrw . Then, (π, h0 ) is revealed in the protocol and still under the
RSA assumption, there is another extractor of ZK2 which computes (x0 , w0 , Rx , Rw ) such that both
relations (cx , cw ) = (comπ (x0 ; Rx ), comπ (w0 ; Rw )) and PS (x0 , w0 ) = 0 mod π are satisfied. Now, let
us consider two situations:
– If x0 = x mod π and w0 = w mod π, then the value committed over the integers, before π was
revealed, satisfy PS (x, w) = 0 mod π, for a random π ∈ J2κ+1 ; 2κ+2 K. We stress that the view
of (n, g, h) does not reveal any information on the prime π.
Since there are approximately 2κ+1 /κ primes in this set, and this extraction works with proba-
κ 2
bility greater than ε2 , PS (x, w) = 0 mod Q, for Q ≥ 22 /ε , which is much larger than the values
that can be taken in the integers, since the inputs and the witnesses have a size polynomial in
κ, and the polynomial PS has a bounded degree.
– If x0 6= x mod π or w0 6= w mod π, wlog, we can assume that x0 6= x mod π:
• we get (x, rx ) such that cx = ±g x hrx = g rπ (x) (±g qπ (x) hr0x )π mod n;
0
• and (x0 , Rx ) such that cx = g x Rx π mod n.
0 0
Hence, g rπ (x) (±g qπ (x) h0x )π = g x Rx π mod n, and so g rπ (x)−x = S π mod n, for S = Rx /(±g qπ (x) hr0x ) mod
r

n. If one would have set h0 = y 2 from an RSA challenge (n, y, π) of exponent π > 2κ , and thus
g = y 2ρ , using Fact 5 from Proposition 1, one gets the π-th root of y modulo n.
This concludes the proof of the knowledge-extractability of the protocol, under the RSA assumption
over Zn .

On the Efficiency of the Method. The advantages of this method compared to the classical
method are twofold. First, most of the work in the protocol comes from the computation of ex-
ponentiations; and our technique transferes most of this work from V to P. This comes from the
fact that verifying an equation such as c = com(x; r) involves exponentiations by integers of size
O(log n+κ) while verifying the equation c = comπ (x mod π; R) involves only two exponentiations by
κ-bit values, which greatly reduces V ’s work. However, to switch from com to comπ P has to adapt
the opening as in (1) of Section 6.2, which costs exponentiations by integers of size O(log n + κ)
to compute the random coin R. V will still need to perform exponentiations by integers during
ZK1 , but his work during this step can be made essentially independent of the number N of inputs
 19

and witnesses (up to a small log N additive term) and completely independent of the degree of the
representing polynomial.
Second, our method separates the argument of knowledge of inputs to a Diophantine equation
from the argument that they do indeed satisfy the equation. The arguments of knowledge of an
opening of a commitment can be very efficiently batched: if P commits to (x1 , · · · , xN ) with ran-
dom coins (r1 , · · · , rN ) as (c1 , · · · , cN ), the verifier can simply send a random seed λ ←R {0, 1}κ
from which both players compute (λ1 , · · · , λN ) using aPpseudo-random generator2 . Then, PQper-
forms a single argument of knowledge of an opening ( i λi xi ; i λi ri ) of the commitment i cλi i
P
(see [BGR98a, BGR98b] for more details). Therefore, when performing multiple membership argu-
ments, P and V will have to perform a single argument for ZK1 (of size essentially independent of
the number of committed values).
In general, the higher the degree of the representing polynomial is, the lower will be the commu-
nication with our method. Still, we show in the next section that even for the case of range proofs,
which is a membership proof to a Diophantine set whose representing polynomial is of degree 2, our
method provides efficiency improvements.
Q
π
Further Improvements. V can set h to h0 i i for several primes πi instead of hπ0 . For some integer
i, let pi ← j6=i πj . Doing so allows V to reveal (hp0i , πi ) instead of (h0 , π) in our method. Hence, in
Q
addition to allowing arbitrary parrallel arguments with a single prime π, a single setting is sufficient
to perform a polynomial number of sequential arguments (fixed in advance) with different primes
πi . In addition, we explained that commitments with knowledge-delayed order allow splitting the
arguments of knowledge of the witnesses, denoted ZK1 , and the argument that they indeed belong
to a Diophantine set, denoted ZK2 . The arguments ZK1 can be batched as described above but,
for efficiency reason, we should not generate (λ1 , λ2 . . . , λN ) as (λ, λ2 , . . . , λN ). Indeed, |λj |b grows
linearly with j over the integers. However, for the argument ZK2 , the order of the commitment has
been revealed. Hence, we can now use batching technique with such λj = λj since the prover is
able to reduce the exponents modulo π at this stage. That means that our technique consisting of
efficiently revealing the order of the commitment between ZK1 and ZK2 allows to use any method
that crucially relies on batching coefficients expressed as powers of some λ, that were only available
for discrete-log based proofs of statement over (pairing-free) known-order groups. For instance, we
can get a sub-linear size argument to show that a committed matrix is the Hadamard products over
the integers of two other committed matrices. Indeed, we can commit the rows of the matrices using
a generalized commitment and make a batch proof for ZK1 , which remain sub-linear in the number
of entries, and then we can import the results of [Gro09, BG12] to ZK2 , preserving its sub-linearity.

Full-Fledged Zero-Knowledge. With an honest verifier, there is no need to prove the existence
of α such that g = hα . In the malicious setting, this proof guarantees the hiding property of the
commitments to the prover, who additionally checks h = hπ0 mod n when they are revealed. Then we
can use classical techniques to convert the HVZK protocol into a ZK protocol, such as an equivocable
commitment of the challenge by the verifier, before the commitments from the prover.

7 Application to Range Proofs

7.1 Lipmaa’s Compact Argument for Positivity
As explained before, Lipmaa [Lip03] proposed an efficient argument for positivity, using generalized
Damgård-Fujisaki commitments, and the proof that an integer is positive if and only if it can
2
The classical trick that consists of using λi = λi is not efficient here since we are in the integers, and so no reduction
can be applied.
 20

be written as the sum of four squares. However, it appears that the explicit construction given
in [Lip03, annex B] is flawed — although the high-level description is correct: any prover can provide
a convincing argument for positivity, regardless of the sign of the committed integer, and so without
holding valid witnesses. This might raise some concerns as the protocol of Lipmaa is the “textbook”
range proof based on hidden order groups. Hence the protocol is suggested in several papers, and
was implemented in e.g. [AMAR05]. In Appendix A, we recall the argument of [Lip03], identify its
flaw, and provide a correct optimized version with a full proof of security.
In the following, we describe a range proof in the same vein as the positivity argument of Lipmaa:
an integer x belongs to an interval Ja ; bK if and only if (x − a)(b − x) ≥ 0. In addition, we take into
account the following improvement suggested by Groth [Gro05]: x is positive if and only if 4x + 1 can
be written as the sum of three squares, and such a decomposition can be computed in polynomial
time by the prover. We view this range proof (we call the three-square range proof, and denote it
3SRP) as an optimized version of the textbook range proof with integer commitments, to which we
will compare our new method with knowledge-delayed order commitments (denoted 3SRP-KDO).

7.2 Three-Square Range Proof

To prove that x ∈ Ja ; bK, for x committed with an integer commitment scheme, we prove that
4(x − a)(b − x) + 1 can be written as the sum of three squares. Let (n, g, h) be the public parameters
of the Damgård-Fujisaki commitment scheme, generated by the verifier. The three-square range
proof (3SRP) is described in full details on Figure 2. Basically, both P and V know that ca contains
4(x − a) and c0 contains (b − x). The latter, with c1 , c2 , c3 containing respectively x1 , x2 , x3 , is
proven in a classical way, and the last part of the proof shows that cxa0 g, which implicitly contains
4(x − a)(b − x) + 1 also contains x21 + x22 + x23 .

For pp = (n, g, h) generated by V , P has sent c, for which he knows (x, r) such that c = g x hr mod n and
x ∈ Ja ; bK. Let H : Z5n 7→ {0, 1}2κ be a collision-resistant hash function. V compute ca = (cg −a )4 mod n and
c0 = c−1 g b mod n; P computes ca .

1. P computes (xi )1≤i≤3 such that 4(b − x)(x − a) + 1 = 3i=1 x2i . P commits to (xi )1≤i≤3 with random coins
P
3 xi ri
(ri )1≤i≤3 ←R J0 ; nK as (ci = g h mod n)1≤i≤3 . Let x0 ← (b − x) and r0 ← r.
2. P picks (m0 , · · · , m3 ) ←R J0 ;Q2B+2κ K4 , (s0 , · · · , s3 ) ←R J0 ; 22κ nK4 , σ ←R J0 ; 2B+2κ nK, and sends ∆ =
m i si σ m0 3 −mi
H((g h mod n)0≤i≤3 , h ca i=1 ci mod n).
3. V picks a challenge e ←R J0 ; 2 K and sends it to V .
κ

4. P computes and sends zi = exi + mi and ti = eri + si for i ∈ {0, 1, 2, 3}, and τ = σ + e(x0 r0 − 3i=1 xi ri ).
P
5. V accepts the argument if
3
!
zi ti −e τ e z0
Y −zi
∆ = H (g h ci mod n)0≤i≤3 , h g ca ( ci ) mod n .
i=1

Fig. 2: Three-Square Range Proof (3SRP)

We then illustrate the technique introduced in Section 6.3 on this 3SRP protocol. The full con-
verted protocol, denoted 3SRP-KDO, is described on Figure 3.

7.3 Results
Let B = log(b−a). Note that for all i ∈ {0, 1, 2, 3}, x2i ≤ (b−a)2 hence log xi ≤ B. An exponentiation
by a t-bit value takes on average 1.5t multiplications using a square-and-multiply algorithm; we do
 21

For pp = (n, g, h) and sk = (π, h0 ) generated by V , P has sent c, for which he knows (x, r) such that c =
g x hr mod n and x ∈ Ja ; bK. Let H : Z6n 7→ {0, 1}2κ be a collision-resistant hash function. V compute ca =
(cg −a )4 mod n and c0 = c−1 g b mod n; P computes ca .

1. P computes (xi )1≤i≤3 such that 4(b − x)(x − a) + 1 = 3i=1 x2i . P commits to (xi )1≤i≤3 with random coins
P
(ri )1≤i≤3 ←R J0 ; nK3 as (ci = g xi hri mod n)1≤i≤3 . Let x0 ← (b − x) and r0 ← r.
2. P picks m ←R J0 ; 2B+3κ K, (m0 , · · · , m3 ) ←R J0 ; 2κ K4 , s ←R J0 ; 23κ nK, (s0 , · · · , s3 ) ←R J0 ; nK4 , σ ←R
B+2κ m s m i si σ m0 Q3 −mi
J0 ; 2 nK, and sends ∆ = H(g h mod n, (g h mod n)0≤i≤3 , h ca i=1 ci mod n).
3. V picks a challenge e ←R J0 ; 2 K and sends (e , π, h0 ) to P.
0 κ 0

4. PPextends the challenge e0 into (e, (λi )0≤i≤3 ) ∈ J0 ; 2κ K5 , computes and sends z = e λi xi + m and t =
P
eri +si qπ (exi +mi )
e λi ri + s, as well as zi = rπ (exi + mi ) and Ti = h0 g mod n for i ∈ {0, 1, 2, 3}, and T =
σ+e(x0 r0 − 3
P
i=1 xi ri ) qπ (ex0 +m0 ) −qπ (exi +mi )
Q3
h0 ca i=1 ci mod n.
5. V accepts the argument if
3 3
!
Y Y −zi
∆ = H g z ht ( cλi i )−e mod n, (g zi Tiπ c−e i mod n) 3
i=0 , T π e z0
g c a ( c i ) mod n
i=0 i=1

Fig. 3: Three-Square Range Proof with Knowledge-Delayed Order (3SRP-KDO)

3SRP 3SRP-KDO
Communication N (8 log n + 18κ + 5B) + 3κ N (8 log n + 4κ) + 10κ + 2 log n + B + log N
1.5(N (13 log n + 13B + 18κ + log a) + log n +
Prover’s work 1.5N (8 log n + 12B + 26κ + log a)
B + 6κ + log N )
1.5(N (5 log n + 9B + 30κ + log a + 1.5(N (12κ + log a + log b) + log n + B + 10κ +
Verifier’s work
log b) + κ) log N )

Table 1: Complexities of 3SRP and 3SRP-KDO

not take into account possible optimizations from multi-exponentiation algorithms. Table 1 sums
up the communication complexity and the computational complexity of both the 3SRP and the
3SRP-KDO arguments for the execution of N parallel range proofs on the same interval Ja ; bK, as
classical batch techniques [BGR98a, BGR98b] allow to batch arguments of knowledge. Note that we
omit constant terms. The communication is given in bits, while the work is given as a number of
multiplications of elements of QRn . When comparing the work of the prover, we also omit the cost
of the decomposition in sum of squares, as it is the same in both protocols. Similarly, we omit the
cost of the initial proof of g = hα mod n by the verifier to the prover.

Efficiency Analysis. We now provide a detailed comparison between the 3SRP and the 3SRP-KDO
protocols. We set the order of the modulus n to 2048 bits and the security parameter κ to 128. As
the communication of the protocols does also depend on the bound 2B on the size of the interval, we
consider various bounds in our estimation. For the sake of simplicity, we assume B = log b. We eval-
uate the overhead of the 3SRP-KDO with respect to 3SRP, computed as 100 × (cost(3SRP-KDO) −
cost(3SRP))/cost(3SRP), cost being either a number of bits exchanged, or a number of exponentia-
tions.

Small Intervals and Large Intervals. As pointed out in [CCs08], several practical applications of
range proofs, such as e-voting [Gro05] and e-cash [CHL05], involve quite small intervals (say, of
size at most 230 , and so B ≤ 30). However, in numerous cryptographic schemes, range proofs on
very large intervals are involved. Examples include anonymous credentials [CL01], mutual private
set intersection protocols [KLC12], secure generation of RSA keys [JG02, DM10], zero-knowledge
primality tests [CM99a], and some protocols for performing non-arithmetic operations on Paillier
ciphertexts [GMS10, CPP15]. In such protocols, B typically range from 1024 to 8000. We note that
 22

communication verifier’s work

prover’s work overhead
overhead overhead
B = 30, N = 1 +16% +60.2% −66%
B = 1024, N = 1 −3.7% +44% −71.7%
B = 2048, N = 1 −17% +36.4% −74.1%
B = 30, N = 10 −7.6% +47.5% −86.8%
B = 1024, N = 10 −26.5% +33.2% −87.7%
B = 2048, N = 10 −39.1% +26.5% −88%

This is for various interval sizes (2B ) and numbers N of parallel executions
Table 2: Comparison between the 3SRP and the 3SRP-KDO
such intervals are exactly the ones for which range proofs based on groups of hidden order are
likely to be used, since for for small intervals, protocols based on some u-ary decomposition of the
input [CCs08, Gro11] will in general have better performances (essentially because they avoid the
need of the Rabin-Shallit algorithm, which is computationally involved).

Comparisons. Table 2 gives a summary of our results. As already noted, the overhead of the work
of the prover in 3SRP-KDO is measured by comparing the works without considering the cost of the
Rabin-Shallit algorithm; the latter one, however, is by far the dominant cost when B is large (as
it runs in expected O(B 2 log B · M (log B)) time, where M (log B) is the time taken to perform a
multiplication of (log B)-bit integers). Therefore, for a large B, the overhead of the work of the prover
in 3SRP-KDO is very small, whereas there is a huge gain for the verifier. As expected, the 3SRP-KDO
protocol provides interesting performances in settings where the verifier is computationally weak (e.g.
in secure Cloud computing), and/or multiples range proofs are likely to be used in parallel, and/or
the intervals are large.

Acknowledgments

This work was supported in part by the European Research Council under the European Com-
munity’s Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 – Crypto-
Cloud).

References
AM76. L. Adleman and K. Manders. Diophantine complexity. In Proceedings of the 17th Annual Symposium on
Foundations of Computer Science, SFCS ’76, pages 81–88, Washington, DC, USA, 1976. IEEE Computer
Society.
AMAR05. A. André, R. Markus, and S. Ahmad-Reza. Non-interactive watermark detection for a correlation-based
watermarking scheme. In Communications and Multimedia Security: 9th IFIP TC-6 TC-11 International
Conference, CMS 2005, pages 129–139, 2005.
BCDv88. E. F. Brickell, D. Chaum, I. Damgård, and J. van de Graaf. Gradual and verifiable release of a secret. In
CRYPTO’87, LNCS 293, pages 156–166. Springer, Heidelberg, August 1988.
BG12. S. Bayer and J. Groth. Efficient zero-knowledge argument for correctness of a shuffle. In EURO-
CRYPT 2012, LNCS 7237, pages 263–280. Springer, Heidelberg, April 2012.
BGR98a. M. Bellare, J. A. Garay, and T. Rabin. Batch verification with applications to cryptography and checking.
In LATIN 1998, LNCS 1380, pages 170–191. Springer, Heidelberg, April 1998.
BGR98b. M. Bellare, J. A. Garay, and T. Rabin. Fast batch verification for modular exponentiation and digital
signatures. In EUROCRYPT’98, LNCS 1403, pages 236–250. Springer, Heidelberg, May / June 1998.
BHJ+ 13. F. Böhl, D. Hofheinz, T. Jager, J. Koch, J. H. Seo, and C. Striecks. Practical signatures from standard
assumptions. In EUROCRYPT 2013, LNCS 7881, pages 461–485. Springer, Heidelberg, May 2013.
Bou00. F. Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT 2000, LNCS
1807, pages 431–444. Springer, Heidelberg, May 2000.
 23

BP97. N. Bari and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In
EUROCRYPT’97, LNCS 1233, pages 480–494. Springer, Heidelberg, May 1997.
BS02. E. Bresson and J. Stern. Proofs of knowledge for non-monotone discrete-log formulae and applications. In
ISC 2002, LNCS 2433, pages 272–288. Springer, Heidelberg, September / October 2002.
CCs08. J. Camenisch, R. Chaabouni, and a. shelat. Efficient protocols for set membership and range proofs. In
ASIACRYPT 2008, LNCS 5350, pages 234–252. Springer, Heidelberg, December 2008.
CCT07. S. Canard, I. Coisel, and J. Traoré. Complex zero-knowledge proofs of knowledge are easy to use. In
ProvSec 2007, LNCS 4784, pages 122–137. Springer, Heidelberg, November 2007.
CFT98. A. H. Chan, Y. Frankel, and Y. Tsiounis. Easy come - easy go divisible cash. In EUROCRYPT’98, LNCS
1403, pages 561–575. Springer, Heidelberg, May / June 1998.
CHL05. J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact e-cash. In EUROCRYPT 2005, LNCS 3494,
pages 302–321. Springer, Heidelberg, May 2005.
CL01. J. Camenisch and A. Lysyanskaya. An efficient system for non-transferable anonymous credentials with
optional anonymity revocation. In EUROCRYPT 2001, LNCS 2045, pages 93–118. Springer, Heidelberg,
May 2001.
CM99a. J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes.
In EUROCRYPT’99, LNCS 1592, pages 107–122. Springer, Heidelberg, May 1999.
CM99b. J. Camenisch and M. Michels. Separability and efficiency for generic group signature schemes. In
CRYPTO’99, LNCS 1666, pages 413–430. Springer, Heidelberg, August 1999.
CPP15. G. Couteau, T. Peters, and D. Pointcheval. Encryption switching protocols. Cryptology ePrint Archive,
Report 2015/990, 2015. http://eprint.iacr.org/.
DF02. I. Damgård and E. Fujisaki. A statistically-hiding integer commitment scheme based on groups with
hidden order. In ASIACRYPT 2002, LNCS 2501, pages 125–142. Springer, Heidelberg, December 2002.
DM10. I. Damgård and G. L. Mikkelsen. Efficient, robust and constant-round distributed RSA key generation.
In TCC 2010, LNCS 5978, pages 183–200. Springer, Heidelberg, February 2010.
DPR61. M. Davis, H. Putnam, and J. Robinson. The decision problem for exponential diophantine equations.
Annals of Mathematics, pages 425–436, 1961.
FO97. E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations.
In CRYPTO’97, LNCS 1294, pages 16–30. Springer, Heidelberg, August 1997.
Gen04. R. Gennaro. Multi-trapdoor commitments and their applications to proofs of knowledge secure under con-
current man-in-the-middle attacks. In CRYPTO 2004, LNCS 3152, pages 220–236. Springer, Heidelberg,
August 2004.
GMS10. J. Guajardo, B. Mennink, and B. Schoenmakers. Modulo reduction for Paillier encryptions and application
to secure statistical analysis. In FC 2010, LNCS 6052, pages 375–382. Springer, Heidelberg, January 2010.
Gro05. J. Groth. Non-interactive zero-knowledge arguments for voting. In ACNS 05, LNCS 3531, pages 467–482.
Springer, Heidelberg, June 2005.
Gro09. J. Groth. Linear algebra with sub-linear zero-knowledge arguments. In CRYPTO 2009, LNCS 5677, pages
192–208. Springer, Heidelberg, August 2009.
Gro11. J. Groth. Efficient zero-knowledge arguments from two-tiered homomorphic commitments. In ASI-
ACRYPT 2011, LNCS 7073, pages 431–448. Springer, Heidelberg, December 2011.
HJK11. D. Hofheinz, T. Jager, and E. Kiltz. Short signatures from weaker assumptions. In ASIACRYPT 2011,
LNCS 7073, pages 647–666. Springer, Heidelberg, December 2011.
HMRT12. C. Hazay, G. L. Mikkelsen, T. Rabin, and T. Toft. Efficient RSA key generation and threshold Paillier in the
two-party setting. In CT-RSA 2012, LNCS 7178, pages 313–331. Springer, Heidelberg, February / March
2012.
HW09. S. Hohenberger and B. Waters. Short and stateless signatures from the RSA assumption. In CRYPTO 2009,
LNCS 5677, pages 654–670. Springer, Heidelberg, August 2009.
JG02. A. Juels and J. Guajardo. RSA key generation with verifiable randomness. In PKC 2002, LNCS 2274,
pages 357–374. Springer, Heidelberg, February 2002.
JKK14. S. Jarecki, A. Kiayias, and H. Krawczyk. Round-optimal password-protected secret sharing and T-PAKE in
the password-only model. In ASIACRYPT 2014, Part II, LNCS 8874, pages 233–253. Springer, Heidelberg,
December 2014.
JS07. S. Jarecki and V. Shmatikov. Efficient two-party secure computation on committed inputs. In EURO-
CRYPT 2007, LNCS 4515, pages 97–114. Springer, Heidelberg, May 2007.
KLC12. M. Kim, H. T. Lee, and J. H. Cheon. Mutual private set intersection with linear complexity. In WISA 11,
LNCS 7115, pages 219–231. Springer, Heidelberg, August 2012.
KTY04. A. Kiayias, Y. Tsiounis, and M. Yung. Traceable signatures. In EUROCRYPT 2004, LNCS 3027, pages
571–589. Springer, Heidelberg, May 2004.
LAN01. H. Lipmaa, N. Asokan, and V. Niemi. Secure vickrey auctions without threshold trust. Cryptology ePrint
Archive, Report 2001/095, 2001. http://eprint.iacr.org/2001/095.
 24

Lip03. H. Lipmaa. On diophantine complexity and statistical zero-knowledge arguments. In ASIACRYPT 2003,
LNCS 2894, pages 398–415. Springer, Heidelberg, November / December 2003.
Ped92. T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO’91,
LNCS 576, pages 129–140. Springer, Heidelberg, August 1992.
Pol03. C. Pollett. On the bounded version of hilbert’s tenth problem. Arch. Math. Log., 42(5):469–488, 2003.
PS96. D. Pointcheval and J. Stern. Security proofs for signature schemes. In EUROCRYPT’96, LNCS 1070,
pages 387–398. Springer, Heidelberg, May 1996.
PS00. D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. Journal of
Cryptology, 13(3):361–396, 2000.
RS86. M. O. Rabin and J. O. Shallit. Randomized algorithms in number theory. Communications on Pure and
Applied Mathematics, 39(S1):S239–S256, 1986.
RSA78. R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signature and public-key
cryptosystems. Communications of the Association for Computing Machinery, 21(2):120–126, 1978.

A A Correction on Lipmaa’s Argument for Positivity

In this section, we outline a flaw in the protocol of [Lip03, Annex B]. We then construct a corrected
protocol and prove its security. We notified the author of our finding.

A.1 Initial Protocol

Lipmaa [Lip03, Annex B] proposed an efficient zero-knowledge argument of positivity. Since the exact
protocol was not fully detailled, we found that the protocol could be understood in two different
ways. If one closely follows the description of the protocol, then the resulting scheme does not satisfy
correctness; and indeed, the proof of correctness seems to assume a different scheme.
We thus describe on Figure 4 our understanding from reading the proof of correctness. Unfortu-
nately, it is not sound, and the flaw comes from the fact that the original protocol is described as
using a generalized Damgård-Fujisaki commitment scheme. However, the same basis is used to com-
mitPto masks m1 , m2 , m3 , m4 , which implies that the prover will only be (computationally) binded
to i xi in the argument.

P knows (x, r) such that c = g x hr mod n and x ≥ 0. V knows c.

1. P computes (xi )i≤4 such that x = 4i=1 x2i . P commits the xi ’s with fresh random coins ri ←R J0 ; nK as
P
ci = g h mod n. P sends c1 , c2 , c3 , c4 to V .
xi ri

2. P picks (mi )4i=1 ←R J0 ; 2B/2+2κ K4 , s1 ←R J0 ; 22κ+|n|b K, and s2 ←R J0 ; 2B/2+|n|b +2κ K. Then, P sends d1 =
g m1 +m2 +m3 +m4 · hs1 mod n and d2 = c1m1 cm 2 m3 m4
2 c3 c4 · hs2 mod n.
3. V picks a challenge e ←R J0 ; 2κ K and sends it to P.
4. P computes and sends zi = exi + yi , for i = 1 to 4, t1 = e i ri + s1 and t2 = e(r − i xi ri ) + s2 .
P P
5. V accepts the argument if both

(c1 c2 c3 c4 )e · d1 = g z1 +z2 +z3 +z4 ht1 and ce · d2 = cz11 cz22 cz33 cz44 · ht2 .

Fig. 4: Lipmaa’s Compact Argument for Positivity

Actually, it does not seem possible to rely on generalized commitments to get a more efficient
protocol. Concretely, let us consider a prover P ∗ holding (x, r) such that c = g x hr and x = −1.
P ∗ commits x1 = 0, x2 = 1, x3 = 0 and x4 = 0, and computes d1 , d2 honestly. After receiving a
challenge, however, P ∗ sets x̄1 = 2, x̄2 =P−1, x̄1 = 0, x̄1 = 0, and sends z̄i = ex̄i + mi for i = 1 to 4
instead of the correct
P z ,
iP and t̄2 = e(r −
P i x̄i ri )P
+ s2 instead
P of the correct
P t2 .P P x̄i were
The values
chosen so that i x̄i = i xi , hence i z̄i = e( i x̄i ) + i mi = e( i xi ) + i mi = i zi , and
 25

so the check thatP (c1 c2 c3 c4 )e · d1 = g z̄1 +z̄2 +z̄3 +z̄4 ht1 succeeds. The second verification is equivalent
to checking that i xi · x̄i = x, which is the case here (−1 = 0 × 2 + 1 × (−1) + 0 × 0 + 0 × 0): V
accepts the argument even though the value x known by P ∗ is strictly negative.
A natural way to fix this flaw without increasing the communication would be to require the
verifier to send a seed λ between P step 1 and step P 2, from which pseudo-random values λ1 , λ2 , λ3 , λ4
are stretched, to send d1 = i λ i mi , t1 = e i λi ri + s1 and to adapt the verification equation
accordingly. However, an attack quite similar to the one we’ve just described succeeds with good
probability in this case (it is sufficient that the gcd of λi and λj is small, for some i 6= j, for the
attack to succeed). The interesting point is that we cannot batch the arguments of knowledge and
the proof of membership at the same time.

A.2 Corrected Protocol

In this section, we propose a variant of Lipmaa’s protocol [Lip03] proving that a committed x is a
sum of four squares. There are two correct ways to construct an optimized argument of positivity. A
first possibility is to rely on a collision-resistant hash function to strongly reduce the length of the
flow sent by P in step 2 (note that we only require the hash function to be collision-resistant, hence
the protocol is in the standard model). An alternative would be to let P send all individual values
(di )i and d in step 2 instead of a single hash, and to stretch pseudo-random values from e in step 4
to batch all the ti into a single value. We describe the former solution, on Figure 5, as it is slightly
more efficient than the latter in terms of communication and enjoys a better security reduction.

P knows (x, r) such that c = g x hr and x ≥ 0. V knows c. Let H : Z5n 7→ {0, 1}2κ be a collision-resistant hash
function.

1. P computes (xi )i≤4 such that x = 4i=1 x2i . P commits the xi ’s with fresh random coins ri ←R J0 ; nK as
P
ci = g xi hri mod n. P sends c1 , c2 , c3 , c4 to V .
2. P picks (mQ 4
i )i=1 ←R J0 ; 2 K , (si )4i=1 ←R J0 ; 22κ nK4 , s ←R J0 ; 2B/2+2κ nK, computes (di = g mi hsi mod
B/2+2κ 4

n)i=1 , d = i=1 ci h , and sends the commitment ∆ = H(d1 , d2 , d3 , d4 , d) to V .

4 4 mi s

3. V picks a challenge e ←R J0 ; 2κ K and sends it to P.

4. P computes and sends zi = exi + mi and ti = eri + si forQi = 1 to 4, and t = e(r
P

− xi ri ) + s.
5. V accepts the argument if ∆ = H (g h ci mod n)i=1 , i=1 ci h c mod n .
zi ti −e 4 4 zi t −e

Fig. 5: Variant of Lipmaa’s Compact Argument for Positivity

A.3 Proof of Security

Correctness immediately follows from a careful inspection of the protocol.

Zero-Knowledge Property. We now argue that the protocol is honest-verifier zero-knowledge:

given c and a challenge e, the simulator SimZK sends random group elements c1 , c2 , c3 , c4 , and picks
random (zi , ti ) ←R J0 ; 2B/2+2κ 2κ
 K × J0 ; 2 nK for i = Q
1 to 4, and a random  t ←R J0 ; 2
B/2+2κ nK. In

step 2, SimZK sends ∆ = H (g zi hti c−e 4

i mod n)i=1 ,
4 zi t −e
i=1 ci h c mod n . The commitments (ci )i
are perfectly indistinguishable from valid commitments, and ((zi )i , (ti )i , t) are statistically indistin-
guishable from honestly computed integers, with a similar analysis as in Section 3.
 26

Knowledge Extractability. Let us now prove the knowledge extractability of the protocol under
the RSA assumption. A prover P 0 which succeeds in providing a convincing proof with probability
ε is rewinded, to provide two valid proofs for the same initial commitments c1 , c2 , c3 , c4 , ∆. Under
0 0 0
the collision-resistance of the hash function: g zi hti c−ei = g zi hti c−e
i mod n, for i = 1 to 4, and
Q zi t −e Q zi0 t0 −e0
ci h c = ci h c mod n.
0 0 0 0 Q zi −zi0 t−t0
Hence, we have, for i = 1 to 4, cie −e = g zi −zi hti −ti mod n, and ce −e = ci h mod n.
Using a similar argument as in the proof of Theorem 2, unless one can break the RSA assumption,
e0 −e likely divides all the other differences and so, with ρi = (zi −zi0 )/(e0Q−e) and wi = (ti −t0i )/(e0 −e)
4 ρi w
for i = 1 to 4, and w = (t − t0 )/(e0 − e), we have ci = g ρi hP wi , and c =
i=1 ci h .
Q4 2 2
P
Altogether, thisPimplies that c = i=1 g ρi hwi ρi hw = g ρi hw+ wi ρi mod n. The commitment c
thus contains x = ρ2i , that is necessarily positive.