BRICS RS-98-29 Camenisch & Michels: Proving that a Number is the Product of Two Safe Primes BRICS

Basic Research in Computer Science

Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes

Jan Camenisch Markus Michels BRICS Report Series RS-98-29 ISSN 0909-0878 November 1998 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1998, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/98/29/

Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes

Jan Camenisch

BRICS^{∗}

Department of Computer Science

University of Aarhus DK – 8000 Århus C, Denmark

 camenisch@daimi.au.dk

Markus Michels^{†}

Entrust Technologies Europe r3 security engineering ag Glatt Tower CH – 8301 Glattzentrum, Switzerland

                                 Markus.Michels@entrust.com

November, 1998

Abstract

This paper presents the first efficient statistical zero-knowledge protocols to prove statements such as:

• A committed number is a pseudo-prime.

• A committed (or revealed) number is the product of two safe primes, i.e., primes p and q such that (p − 1)/2 and (q − 1)/2 are primes as well.

• A given value is of large order modulo a composite number that consists of two safe prime factors.

So far, no methods other than inefficient circuit-based proofs are known for proving such properties. Proving the second property is for instance necessary in many recent cryptographic schemes that rely on both the hardness of computing discrete logarithms and of difficulty computing roots modulo a composite.

The main building blocks of our protocols are statistical zero-knowledge proofs that are of independent interest. Mainly, we show how to prove the correct computation of a modular addition, a modular multiplication, or a modular exponentiation, where all values including the modulus are committed but not publicly known. Apart from the validity of the computation, no other information about the modulus (e.g., a generator which order equals the modulus) or any other operand is given. Our technique can be generalized to prove in zeroknowledge that any multivariate polynomial equation modulo a certain modulus is satisfied, where only commitments to the variables of the polynomial and a commitment to the modulus must be known. This improves previous results, where the modulus is publicly known.

We show how a prover can use these building blocks to convince a verifier that a committed number is prime. This finally leads to efficient protocols for proving that a committed (or revealed) number is the product of two safe primes. As a consequence, it can be shown that a given value is of large order modulo a given number that is a product of two safe primes.

∗Basic Research in Computer Science, Center of the Danish National Research Foundation.

†Part of this work was done while this author was with Ubilab, UBS, Switzerland.

Keywords. RSA-based protocols, zero-knowledge proofs of knowledge, primality tests.

1 Introduction

The problem of proving that a number n is the product of two primes p and q of special form arises in many recent cryptographic schemes (e.g., [7, 18, 19]) whose security is based on the infeasibility of computing discrete logarithms and of computing roots in groups of unknown order. In such scheme there typically is a designated entity which knows the group’s order and hence can compute roots. Although the other entities must not learn the group’s order, they still want to be assured that the order is not smooth, since that would allow the designated entity to compute discrete logarithms. One example of such a group are subgroups of ℤ_{n}^{∗}. In this case, it suffices that the designated entity proves that n is the product of two safe primes, i.e., primes p and q such that (p−1)/2 and (q−1)/2 are primes as well [19]. An other example of such a group are elliptic curves over ℤ_{n}. There, n must be the product of two primes p and q such that (p + 1)/2 and (q + 1)/2 are also primes [23]. Finally, standards such as X9.31 require the modulus to be the product of two primes p and q, where (p − 1)/2, (p + 1)/2, (q − 1)/2, and (q + 1)/2 have a large prime factor^{1}. Previously, the only way known for proving such properties was applying inefficient general zero-knowledge proof techniques (e.g., [21, 6, 14]).

Our main results are as follows: First, we provide an efficient protocol to prove that a committed integer is in fact the modular addition of two committed integer modulo another committed integer without revealing any other information whatsoever. Then we provide similar protocols for modular multiplication, modular exponentiation, and, more general, to any multivariate polynomial. Previous protocols allow only to prove algebraic relations modulo a publicly known integer [5, 8, 16, 14] were known. Our schemes work also for the class of commitments described in [14] (that includes discrete-logarithm-based and RSA-based commitment schemes). Second, we present an efficient zero-knowledge proof for pseudo-primality of a committed number and, as a consequence, a zero-knowledge proof that an RSA modulus n consists of two safe primes. The additional advantage of this method is that only a commitment to n but not n itself must be publicly known. If the modulus n is publicly known, however, more efficient protocols can be obtained by combining our techniques with known results described in the next paragraph.

Based on the these proofs it is simple to show that a given element a ∈ ℤ_{n}^{∗} has a large order modulo a given n = pq when (p−1)/2 and (q−1)/2 are primes. First the prover shows that n is indeed of this form. Then the verifier checks whether a^{2} ≢ 1 (mod n) and gcd(a^{2} − 1, n) = 1 holds. From this it follows that a can only be of order (p − 1)(q − 1)/4 or (p − 1)(q − 1)/2.

1It should be mentioned, however, that it is unnecessary to add this requirement into the RSA key generation explicitly. For randomly chosen large primes, the probability that (p − 1)/2, (p + 1)/2, (q − 1)/2, and (q + 1)/2 have a large prime factor is overwhelming. This is sufficient to guarantee that the Pollard-Rho and Williams p+1 factoring methods [28, 33] do not work. On the other hand, a proof that an arbitrarily generated RSA modulus is not weak without revealing the prime factors seems to be hard to obtain, as an infinite number of conditions have to be checked (e.g., see [1]).

Let us finally summarize related results on proving properties of composite numbers. Van de Graaf and Peralta [32] provide an efficient proof that a given modulus n is of the form n = p^{r}q^{s}, where r and s are odd, p and q are primes and p ≡ q ≡ 3 (mod 4). A protocol due to Boyar et al. [3] allows to prove that a given n is squarefree, i.e., there is no prime p with p|n such that p^{2}|n. Hence, if for a given n both properties can be shown, it follows that n is of form n = pq, where p and q are primes and p ≡ q ≡ 3 (mod 4). This result was recently strengthened by Gennaro et al. [20] who present a proof system for showing that a number n satisfying certain side-conditions is the product of quasi-safe primes, i.e., primes p and q for which (p − 1)/2 and (q − 1)/2 is a prime power. However, their protocol can not guarantee that (p − 1)/2 and (q − 1)/2 are indeed primes which is what we are aiming for. Let us further mention the work of Boneh and Franklin [2], who provide a proof that a distributively generated number n indeed consists of two primes (without further showing that these primes are of special form). It should be noted that all these solutions assume that n is publicly known.

2 Tools

2.1 Commitment Schemes

Our schemes build use commitment schemes that allow to algebraic prove properties of the committed value. There are two kinds of commitment scheme. The first kind hides the committed value information theoretically from the verifier (unconditionally hiding) but is only conditionally binding, i.e., a computationally unbounded prover can change his mind. The second kind is only computationally hiding but unconditionally binding. Depending on the kind of the commitment scheme employed, our schemes will zero-knowledge arguments (proofs of knowledge) or be zero-knowledge proof systems.

Cramer and Damgård [14] describe a class of commitment schemes allowing to prove algebraic properties of the committed value. These include RSA-based and discrete-logarithm-based schemes for both kinds of commitment scheme. An example of a computationally binding and unconditionally hiding scheme based on the discrete logarithm problem is the one to Pedersen [27]. Given are a group G of prime order Q and two random generators g and h such that log_{g} h is unknown and computing discrete logarithms is infeasible. A value a ∈ ℤ_{Q} is committed to as c_{a} := g^{a} h^{r}, where r is randomly chosen from ℤ_{Q}. For easier description, we will use this commitment scheme for our protocols and hence they will be statistical zero-knowledge proofs of knowledge. However, the protocol can easily be adapted to work for all the commitment scheme exposed in [14].

2.2 Various Proof-Protocols Found in Literature

In the following we assume a group G = ⟨g⟩ of large known order Q and a second generator h whose discrete logarithm to the base g is not known. We define the discrete logarithm of y to the base g to be any integer x such that y = g^{x} holds, i.e., discrete logarithms are allowed to be negative.

We shortly review various systems for proving knowledge of and about discrete logarithms found in literature.

Proving the knowledge of a discrete logarithm x of a group element y to a basis g [11, 30]. The prover chooses a random r ∈_{R} ℤ_{Q} and computes t := g^{r} and sends t to the verifier. The verifier picks a random challenge c ∈_{R} {0, 1}^{k} and sends it to the prover. The prover computes s := r − cx (mod Q) and sends s to the verifier. The verifier accepts, iff g^{s}y^{c} = t holds. This protocol is an honest-verifier zeroknowledge proof of knowledge for k = Θ(poly(log Q)) and a zero-knowledge proof of knowledge for k = O(log log(Q)) and when serially repeated Θ(poly(log Q)) times. This holds for all other protocols described in this section (when not mentioned otherwise). Adopting the notation in [7], we denote this protocol by PK{(α) : y = g^{α} }, where PKstands for “proof of knowledge”.

Proving the knowledge of a representation of the element y to the bases g_{1}, …, g_{l} [4, 10], i.e., proving the knowledge of integers x_{1}, …, x_{l} such that y = ∏ _{i=1}^{l} g_{i}^{x_{i}} . This protocol is an extension of the previous one to multiple bases. The prover chooses random r_{1}, …, r_{l} ∈_{R} ℤ_{Q}, computes t := ∏ _{i=1}^{l} g_{i}^{r_{i}} , and sends t to the verifier. The verifier picks a random challenge c ∈_{R} {0, 1}^{k} and sends it to the prover. The prover computes s_{i} := r_{i} − cx_{i} (mod Q) for i = 1, …, l and sends all s_{i}’s to the verifier. The verifier accepts, iff t = y^{c} ∏ _{i=1}^{l} g_{i}^{s_{i}} holds. This protocol is denoted PK{(α_{1}, …, α_{l}) : y = ∏ _{i=1}^{l} g_{i}^{α_{i}} }.

Proving the equality of the discrete logarithms of the elements y_{1} and y_{2} to the bases g and h, respectively [12]. Let y_{1} = g^{x} and y_{2} = h^{x}. The prover chooses a random r ∈ ℤ_{Q}^{∗}, computes t_{1} := g^{r}, t_{2} := h^{r}, and sends t_{1}, t_{2} to the verifier. The verifier picks a random challenge c ∈ {0, 1}^{k} and sends it to the prover. The prover computes s := r − cx (mod Q) and sends s to the verifier. The verifier accepts, iff g^{s}y_{1}^{c} = t_{1} and h^{s}y_{2}^{c} = t_{2} holds. This protocol is denoted by PK{(α) : y_{1} = g^{α} ∧ y_{2} = h^{α} }.

Note that this method allows also to prove that one discrete log is the square of another one (modulo the group order), e.g., PK{(α) : y_{1} = g^{α} ∧ y_{2} = y_{1}^{α} }.

Proving the knowledge of (at least) one out of the discrete logarithms of the elements y_{1} and y_{2} to the base g (proof of OR) [15]. W.l.g., we assume that the prover knows x = log_{g} y_{1}. Then r_{1}, s_{2} ∈_{R} ℤ_{Q}^{∗}, c_{2} ∈_{R} {0, 1}^{k} and computes t_{1} := g^{r_{1}} , t_{2} := g^{s_{2}} y_{2}^{c_{2}} and sends t_{1} and t_{2} to the verifier. The verifier picks a random challenge c ∈ {0, 1}^{k} and sends it to the prover. The prover computes c_{1} := c ⊕ c_{2} and s_{1} := r_{1} − c_{1}x (mod Q) and sends s_{1}, s_{2}, c_{1}, and c_{2} to the verifier. The verifier accepts, iff c_{1} ⊕ c_{2} = c and t_{i} = g^{s_{i}} y_{i}^{c_{i}} holds for i ∈ {1, 2}. This protocol is denoted PK{(α, β) : y_{1} = g^{α} ∨ y_{2} = g^{β} }. In their paper [15], Cramer et al. generalize this approach to an efficient system for proving arbitrary monotone statements built with ∧’s and ∨’s.

Proving that a discrete logarithm lies in a given range. The last building block for our protocols are statistical zero-knowledge proofs that the discrete logarithm x of y to the base g satisfies 2^{ℓ_{1}} − 2^{ℓ_{2}} < x < 2^{ℓ_{1}} + 2^{ℓ_{2}} for given parameter ℓ_{1} and ℓ_{2}. The parameter 2^{ℓ_{1}} acts as an offset and can also chosen to be zero. In principle, such a proof can be given by committing to every bit of x and proving that the committed values are indeed 0’s or 1’s and that they are the binary representation of x. Fortunately, there is a much more efficient way to achieve this as is shown in [9, 16]. The price one has to pay is that, first, the protocol is only statistical zero-knowledge and, second, it can only be shown that 2^{ℓ_{1}} − 2^{ϵℓ_{2} +2} < x < 2^{ℓ_{1}} + 2^{ϵℓ_{2} +2} , where ϵ > 1 is a security parameter, although x must lie in the intervals 2^{ℓ_{1}} − 2^{ℓ_{2}} < x < 2^{ℓ_{1}} + 2^{ℓ_{2}} for the prover being able to successfully carry out the proof. Finally, if the group’s order is known, only binary challenges are possible. Since the protocol is not so well known, we describe it in full detail in Appendix A. The protocol is denoted by

PK{(α) : y = g^{α} ∧ 2^{ℓ_{1}} − 2ℓ̈_{2} < α < 2^{ℓ_{1}} + 2ℓ̈_{2} },

where ℓ̈_{2} denotes ϵℓ_{2} +2 (we will stick to that notation for the rest of the paper). It should be mentioned, however, that if the order of the group is not known to the prover (e.g., if a subgroup of an RSA-ring is used) and when believing in the non-standard strong RSA-assumption^{2} then larger challenges can be chosen [16, 17]. Although we describe our protocols for the setting where the group’s order is known to the prover, all protocols can easily be adapted to the setting where the prover does not know the group’s order using the techniques from [16, 17].

All described protocols can be combined in natural ways. First of all, one can use multiple bases instead of a single one in any of the above proofs. Then, executing any number of instances of these protocols in parallel and choosing the same challenges for all of them in each round corresponds to the ∧-composition of the statements the single protocols prove. Using this approach, it is even possible to compose instances according to any monotone formula [15]. In the following we will use of such compositions without having explained the technical details for composition for which we refer to [5, 8, 15].

3 Secret Computations with a Secret Modulus

In this section we assume that a prover has committed to some integers a, b, d, and n. We will provide an efficient protocol for proving that a^{b} ≡ d (mod n) holds for the committed integers without revealing any further information to the verifier (i.e., the proof is zero-knowledge). However, before we can do so, we need protocols to prove that a committed integer is the addition or the multiplication of two committed secret integers modulo a committed secret modulus n.

The algebraic setting is as follows. Let ℓ be an integer such that −2^{ℓ} < a, b, d, n < 2^{ℓ} holds and ϵ > 1 be security parameters (cf. Section 2). Furthermore, we assume that a group G of order Q > 2^{2ϵℓ+5} (= 2^{2ℓ̈+1} ) and two generators g and h are available such that log_{g} h is not known. This group could for instance be chosen by the prover in which case she would have to prove that she has chosen it correctly. Finally, let the prover’s commitments to a, b, d, and n be c_{a} := g^{a} h^{r_{1}} , c_{b} := g^{b}h^{r_{2}} , c_{d} := g^{d}h^{r_{3}} , and c_{n} := g^{n} h^{r_{4}} , where r_{1}, r_{2}, r_{3}, and r_{4} are randomly chosen elements of ℤ_{Q}.

2The strong RSA assumption states that, there exists a probabilistic polynomial-time algorithm G that on input 1^{|n|} outputs an RSA-modulus n and an element z ∈ ℤ_{n}^{∗} such that it is infeasible to find integers e ∉ {−1, 1} and u such that z ≡ u^{e} (mod n).

3.1 Secret Modular Addition and Multiplication

We assume that the verifier already obtained the commitments c_{a}, c_{b}, c_{d}, and c_{n}. Then the prover can convince the verifier that a + b ≡ d (mod n) holds by running the protocol denoted^{3}:

S_{+} := PK{(α, β, γ, δ, ε, ζ, η, ϑ, κ, λ) :
c_{a} = g^{α} h^{β} ∧ −2ℓ̈ < α < 2ℓ̈ ∧ c_{b} = g^{γ} h^{δ} ∧ −2ℓ̈ < γ < 2ℓ̈ ∧
c_{d} = g^{ε}h^{ζ} ∧ −2ℓ̈ < ε < 2ℓ̈ ∧ c_{n} = g^{η}h^{ϑ} ∧ −2ℓ̈ < η < 2ℓ̈∧

\frac{c_{d}}{c_{a} c_{b}} = c_{n}^{κ}h^{λ} ∧ −2ℓ̈ < κ < 2ℓ̈\}.

Alternatively, she can convince the verifier that ab ≡ d (mod n) holds by running the protocol

S_{∗} := PK{(α, β, γ, δ, ε, ζ, η, ϑ, κ, λ, μ, ξ, ρ, σ) :

c_{a} = g^{α} h^{β} ∧ −2ℓ̈ < α < 2ℓ̈ ∧ c_{b} = g^{γ} h^{δ} ∧ −2ℓ̈ < γ < 2ℓ̈ ∧
c_{d} = g^{ε}h^{ζ} ∧ −2ℓ̈ < ε < 2ℓ̈ ∧ c_{n} = g^{η}h^{ϑ} ∧ −2ℓ̈ < η < 2ℓ̈ ∧
c_{d} = c_{b}^{α} c_{n}^{ρ} h^{σ} ∧ −2ℓ̈ < ρ < 2ℓ̈}

with him.

Remark. In some applications the prover might be required to show that n has some minimal size. This can by showing that η lies in the range 2^{ℓ_{1}} − 2ℓ̈_{2} < η < 2^{ℓ_{1}} + 2ℓ̈_{2} instead of −2ℓ̈ < η < 2ℓ̈ for some appropriate values of ℓ_{1} and ℓ_{2} (cf. Section 2.2).

Theorem 1. Let a, b, d, and n be integers that are committed to by the prover as described above. Then the protocol S_{+} is a statistical zero-knowledge proof that a + b ≡ d (mod n) holds. Furthermore, the protocol S_{∗} is a statistical zero-knowledge proof that ab ≡ d (mod n) holds.

Proof. The statistical zero-knowledge claims follows from the statistical zeroknowledgeness of the building blocks.

Let us argue why the modular relations hold. First, we consider what the clauses prove that S_{+} and S_{∗} have in common. Running the prover with either protocol (and using standard techniques), the knowledge extractor can compute integers â, b̂, d̂, n̂, r̂_{1}, r̂_{2}, r̂_{3}, and r̂_{4} such that c_{a} = gâhr̂_{1} , c_{b} = gb̂hr̂_{2} , c_{d} = gb̂hr̂_{3} , and c_{n} = gn̂hr̂_{4} holds. Moreover, −2ℓ̈ < â < 2ℓ̈, −2ℓ̈ < b̂ < 2ℓ̈, −2ℓ̈ < d̂ < 2ℓ̈, and −2ℓ̈ < n̂ < 2ℓ̈ holds for these integers.

When running the prover with S_{+}, the knowledge extractor can further compute

integers r̂_{5} ∈ ℤ_{Q} and û with −2ℓ̈ < û < 2ℓ̈ such that c_{d}/(c_{a} c_{b}) = cû ; nhr̂_{5} holds.

3Recall that ℓ̈denotes ϵℓ + 2.

Therefore we have g^{d̂−â−b̂}h^{r̂_{3} −r̂_{1} −r̂_{2}} = g^{n̂û}h^{ûr̂_{4} +r̂_{5}} and hence, provided that the discrete log of h to the base g is not known, we must have

d̂ ≡ â + b̂ + ûn̂ (mod Q) .

Thus we have d̂ = â+ b̂ + ûn̂ + w̄Q for some integer w̄. Since 2^{2ℓ̈+1} < Q and due to the constraints on â, b̂, d̂, n̂, and û we can conclude that the integer w̄ must be 0 and hence

d̂ ≡ â + b̂ (mod n̂)

must hold.

Now consider the case when running the prover with S_{∗}. In this case the knowledge-extractor can additionally compute integers r̂_{6} ∈ ℤ_{Q} and v̂ with −2ℓ̈ <

v̂ < 2ℓ̈ such that c_{d} = câ ; bcv̂ ; n h^{r_{6}} and thus gd̂hr̂_{3} = g^{âb̂+v̂n̂}h^{âr̂_{2} +v̂r̂_{4} +r̂_{∗}} holds. Again,

provided that the discrete logarithm of h to the base g is not known, we have

d̂ ≡ âb̂ + v̂n̂ (mod Q) .

As before, because of 2^{2ℓ̈+1} < Q and the constraints on on â, b̂, d̂, n̂, and v̂ we can conclude that

d̂ ≡ âb̂ (mod n̂)

must hold for the committed values.

3.2 Secret Modular Exponentiation

We now extend the ideas given in the previous paragraph to a method for proving that a^{b} ≡ d (mod n) holds. Using the same approach as above, i.e., having the prover to provide an integer ã that equals a^{b} (in ℤ) and proving this fact, would required that G has order about 2^{bℓ} and thus such a proof would become rather inefficient.

Below we expose a more efficient protocol for proving this which is obtained by constructing a^{b} (mod n) step by step according to the square & multiply algorithm (cf. Appendix B for easy reference). (In practice a more enhanced exponentiation algorithm might be used (see, e.g., [13]), but one should keep in mind that it must not leak additional information about the exponent.) In the following, we assume that an upper-bound ℓ_{b} ≤ ℓ on the length of b is publicly known.

1. Apart from committing to a, b = ∑ _{i=0}^{ℓ_{b} −1} b_{i}2^{i}, d, and n the prover must also commit to all bits of b: let c_{b_{i}} := g^{b_{i}} hr̃_{i} with r̃_{i} ∈_{R} ℤ_{Q} for i ∈ {0, …, ℓ_{b} − 1}. Furthermore she needs to provide commitments to the intermediary results of

the square & multiply algorithm: let c_{v_{i}} := g^{(a^{2^{i}} (mod n))} hr̂_{i} , (i = 1, …, ℓ_{b} −1), be her commitments to the powers of a, i.e., a^{2^{i}} (mod n), where r̂_{i} ∈_{R} ℤ_{Q}, and let c_{u_{i}} := g^{u_{i}} hr̄_{i} , (i = 0, …, ℓ_{b} − 2), where u_{i} := u_{i−1} (a^{2^{i}} )^{b_{i}} (mod n), (i = 1, …, ℓ_{b} − 2), u_{0} = a^{b_{0}} (mod n), and r̄_{i} ∈_{R} ℤ_{Q}.

2. To prove that a^{b} ≡ d (mod n) holds, the prover sends all her commitments to the verifier and then they carry out the protocol

S_{exp} := PK⟨(α, β, ξ, χ, γ, δ, ε, ζ, η, (λ_{i}, μ_{i}, ν_{i}, ξ_{i}, σ_{i}, τ_{i}, ϑ_{i}, φ_{i}, ψ_{i})_{i=1}^{ℓ_{b} −1}, (κ_{i}, ρ_{i})_{i=1}^{ℓ_{b} −2}, ) :

c_{a} = g^{α} h^{β} ∧ −2ℓ̈ < α < 2ℓ̈ ∧  (1)
c_{d} = g^{γ} h^{δ} ∧ −2ℓ̈ < γ < 2ℓ̈ ∧  (2)
c_{n} = g^{ε}h^{ζ} ∧ −2ℓ̈ < ε < 2ℓ̈ ∧  (3)
( ∏_{i=0}^{ℓ_{b} −1} c_{b_{i}}^{2^{i}} )/c_{b} = h^{η} ∧  (4)
c_{v_{1}} = g^{λ_{1}} h^{μ_{1}} ∧ … ∧ c_{v_{ℓ_{b} −1}} = g^{λ_{ℓ_{b} −1}} h^{μ_{ℓ_{b} −1}} ∧  (5)

c_{v_{1}} = c_{a}^{α} c_{n}^{ν_{1}} h^{ξ_{1}} ∧ c_{v_{2}} = c_{v_{1}}^{λ_{1}} c_{n}^{ν_{2}} h^{ξ_{2}} ∧ … ∧ c_{v_{ℓ_{b} −1}} = c_{v_{ℓ_{b} −2}}^{λ_{ℓ_{b} −2}} c_{n}^{ν_{ℓ_{b} −1}} h^{ξ_{ℓ_{b} −1}} ∧(6)

−2ℓ̈ < λ_{1} < 2ℓ̈ ∧ … ∧ −2ℓ̈ < λ_{ℓ_{b} −1} < 2ℓ̈ ∧  (7)
−2ℓ̈ < ν_{1} < 2ℓ̈ ∧ … ∧ −2ℓ̈ < ν_{ℓ_{b} −1} < 2ℓ̈ ∧  (8)
c_{u_{1}} = g^{κ_{1}} h^{ρ_{1}} ∧ … ∧ c_{u_{ℓ_{b} −2}} = g^{κ_{ℓ_{b} −2}} h^{ρ_{ℓ_{b} −2}} ∧  (9)
−2ℓ̈ < κ_{1} < 2ℓ̈ ∧ … ∧ −2ℓ̈ < κ_{ℓ_{b} −2} < 2ℓ̈ ∧  (10)
((c_{b_{0}} = h^{σ_{0}} ∧ c_{u_{0}} /g = h^{τ_{0}} ) ∨ (c_{b_{0}} /g = h^{ϑ_{0}} ∧ c_{u_{0}} /c_{a} = h^{ψ_{0}} )) ∧ (11)
((c_{b_{1}} = h^{σ_{1}} ∧ c_{u_{1}} /c_{u_{0}} = h^{τ_{1}} ) ∨  (12)
(c_{b_{1}} /g = h^{ϑ_{1}} ∧ c_{u_{1}} = c_{u_{0}}^{λ_{1}} c_{n}^{φ_{1}} h^{ψ_{1}} ∧ −2ℓ̈ < φ_{1} < 2ℓ̈)) ∧ … ∧
((c_{b_{ℓ_{b} −2}} = h^{σ_{ℓ_{b} −2}} ∧ c_{u_{ℓ_{b} −2}} /c_{u_{ℓ_{b} −3}} = h^{τ_{i}} ) ∨  (13)

(c_{b_{ℓ_{b} −2}} /g = h^{ϑ_{ℓ_{b} −2}} ∧ c_{u_{ℓ_{b} −2}} = c_{u_{ℓ_{b} −3}}^{λ_{ℓ_{b} −2}} c_{n}^{φ_{ℓ_{b} −2}} h^{ψ_{ℓ_{b} −2}} ∧ −2ℓ̈ < φ_{ℓ_{b} −2} < 2ℓ̈)) ∧

((c_{b_{ℓ_{b} −1}} = h^{σ_{ℓ_{b} −1}} ∧ c_{d}/c_{u_{ℓ_{b} −2}} = h^{τ_{i}} ) ∨  (14)

(c_{b_{ℓ_{b} −1}} /g = h^{ϑ_{ℓ_{b} −1}} ∧ c_{d} = c_{u_{ℓ_{b} −2}}^{λ_{ℓ_{b} −1}} c_{n}^{φ_{ℓ_{b} −1}} h^{ψ_{ℓ_{b} −1}} ∧ −2ℓ̈ < φ_{ℓ_{b} −1} < 2ℓ̈))⟩ .

Let us now explain why this protocol proves that a^{b} ≡ d (mod n) holds and consider the clauses of sub-protocol S_{exp}. What the Clauses 1–3 prove should be clear. The Clause 4 shows that the c_{b_{i}} ’s indeed commit to the bits of the integer committed to in c_{b} (that these are indeed bits is shown in the Clauses 11–14). From this it can further be concluded that c_{b} commits to a value smaller that 2^{ℓ_{b}} . The Clauses 5–8 prove that the c_{v_{i}} ’s indeed contain a^{2^{i}} (mod n) (cf. Section 3.1). Finally, the Clauses 9–14 show that c_{u_{i}} ’s commit to the intermediary results of the square & multiply algorithm and that c_{d} commits to the result: The Clauses 9 and 10 show that the c_{u_{i}} ’s commit to integers that lie in {−2ℓ̈+ 1, …, 2ℓ̈− 1} (for c_{u_{0}} this follows from Clause 11). Then, Clause 11 proves that either c_{b_{0}} commits to a 0 and c_{u_{0}} commits to a 1 or c_{b_{0}} commits to a 1 and c_{u_{0}} commits to the same integer as c_{a}. The Clauses 12 and 13, show that for i = 1 to ℓ_{b} −2 either c_{b_{i}} commits to a 0 and c_{u_{i}} commits to same integer as c_{u_{i−1}} or c_{b_{i}} commits to a 1 and c_{u_{i}} commits to the modular product of the value c_{u_{i−1}} commits and of a^{2^{i}} (mod n) (which c_{v_{i}} commits to). Finally, Clause 14 proves (in a similar manner as the Clauses 12 and 13) that c_{d} commits to the result of the square & multiply algorithm and thus to a^{b} (mod n).

Theorem 2. Let a, b, d, and n be integers that are committed in c_{a}, c_{b}, c_{d}, and c_{n} by the prover and let c_{b_{0}} , …, c_{b_{ℓ−1}} , c_{v_{1}} , …, c_{v_{ℓ_{b} −1}} , c_{u_{0}} , …, c_{u_{ℓ_{b} −2}} be her auxiliary commitments. Then the protocol S_{exp} is a statistical zero-knowledge proof that the equation a^{b} ≡ d (mod n) holds.

Proof. The proof is straight forward from Theorem 1 and the explanations given above that c_{b_{0}} , …, c_{b_{ℓ−1}} , c_{v_{1}} , …, c_{v_{ℓ_{b} −1}} , c_{u_{0}} , …, c_{u_{ℓ_{b} −2}} , S implement the square & multiply algorithm step by step.

In the following, when denoting a protocol, we will abbreviate the protocol S_{exp} by a clause like (α^{β} ≡ γ (mod δ)) to the statement that is proven and assume that the prover send the verifier all necessary commitments; e.g.,

PK⟨(α, β, γ, δ, α̃, β̃, γ̃, δ̃) : c_{a} = g^{α} hα̃ ∧ c_{b} = g^{β} hβ̃ ∧ c_{d} = g^{γ} hγ̃ ∧

c_{n} = g^{δ}hδ̃ ∧ (α^{β} ≡ γ (mod δ))⟩.

3.3 Efficiency Analysis

For both S_{+} and S_{∗} the prover and the verifier both need to compute 5 multiexponentiations per round. The communication per round is about the size of 10 group elements and 5ϵℓ bits in case of S_{+} and about the size of 11 group elements and 5ϵℓ bits in case of S_{∗}.

In case of the exponentiation proof the verifier and the prover need to compute about 6ℓ_{b} multi-exponentiations per round, while the prover needs to compute about 3ℓ_{b} multi-exponentiations for the commitments to the intermediary results of the square & multiply algorithm. The communication cost per round is about the size of 12ℓ_{b} group elements and 4ℓ_{b}ϵℓ bits and an initial 3ℓ_{b} group element which are the commitments to the intermediary results of the square & multiply algorithm.

3.4 Extension to a General Multivariate Polynomial

Let us outline how the correct computation of a general multivariate polynomial equation of form

f(x_{1}, …, x_{t}, a_{1}, …, a_{l}, b_{1,1} , …, b_{l,t} , n) =∑_{i=1}^{l} a_{i} ∏_{j=1}^{t} x_{j}^{b_{i,j}} ≡ 0 (mod n)

where all integers x_{1}, …, x_{t}, a_{1}, …, a_{l}, b_{1,1} , …, b_{l,t} , and n might only given as commitments can be shown: The prover commits to all the summands s_{1} := a_{1} ∏ _{j=1}^{t} x_{j}^{b_{1,j}} (mod n), …, s_{l} := a_{l} ∏ _{j=1}^{t} x_{j}^{b_{l,j}} (mod n) and shows that the sum of these summands is indeed zero modulo n. Then, she commits to all the product terms p_{1,1} := x_{1}^{b_{1,1}} (mod n), …, p_{t,l} := x_{t}^{b_{l,t}} (mod n) of the product and shows that s_{i} ≡ a_{i} ∏ _{j=1}^{t} p_{i,j} (mod n). Finally, she shows that p_{i,j} ≡ x_{j}^{b_{i,j}} (mod n) using the modular exponentiation proof described above and that for all i the same x_{j} is in p_{i,j} . Clearly, several such polynomials can be combined as well.

4 A Proof That a Secret Number is a Pseudo-Prime

In this section we describe how the prover and the verifier can carry out a primality test for an integer that is only given by a commitment. Some primality tests reveal information about the structure of the prime and are hence not suited unless one is willing to give away this information. Examples of such tests are the Miller-Rabin test [26, 29] or the one based on Pocklington’s theorem. A test that does not reveal such information is the one due to Lehmann [25] which we describe in the next subsection.

4.1 Lehmann’s Primality Test

Lehmann’s primality test is variation of the Solovay-Strassen [31] primality test and based on the following theorem [24]:

Theorem 3. An odd integer n > 1 is prime if and only if

∀a ∈ ℤ_{n}^{∗} : a^{(n−1)/2} ≡ ±1 (mod n) and ∃a ∈ ℤ_{n}^{∗} : a^{(n−1)/2} ≡ −1 (mod n) .

This theorem suggest the following probabilistic primality test:

• choose k random bases a_{1}, …, a_{k} ∈ ℤ_{n}^{∗},

• check whether a_{i}^{(n−1)/2} ≡ ±1 (mod n) holds for all i’s and whether a_{i}^{(n−1)/2} ≡ −1 (mod n) holds for at least one i.

The probability that a non-prime n passes this test is at most 2^{−k}. Note that in case n and (n − 1)/2 are both odd, the condition that a_{i}^{(n−1)/2} ≡ −1 (mod n) holds for at least one i can be omitted. In this special case the Lehmann-test is equivalent to the Miller-Rabin test and the failure probability is at most 4^{−k} [29].

4.2 Proving the Pseudo-Primality of a Committed Number

We now show how the prover and the verifier can do Lehmann’s primality test for a number committed by prover such that the verifier is convinced that the test was correctly done but does not learn any other information. The general idea is that the prover commits to t random bases a_{i} (of course, the verifier must be assured that the a_{i}’s are chosen at random) and then prove that for these bases a_{i}^{(n−1)/2} ≡ ±1 (mod n) holds. Furthermore, the prover must commit to a base, say ã, such that ã^{(n−1)/2} ≡ −1 (mod n) holds to satisfy the second condition in Theorem 3.

Let ℓ be an integer such that n < 2^{ℓ} holds and let ϵ > 1 be security parameter. As in the previous section, a group G of prime order Q > 2^{2ϵℓ+5} and two generators g and h are chosen, such that log_{g} h is not known. Let c_{n} := g^{n} h^{r_{n}} with r_{n} ∈_{R} ℤ_{Q} be the prover’s commitment to the integer on which the primality test should be performed.

The following four steps constitute the protocol.

1. The prover picks random â_{i} ∈_{R} ℤ_{n} for i = 1, …, t and commits to them as câ_{i} := gâ_{i} h^{râ_{i}} with râ_{i} ∈_{R} ℤ_{Q} for i = 1, …, t. She sends câ_{1} , …, câ_{t} to the verifier.

2. The verifier picks random integers −2^{ℓ} < ǎ_{i} < 2^{ℓ} for i = 1, …, t and sends them to the prover.

3. The prover computes a_{i} := â_{i} + ǎ_{i} (mod n), c_{a_{i}} := g^{a_{i}} h^{r_{a_{i}}} with r_{a_{i}} ∈_{R} ℤ_{Q}, d_{i} := a_{i}^{(n−1)/2} (mod n), and c_{d_{i}} := g^{d_{i}} h^{r_{d_{i}}} with r_{d_{i}} ∈_{R} ℤ_{Q} for all i = 1, …, t. Moreover, the prover commits to (n−1)/2 by c_{b} := g^{(n−1)/2} h^{r_{b}} with r_{b} ∈_{R} ℤ_{Q}. Then the prover searches a base ã such that ã^{(n−1)/2} ≡ −1 (mod n) holds and commits to ã by cã := gãh^{rã} with rã ∈_{R} ℤ_{Q}.

4. The prover sends c_{b}, cã, c_{a_{1}} , …, c_{a_{t}} , c_{d_{1}} , …, c_{d_{t}} to the verifier and then they carry out the following (sub-)protocol

S_{p} := PK⟨(α, β, γ, ν, ξ, ρ, κ, (δ_{i}, ε_{i}, ζ_{i}, η_{i}, ϑ_{i}, κ_{i}, ρ_{i}, κ_{i}, μ_{i}, ψ_{i})_{i=1}^{t} :

c_{b} = g^{α} h^{β} ∧ −2ℓ̈ < α < 2ℓ̈ ∧  (15)
c_{n} = g^{ν} h^{ξ} ∧ −2ℓ̈ < ν < 2ℓ̈ ∧  (16)
c_{b}^{2}g/c_{n} = h^{γ} ∧  (17)
cã = g^{ρ}h^{κ} ∧ (ρ^{α} ≡ −1 (mod ν)) ∧  (18)
câ_{1} = g^{δ_{1}} h^{ε_{1}} ∧ … ∧ câ_{t} = g^{δ_{t}} h^{ε_{t}} ∧  (19)
c_{a_{1}} /gǎ_{1} = g^{δ_{1}} c_{n}^{ζ_{1}} h^{η_{1}} ∧ … ∧ c_{a_{t}} /gǎ_{t} = g^{δ_{t}} c_{n}^{ζ_{t}} h^{η_{t}} ∧  (20)
−2ℓ̈ < δ_{1} < 2ℓ̈ ∧ … ∧ −2ℓ̈ < δ_{t} < 2ℓ̈ ∧  (21)
−2ℓ̈ < ζ_{1} < 2ℓ̈ ∧ … ∧ −2ℓ̈ < ζ_{t} < 2ℓ̈ ∧  (22)
c_{a_{1}} = g^{ρ_{1}} h^{κ_{1}} ∧ … ∧ c_{a_{t}} = g^{ρ_{t}} h^{κ_{t}} ∧  (23)
(c_{d_{1}} /g = h^{ϑ_{1}} ∨ c_{d_{1}} g = h^{ϑ_{1}} ) ∧ … ∧ (c_{d_{t}} /g = h^{ϑ_{t}} ∨ c_{d_{t}} g = h^{ϑ_{t}} ) ∧  (24)
c_{d_{1}} = g^{μ_{1}} h^{ψ_{1}} ∧ … ∧ c_{d_{t}} = g^{μ_{t}} h^{ψ_{t}} ∧  (25)
(ρ_{1}^{α} ≡ μ_{1} (mod ν)) ∧ … ∧ (ρ_{t}^{α} ≡ μ_{t} (mod ν))⟩ .  (26)

This concludes the protocol. In Step 1 and 2 of the protocol, the prover and the verifier together choose the random bases a_{1}, …, a_{t} for the primality test. Each base is the sum (modulo n) of the random integer the verifier chose and the one the prover chose. Hence, both parties are ensured that the bases are random, although the verifier does not get any information about the bases finally used in the primality test. That the bases are indeed chosen according to this procedure is shown in the Clauses 19–23 of the sub-protocol S_{p}, the correct generation of the random values a_{i}, committed in c_{a_{i}} , is proved. The Clauses 16–17 prove that indeed (n − 1)/2 is committed in c_{b} and the Clause 18 shows that there exists a base ã such that ã^{(n−1)/2} ≡ −1 (mod n). In the Clause 24 it is shown that the values committed in c_{d_{i}} are either equal to −1 or to 1. Finally, in Clause 26 (together with the Clauses 15, 16, 23, and 25) it is proved that a_{i}^{(n−1)/2} ≡ d_{i} (mod n), i.e., a_{i}^{(n−1)/2} (mod n) ∈ {−1, 1} and thus the conditions that n is a prime with error-probability 2^{−t} are met.

Note that all modular exponentiations in Clause 26 have the same b and n and hence the proofs for these parts can be optimized. In particular, this is the case for the Clauses 3, 4, and 11–14 in S_{exp}.

Theorem 4. Given a commitment c_{n} to an integer, the above protocol is a statistical zeroknowledge proof that the committed integer is a prime with error-probability at most 2^{−t} for the primality-test.

Proof. The proof is straight forward from the Theorems 1, 2, and 3.

Similar as for modular exponentiation we will abbreviate the above protocol by adding a clause such as α ∈ pseudoprimes (t) to the statement that is proven, where t denotes the number of bases used in the primality test.

Remark. If (n − 1)/2 is odd and the prover is willing to reveal that, she can additionally prove that she knows χ and ψ such that c_{b}/g = (g^{2})^{χ}h^{ψ} and −2ℓ̈ < χ < 2ℓ̈ holds and skip the Clause 18. This results in a statistical zero-knowledge proof that n of form n = 2w + 1 is prime and w is odd with error-probability at most 2^{−2t}.

4.3 Efficiency Analysis

Assume that the commitment to the prime n is given. Altogether t + 1 proofs that a modular exponentiation holds are needed where the exponents are about log n bits. Thus, the verifier needs to compute about 6t log n multi-exponentiations per round and the prover needs to compute about 2t log n multi-exponentiations for the commitments to the intermediary results of the square & multiply algorithm. The communication cost per round is about the size of 12t log n group elements and 4t log nϵℓ bits and an initial 2t log n group element which are the commitments to the intermediary results of the square & multiply algorithm and the commitments to the bases for the primality test.

5 Proving that an RSA Modulus Consists of Two Safe Primes

We finally present protocols for proving that an RSA modulus consists of two safe primes. First, we restrict ourselves to the case where the modulus is not known to the verifier, i.e., only a commitment of the modulus is given. Later, we will discuss improvements for cases when the RSA modulus is known to the verifier.

5.1 A Protocol For a Secret RSA Modulus

Let 2^{ℓ} be an upper-bound on the length of the largest factor of the modulus and let ϵ > 1 be a security parameter. Furthermore, a group G of prime order Q > 2^{2ϵℓ+5} and two generators g and h are chosen, such that log_{g} h is not known and computing discrete logarithms is infeasible.

Let c_{n} := g^{n} h^{r_{n}} be the prover’s commitment an integer n, where she choose r_{n} ∈_{R} ℤ_{Q} and let p and q denote the two prime factors of n. The following is a protocol that allows her to convince the verifier that c_{n} commits to the product of two safe (pseudo-)primes.

1. The prover computes the commitments c_{p} := g^{p}h^{r_{p}} , cp̃ := g^{(p−1)/2} h^{rp̃} , c_{q} := g^{q} h^{r_{b}} , and cq̃ := g^{(q−1)/2} h^{rp̃} with r_{p}, rp̃, r_{q} , rq̃ ∈_{R} ℤ_{Q} and sends all these commitments to the verifier.

2. The two parties carry out the following protocol

S_{51} := PK{(α, β, γ, δ, ρ, ν, ξ, χ, ε, ζ, η) :

cp̃ = g^{α} h^{β} ∧ (−2ℓ̈ < α < 2ℓ̈) ∧  (27)
cq̃ = g^{γ} h^{δ} ∧ (−2ℓ̈ < δ < 2ℓ̈) ∧  (28)
c_{p} = g^{ρ}h^{ν} ∧ c_{q} = g^{ξ}h^{χ} ∧  (29)
c_{p}/(c2 ; p̃g) = h^{ε} ∧ c_{q} /(c2 ; q̃g) = h^{ζ} ∧ c_{n} /(c_{p}c_{q} ) = h^{η} ∧  (30)

               α ∈ pseudoprimes (t) ∧ γ ∈ pseudoprimes (t) ∧  (31)
                ρ ∈ pseudoprimes (t) ∧ ξ ∈ pseudoprimes (t)} ,  (32)

where t denotes the number of bases used in the Lehmann-primality tests.

Theorem 5. Let n be an integer that is committed by c_{n}. Then the above protocol is a statistical zero-knowledge proof that n is an RSA modulus of form n = pq where p, q, (p − 1)/2 and (q − 1)/2 are primes with error-probability at most 2^{−t} each of for the primality tests.

Proof. The proof is straight forward from the Theorems 1, 2, and 4.

The efficiency is reigned by the (pseudo-)primality-proofs and thus about four times as high as for a single (pseudo-)primality-proof (cf. Subsection 4.3).

5.2 A Protocol For a Publicly Known RSA Modulus

We now consider the case where the modulus n is publicly known. In case n fulfils certain side-conditions (see below), it is more efficient to first run the protocol due to Gennaro et al. [20] (which includes the proofs proposed by Peralta & van de Graaf [32] and by Boyar et al. [3]). This protocol is a statistical zero-knowledge proof system that there exist two integers a, b ≥ 1 such that n consists of two primes p = 2p̃^{a} + 1 and q = 2q̃^{b} + 1 with p, q, p̃, q̃ ≢ 1 (mod 8), p ≢ q (mod 8), and p̃ ≢ q̃ (mod 8). Given the fact that (p − 1)/2 and (p − 1)/2 are prime powers, the probability that they pass a single round of the Lehmann’s primality test for any a > 1 and b > 1, is at most p̃^{1−a} ≤ \sqrt{2/(p − 1)} and q̃^{1−a} ≤ \sqrt{2/(q − 1)}, respectively, if they are not prime. Hence, if p and q are sufficiently large, a single round of the Lehmann-primality test on (p − 1)/2 and (q − 1)/2 will be sufficient to prove their (pseudo-)primality.

We now describe the protocol that allows the prover to prove the verifier that a given integer n is the product of two safe (pseudo-)primes.

1. First the prover computes c_{p} := g^{p}h^{r_{p}} , cp̃ := g^{(p−1)/2} h^{rp̃} , c_{q} := g^{q} h^{r_{b}} , and cq̃ := g^{(q−1)/2} h^{rp̃} with r_{p}, rp̃, r_{q} , rq̃ ∈_{R} ℤ_{Q} and sends these commitments together with n to the verifier.

2. The prover and the verifier carry out the protocol by Gennaro et al. [20]

3. and then the protocol denoted

S_{52} := PK{(α, β, γ, δ, ρ, ϵ, ξ, χ, ε, ζ, η) :

cp̃ = g^{α} h^{β} ∧ (−2^{ℓ̈/2} < α < 2^{ℓ̈/2} ) ∧ cq̃ = g^{γ} h^{δ} ∧ (−2^{ℓ̈/2} < δ < 2^{ℓ̈/2} ) ∧ (33)
c_{p} = g^{ρ}h^{ϵ} ∧ c_{q} = g^{ξ}h^{χ} ∧ c_{p}/(c2 ; p̃g) = h^{ε} ∧ c_{q} /(c2 ; q̃g) = h^{ζ} ∧  (34)
g^{n} /(c_{p}c_{q} ) = h^{η} ∧ γ ∈ pseudoprimes (1) ∧ α ∈ pseudoprimes (1)} .(35)

Theorem 6. Let n = pq be a given integer that passes the test given in [20] with error probability at most 2^{−z} for an integer z ≥ 1. Then the above protocol is a statistical zeroknowledge proof that n is an RSA modulus of form n = pq where p, q, (p − 1)/2 and (q − 1)/2 are primes with error probability at most 1 − (1 − 2^{−z})(1 − \sqrt{2/(p − 1)})(1 − \sqrt{2/(q − 1)}) < 2^{−z} + \sqrt{2/(p − 1)} + \sqrt{2/(q − 1)} + 2^{−z} \sqrt{2/(p − 1)}\sqrt{2/(q − 1)}.

The efficiency for this protocol is dominated by the efficiency of a single round (i.e., t = 1) of the (pseudo-)primality proof described in the previous section and the efficiency of protocol of Gennaro et al. [20].

6 Conclusion

We have presented efficient protocols for proving that modular relations among secret values (including the modulus!) hold and for proving that an given (or only committed-to) number is the product of two safe primes.

We note that it is obvious how to use our techniques to get a protocol for proving that n is the product of two strong primes [22], i.e., (p − 1)/2, (q − 1)/2, (p + 1)/2 and (q + 1)/2 are primes or have a large prime factor. Lower bounds on p, q, and on n might also be shown. Also, factors r other than 2 in (p − 1)/r could easily be incorporated.

References

[1] E. Bach and J. Shallit. Factoring with cyclotomic polynomials. In Proc. 26th IEEE Symposium on Foundations of Computer Science (FOCS), pages 443–450, 1985.

[2] D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1296 of Lecture Notes in Computer Science, pages 425–439. Springer Verlag, 1997.

[3] J. Boyar, K. Friedl, and C. Lund. Practical zero-knowledge proofs: Giving hints and using deficiencies. Journal of Cryptology, 4(3):185–206, 1991.

[4] S. Brands. Electronic cash systems based on the representation problem in groups of prime order. In Preproceedings of Advances in Cryptology — CRYPTO ’93, pages 26.1–26.15, 1993.

[5] S. Brands. Rapid demonstration of linear relations connected by boolean operators. In W. Fumy, editor, Advances in Cryptology — EUROCRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 318–333. Springer Verlag, 1997.

[6] G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156–189, Oct. 1988.

[7] J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1296 of Lecture Notes in Computer Science, pages 410–424. Springer Verlag, 1997.

[8] J. Camenisch and M. Stadler. Proof systems for general statements about discrete logarithms. Technical Report TR 260, Institute for Theoretical Computer Science, ETH Zürich, Mar. 1997.

[9] A. Chan, Y. Frankel, and Y. Tsiounis. Easy come – easy go divisible cash. In K. Nyberg, editor, Advances in Cryptology — EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 561–575. Springer Verlag, 1998.

[10] D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In D. Chaum and W. L. Price, editors, Advances in Cryptology — EUROCRYPT ’87, volume 304 of Lecture Notes in Computer Science, pages 127–141. Springer-Verlag, 1988.

[11] D. Chaum, J.-H. Evertse, J. van de Graaf, and R. Peralta. Demonstrating possession of a discrete logarithm without revealing it. In A. M. Odlyzko, editor, Advances in Cryptology — CRYPTO ’86, volume 263 of Lecture Notes in Computer Science, pages 200–212. Springer-Verlag, 1987.

[12] D. Chaum and T. P. Pedersen. Wallet databases with observers. In E. F. Brickell, editor, Advances in Cryptology — CRYPTO ’92, volume 740 of Lecture Notes in Computer Science, pages 89–105. Springer-Verlag, 1993.

[13] H. Cohen. A Course in Computational Algebraic Number Theory. Number 138 in Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993.

[14] R. Cramer and I. Damgård. Zero-knowledge proof for finite field arithmetic, or: Can zero-knowledge be for free? In H. Krawczyk, editor, Advances in Cryptology — CRYPTO ’98, volume 1642 of Lecture Notes in Computer Science, pages 424–441, Berlin, 1998. Springer Verlag.

[15] R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Y. G. Desmedt, editor, Advances in Cryptology — CRYPTO ’94, volume 839 of Lecture Notes in Computer Science, pages 174–187. Springer Verlag, 1994.

[16] E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1294 of Lecture Notes in Computer Science, pages 16–30. Springer Verlag, 1997.

[17] E. Fujisaki and T. Okamoto. A practical and provably secure scheme for publicly verifiable secret sharing and its applications. In K. Nyberg, editor, Advances in Cryptology — EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 32–46. Springer Verlag, 1998.

[18] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust and efficient sharing of RSA functions. In N. Koblitz, editor, Advances in Cryptology — CRYPT0 ’96, volume 1109 of Lecture Notes in Computer Science, pages 157–172, Berlin, 1996. IACR, Springer Verlag.

[19] R. Gennaro, H. Krawczyk, and T. Rabin. RSA-based undeniable signatures. In B. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, volume 1296 of Lecture Notes in Computer Science, pages 132–149. Springer Verlag, 1997.

[20] R. Gennaro, D. Micciancio, and T. Rabin. An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products. In 5rd ACM Conference on Computer and Communicatons Security, 1998.

[21] O. Goldreich, S. Micali, and A. Wigderson. How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design. In A. M. Odlyzko, editor, Advances in Cryptology — CRYPTO ’86, volume 263 of Lecture Notes in Computer Science, pages 171–185. Springer-Verlag, 1987.

[22] J. Gordon. Strong RSA keys. Electronics Letters, 20(12):514–516, 1984.

[23] K. Koyama, U. Maurer, T. Okamoto, and S. Vanstone. New public-key schemes based on elliptic curves over the ring Z_{n}. In J. Feigenbaum, editor, Advances in Cryptology — CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 252–266. Springer-Verlag, 1992.

[24] E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.

[25] D. J. Lehmann. On primality tests. SIAM Journal of Computing, 11(2):374–375, May 1982.

[26] G. L. Miller. Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences, 13:300–317, 1976.

[27] T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology – CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 129–140. Springer Verlag, 1992.

[28] J. M. Pollard. Theorems on factorization and primality testing. Proc. Cambridge Philosophical Society, 76:521–528, 1974.

[29] M. O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12:128–138, 1980.

[30] C. P. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology, 4(3):239–252, 1991.

[31] R. Solovay and V. Strassen. A fast monte-carlo test for primality. SIAM Journal on Computing, 6(1):84–85, Mar. 1977.

[32] J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public key. In C. Pomerance, editor, Advances in Cryptology — CRYPTO ’87, volume 293 of Lecture Notes in Computer Science, pages 128–134. Springer-Verlag, 1988.

[33] H. C. Williams. A p + 1 method of factoring. Mathematics of Computation, 39(159):225–234, 1982.

A Proving a Secret’s Length in Groups with Known Order

In this section we review the statistical zero-knowledge proof of knowledge of the discrete logarithm, say x, of y to the base gand that, additionally, x lies within a given interval. This proof is based on a protocols that appeared in [16, 9].

Prover  Verifier
(g, Q, y, x)  (g, Q, y)
]  ]

r ∈_{R} {−2^{ϵℓ_{2}} , …, 2^{ϵℓ_{2}} }

t := g^{r} t \overline{}
c ∈ {0, 1}
\overline{}c

s := r − c(x − 2^{ℓ_{1}} ) (in ℤ)

s  \overline{}

−2^{ϵℓ_{2} +1} <^{?} s <^{?} 2^{ϵℓ_{2} +1}

t =^{?} g^{s−c2^{ℓ_{1}}} y^{c}

]

                                                                (yes /no)

Figure 1: When repeated sufficiently many times, this protocol allows a prover to convince a verifier that the secret he committed to in y lies within the bound {2^{ℓ_{1}} − 2^{ϵℓ_{2} +2} , …, 2^{ℓ_{1}} + 2^{ϵℓ_{2} +2} } for given parameters ϵ, ℓ_{1}, and ℓ_{2}.

Theorem 7. Let G be a group of prime order Q, g and h two generators of G such that log_{g} h is unknown, ϵ > 1 be a security parameter, and ℓ_{1} < log Q and ℓ_{2} be lengths. Let y be a public group element. When sequentially repeated j = Θ(poly(log Q)) times, the protocol depicted in Figure 1 is a proof of knowledge of a secret x ∈ {2^{ℓ_{1}} − 2^{ϵℓ_{2} +2} , …, 2^{ℓ_{1}} + 2^{ϵℓ_{2} +2} } such that y = g^{x} and is statistical zero-knowledge for ℓ_{2} = poly(log Q)) and if x ∈ {2^{ℓ_{1}} − 2^{ℓ_{2}} , …, 2^{ℓ_{1}} + 2^{ℓ_{2}} }.

Proof (Sketch).Proof of knowledge: First, the knowledge extractor needs two find views of accepting protocol-runs with the same t but different c’s as usual. Let (t, c, s) and (t, c̃, s̃) these views. Without loss of generality we can assume that c = 0 and c̃ = 1. Then we have t = g^{s−2^{ℓ_{1}}} y = gs̃ and thus y = g^{s̃−s+2^{ℓ_{1}}} . Thus one can compute

x̂ := s̃− s + 2^{ℓ_{1}} (mod Q)

such that y = gx̂ holds. Due to the bounds that s and s̃ satisfy, it follows that −2^{ϵℓ_{2} +2} + 2^{ℓ_{1}} < x̂ < 2^{ϵℓ_{2} +2} + 2^{ℓ_{1}} must hold, which was to be shown.

Statistical zero-knowledge: We provide only a simulator for one round of the protocol. Extending this simulator to a simulator for all rounds is straight forward.

The simulator randomly chooses c′ ∈_{R} {0, 1} and s′ ∈_{R} {−2^{ϵℓ_{2}} , …, 2^{ϵℓ_{2}} } according to the uniform distribution. Using these values, the simulator computes t′ = g^{s′} y^{c′} which he feeds the verifier. If the verifier responds with c′ the simulator outputs (t′, c′, s′). To prove that these values are statistical indistinguishable from a view of a protocol run with the prover, it suffices to consider the probability distribution P_{S}(s) of the response s of the prover and P_{S′}(s′) according to which the simulator chooses s′.

If the prover chooses r uniformly at random from {−2^{ϵℓ_{2}} , …, −2^{ϵℓ_{2}} } and the secret key x − 2^{ℓ_{1}} randomly from {−2^{ℓ_{2}} , …, 2^{ℓ_{2}} } according to any distribution, we have

P_{S}(s) \{ \begin{matrix}= 0 & for s < −2^{ϵℓ_{2}} − 2^{ℓ_{2}} \\ ≤ 2^{−ϵℓ_{2}} & for − 2^{ϵℓ_{2}} − 2^{ℓ_{2}} ≤ s < −2^{ϵℓ_{2}} + 2^{ℓ_{2}} \\ = 2^{−ϵℓ_{2}} & for − 2^{ϵℓ_{2}} + 2^{ℓ_{2}} ≤ s ≤ 2^{ϵℓ_{2}} − 2^{ℓ_{2}} \\ ≤ 2^{−ϵℓ_{2}} & for 2^{ϵℓ_{2}} − 2^{ℓ_{2}} < s ≤ 2^{ϵℓ_{2}} + 2^{ℓ_{2}} \\ = 0 & for 2^{ϵℓ_{2}} + 2^{ℓ_{2}} < s . \end{matrix}

This holds for any distribution of c over {0, 1}. Thus we have

∑_{α∈ℤ} |P_{S}(α) − P_{S′}(α)| ≤ \frac{2^{ℓ_{2} +2}}{2^{ϵℓ_{2}}} = \frac{4}{(2^{ℓ_{2}} )^{(ϵ−1)}}

For ℓ_{2} and ϵ as stated in the theorem, the last term can be expressed as one over a polynomial in the input length, and therefore the two distributions are statistical indistinguishable.

The relation ϵℓ_{2} + 2 < log Q should hold, as otherwise the any secret value will lie within the bound.

In the above theorem there is a “hole” in the range of the prover’s secret key x, i.e., the protocol is complete and zero-knowledge only for (x−2^{ℓ_{1}} ) ∈ {−2^{ℓ_{2}} , …, 2^{ℓ_{2}} }. For (x−2^{ℓ_{1}} ) ∈ {−2^{ϵℓ_{2} +1} , …, 2^{ϵℓ_{2} +1} }/{−2^{ℓ_{2}} , …, 2^{ℓ_{2}} } the prover’s success probability is smaller than 1 but larger than 2^{−j}, depending on the size of |(x − 2^{ℓ_{1}} )| − 2^{ℓ_{2}}.

B Square & Multiply Algorithm for d ≡ a^{b} (mod n)

The following algorithm computes d ≡ a^{b} (mod n) (we use the same names for all variables as in Section 3.2).

v_{0} := a if b_{0} = 1 then u_{0} := a else u_{0} := 1 fi

for i = 1 to ℓ_{b} − 1 do

v_{i} := v_{i−1} · v_{i−1} (mod n) % thus v_{i} ≡ a^{2^{i}} (mod n)

  if b_{i} = 1 then

u_{i} := u_{i−1} · v_{i} (mod n) % thus u_{i} ≡ u_{i−1} · a^{2^{i}} (mod n)

  else

u_{i} := u_{i−1}

  endif
endfor

d := u_{ℓ_{b} −1}

Recent BRICS Report Series Publications

RS-98-29 Jan Camenisch and Markus Michels. Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. November 1998. 19 pp.

RS-98-28 Rasmus Pagh. Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time. November 1998. 15 pp.

RS-98-27 Jan Camenisch and Markus Michels. A Group Signature Scheme Based on an RSA-Variant. November 1998. 18 pp. Preliminary version appeared in Ohta and Pei, editors, Advances in Cryptology: 4th ASIACRYPT Conference on the Theory and Applications of Cryptologic Techniques, ASIACRYPT ’98 Proceedings, LNCS 1514, 1998, pages 160–174.

RS-98-26 Paola Quaglia and David Walker. On Encoding pπ in mπ. October 1998. 27 pp. Full version of paper to appear in Foundations of Software Technology and Theoretical Computer Science: 18th Conference, FCT&TCS ’98 Proceedings, LNCS, 1998.

RS-98-25 Devdatt P. Dubhashi. Talagrand’s Inequality in Hereditary Settings. October 1998. 22 pp.

RS-98-24 Devdatt P. Dubhashi. Talagrand’s Inequality and Locality in Distributed Computing. October 1998. 14 pp.

RS-98-23 Devdatt P. Dubhashi. Martingales and Locality in Distributed Computing. October 1998. 19 pp.

RS-98-22 Gian Luca Cattani, John Power, and Glynn Winskel. A Categorical Axiomatics for Bisimulation. September 1998. ii+21 pp. Appears in Sangiorgi and de Simone, editors, Concurrency Theory: 9th International Conference, CONCUR ’98 Proceedings, LNCS 1466, 1998, pages 581–596.

RS-98-21 John Power, Gian Luca Cattani, and Glynn Winskel. A Representation Result for Free Cocompletions. September 1998. 16 pp.

RS-98-20 Søren Riis and Meera Sitharam. Uniformly Generated Submodules of Permutation Modules. September 1998. 35 pp.

RS-98-19 Søren Riis and Meera Sitharam. Generating Hard Tautologies Using Predicate Logic and the Symmetric Group. September 1998. 13 pp.