Protocols for Secure Generation of Shared RSA Keys

DARPA Contract F30602-97-C-0326

Data Item Number A007: Technical Information Report.

Bill Aiello  Dan Boneh
aiello@bellcore.com  dabo@cs.stanford.edu
Matthew Franklin  Jeremy Horwitz
franklin@research.att.com  horwitz@cs.stanford.edu

1 Executive Summary

The attached report contains a comprehensive survey of our results on distributed generation of shared RSA keys. These results are a central component of our Intrusion Tolerance project.

A private RSA key is often stored (encrypted) at a single location such as a user’s machine. The machine then becomes a prime target for a hacker who wishes to obtain the private key. To protect a highly sensitive private key (such as the one belonging to a root Certification Authority) one may wish to split the key into a number of pieces and store each piece at a separate location. Fortunately, for the RSA cryptosystem it is possible to share the private key among several sites without having to reconstruct the key in order to use it — a root CA can issue certificates without reconstructing its private key at a single location. To explain how this is done we briefly recall the details of the RSA system. Let N = pq be a product of two large prime. Let e be a public certificate verification exponent. Let d be a private certificate issuing exponent. We have that d · e = 1 mod ϕ(N) where ϕ(N) = N − p − q + 1. A public RSA key is made up of ⟨e, N⟩. A private key is made up of ⟨d, N⟩ (the private key often includes other information such as p and q for efficient signature generation). To share its private key among four sites, the root CA does the following: it picks four random integers d_{1}, …, d_{4} in the range 1, …, N such that d_{1} + d_{2} + d_{3} + d_{4} = d. Each of these shares is then stored (encrypted) in a separate location. To issue a certificate, the CA can create a signature on a message m by having each site compute s_{i} = m^{d_{i}} mod N. Each site then sends s_{i} to the entity requesting the certificate. The requesting entity can multiply the four s_{i}’s to obtain s = m^{d_{1}+d_{2}+d_{3}+d_{4}} = m^{d} mod N. Thus, a valid signature is obtained. The beauty of this simple procedure is that the private key d is never reconstructed at a single location. If a hacker penetrates even three of the four sites, he obtains no information about the private key. To achieve fault-tolerance the above scheme may be slightly modified so that any 3-out-of-4 sites can issue a certificate.

An important issue left out of the above discussion is key generation. Who generates the modulus N and the private key d? A simple solution is to ask a trusted dealer to generate two primes p and q, multiply them to get N and then generate e, d. Finally, the dealer splits d into four pieces and sends each piece to each of the sites. Unfortunately, a trusted dealer introduces a single point of attack: the dealer, or anyone who compromises the dealer, knows the private key and can issue false certificates. Our research on distributed generation of shared RSA keys eliminates the need for a trusted dealer. The four sites can jointly generate a shared key such that neither one of them known the private key d or the factorization of N. Our algorithms are useful also in other contexts, such as the Fiat-Shamir authentication scheme where a number of entities use a modulus N = pq for authentication, but none of them should know the factorization of N. The original Fiat-Shamir scheme called for a trusted dealer to generate N. Our research eliminates the need for a trusted dealer.

We briefly outline our approach. Our goal is to have k machines generate a modulus N = pq and exponents e and d. At the end of the computation all parties should be convinced that N is the product of two primes, however none of them should know the factorization. Furthermore, e should be public while d should be shared among the machines in a way that enables t-out-of-k threshold signature generation. That is, any t machines should be able to issue a certificate. At the same time, an attacker who penetrates at most t − 1 machines should not be able to obtain any information about the private key. Our key generation algorithm proceeds in a number of steps. At a high level these steps are as follows:

(1) pick candidates: Each of the k machines picks two random n-bit integers p_{i}, q_{i} and keeps them secret.

(2) compute N: Using a private distributed computation the k machines compute

N = (p_{1} + … + p_{k}) · (q_{1} + … + q_{k})

Other than the value of N, this step reveals no information about the secret values p_{1}, …, p_{k} and q_{1}, …, q_{k} (!) Now that N is public, the k machines apply trial division to ensure that N is not divisible by small primes.

(3) primality test: The k machines engage in a private distributed computation to test that N is the product of two primes. If the test fails, then the protocol is restarted from step 1. As before, this step reveals no information about the private shares.

(4) key generation: Given a public encryption exponent e, the machines use a private distributed computation to generate a shared secret decryption exponent d.

Part I of the attached report gives the full details of each of these steps. A number of practical optimizations that we used in the implementation of the algorithm are presented. A description of our implementation including timing measurements is given in [34]. Part II describes an extension of our algorithm enabling k machines to generate a modulus N which is the product of three large primes N = pqr. Generating an RSA modulus with three primes has some advantages over standard RSA and is occasionally used. The two parts are expanded versions of our papers that recently appeared in technical conferences.

Part I

Algorithms for Generating Shared RSA keys

Abstract We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus N = pq is publicly known. None of the parties know the factorization of N. In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication.

2 Introduction

We present efficient protocols for a number of parties to jointly generate an RSA modulus N = pq where p, q are prime. At the end of the computation the parties are convinced that N is indeed a product of two large primes. However, none of the parties know the factorization of N. We then show how the parties can proceed to compute a public exponent e and shares of the corresponding private exponent. Our techniques require a number of steps including a new distributed primality test. The test enables two (or more) parties to test that a random integer N is a product of two large primes without revealing the primes themselves.

Several cryptographic protocols require an RSA modulus N = pq for which none of the participants know the factorization. A good example is the original Fiat-Shamir authentication protocol [21] where all parties use the same modulus N, but none of them know its factorization. For other examples see [20, 25, 31, 35, 36]. Usually a modulus N with an unknown factorization is obtained by asking a dealer to generate it. The dealer must be trusted not to reveal the factorization of N. Our results eliminate the need for a trusted dealer since the parties can generate the modulus N themselves.

Threshold cryptography is a concrete example where shared generation of RSA keys is very useful. We give a brief motivating discussion and refer to [26] for a survey. Let N = pq be an RSA modulus and d, e be signing and verification exponents respectively, i.e. de = 1 mod ϕ(N). A threshold RSA signature scheme involves k parties and enables any subset of t of them to generate an RSA signature of a given message. No subset of t − 1 parties can generate a signature. Unlike standard secret sharing [41], the signature is generated without having to reconstruct the private decryption exponent d. A simple approach for obtaining a k-out-of-k threshold signature scheme is as follows [22]: pick random d_{i}’s satisfying d = ∑_{i=1}^{d} d_{i} mod ϕ(N) and give d_{i} to party i. Abstractly, to sign a message m each party computes s_{i} = m^{d_{i}} mod N and sends s_{i} to a combiner (that holds no secrets). The combiner multiplies the s_{i}’s and obtains the signature. This way the parties are able to generate a standard RSA signature without having to reconstruct the private key d at a single location. This is clearly advantageous for securing a sensitive private RSA key such as the one used by a Certificate Authority. Constructions providing a t-out-of-k RSA threshold signatures schemes can be found in [17, 14, 23, 40].

An important issue left out of the above discussion is the initial generation of the RSA modulus N and the shares d_{i}. Traditionally the modulus N and the shares of the private key are assumed to be generated by a trusted dealer. Clearly, the dealer, or anyone who compromises the dealer, can forge signatures. Our results eliminate the need for a trusted dealer since the k parties can generate N and the private shares themselves. Such results were previously known for the ElGamal public key system [37], but not for RSA.

The paper is organized as follows: we give a high level description of our protocol in Section 3. In Sections 3–5 we explain the various stages for generating a modulus N = pq with an unknown factorization. In Section 7 we describe protocols that given a public exponent e, generate shares of the corresponding private key d = e^{−1} mod φ(N). To achieve fault tolerance one often shares d using a t-out-of-k scheme. That is, any subset of t users can apply the private key d. We explain how a t-out-of-k sharing of d is obtained in Section 7.3. We discuss various practical improvements of our protocol in Section 8.

We note that generic secure circuit evaluation techniques, e.g. [45, 28, 3, 10] can also be used to generate shared RSA keys. After all, a primality test can be represented as a boolean circuit. However, such general techniques are too inefficient.

2.1 Communication and privacy model

The communication and privacy model assumed by our protocol are as follows:

Full connectivity Any party can communicate with any other party. This is a typical setup on a local network or the Internet.

Private and authenticated channels Messages sent from party A to party B are private and cannot be tampered with en route. This can be achieved by having A and B share a secret key which they use for encryption, integrity and authentication.

Honest parties We assume all parties are honestly following the protocol. At the end of the protocol no threshold of parties have enough information to factor the generated modulus. This model is often called honest but curious parties. In Section 9 we discuss some results showing how this assumption can be relaxed. Recently, Frankel, MacKenzie and Yung [24] showed how our protocol can be made robust against ⌊\frac{k−1}{2}⌋ malicious parties.

Collusion Our protocol is ⌊\frac{k}{2}⌋ private. That is, any coalition of size at most ⌊\frac{k}{2}⌋ learns no information about the factorization of N = pq. However, a coalition of more than ⌊\frac{k}{2}⌋ can recover the factorization. The reason for this bound is our reliance on the BGW [3] protocol in one step of our algorithm. The BGW protocol provides information theoretic security and hence limited to achieving ⌊\frac{k}{2}⌋ privacy (in the honest parties model). We note that it is possible to achieve k−1 privacy by replacing the BGW step with a heuristic protocol due to Cocks [11]. Unfortunately, Cocks’ protocol is by far slower than the BGW method. Furthermore, its security is based on a heuristic argument.

To prove the security properties (i.e. privacy) satisfied by our protocol we provide a simulation argument for each of its components.

3 Overview

In this section we give a high level overview of the protocol. The k parties wish to generate a shared RSA key. That is, they wish to generate an RSA modulus N = pq and a public/private pair of exponents e, d where e · d = 1 mod φ(N). The factors p and q should be at least n bits each. At the end of the computation N and e are public, and d is shared between the k parties in a way that enables threshold decryption. All parties should be convinced that N is indeed a product of two primes, but no coalition of at most t = ⌊\frac{k−1}{2}⌋ parties should have any information about the factors of N. At a high level the protocol works as follows:

(1) pick candidates: The following two steps are repeated twice.

(a) secret choice: Each party i picks a secret n-bit integer p_{i} and keeps it secret.

(b) trial division: Using a private distributed computation the k parties determine that p = p_{1} + … + p_{k} is not divisible by any prime less than some bound B_{1}. Details are given in Section 6. If this step fails repeat step (a).

Denote the secret values picked at the first iteration by p_{1}, …, p_{k}, and at the second iteration by q_{1}, …, q_{k}.

(2) compute N: Using a private distributed computation the k parties compute

N = (p_{1} + … + p_{k}) · (q_{1} + … + q_{k})

Other than the value of N, this step reveals no further information about the secret values p_{1}, …, p_{k} and q_{1}, …, q_{k}. Details are given in Section 5.

Now that N is public, the k parties can perform further trial divisions and test that N is not divisible by small primes in the range [B_{1}, B_{2}] for some bound B_{2}.

(3) primality test: The k parties engage in a private distributed computation to test that N is indeed the product of two primes. If the test fails, then the protocol is restarted from step 1. We note that the primality test protocol is k − 1 private and applies whenever two (or more) parties are involved. Details are in section 4.

(4) key generation: Given a public encryption exponent e, the parties engage in a private distributed computation to generate a shared secret decryption exponent d. Details are in Section 7.

Notation Throughout the paper we adhere to the following notation: the RSA modulus is denoted by N and is a product of two n bit primes p, q. When p = ∑ p_{i} we denote by p_{i} the share in possession of party i. Similarly for q_{i}. When the p_{i}’s themselves are shared among the parties we denote by p_{i,j} the share of p_{i} that is sent to party j.

Performance issues Our protocol generates two random numbers and tests that N = pq is a product of two primes. By the prime number theorem the probability that both p and q are prime is asymptotically 1/n^{2}. Therefore, naively one has to perform n^{2} probes on average until a suitable N is found. This is somewhat worse than the expected 2n probes needed in traditional generation of an RSA modulus (one first generates one prime using n probes and then a second prime using another n probes). This n/2 degradation in performance is usually unacceptable (typically n = 512).

Fortunately, thanks to trial division things aren’t so bad. Our trial division (Step 1b) tests each prime individually. Therefore, to analyze our protocol we must analyze the effectiveness of trial division. Suppose a random n-bit number p passes the trial division test where all primes less than B are tested. We take B = c · n for some constant c. How likely is p to be prime? Using a classic result due to Mertens, DeBruijn [13] shows that asymptotically

Pr[p prime | trial division up to B] = e^{γ} \frac{ln B}{ln 2^{n}} (1 + o(1/n)) = 2.57\frac{ln B}{n} (1 + o(1/n))

Hence, when n = 512 bits and ln B = 9 (i.e. B = 8103) the probability that p is prime is approximately 1/22. Consequently, traditional RSA modulus generation requires 44 probes while our protocol requires 484 probes. This eleven fold degradation in performance is unfortunate, but manageable. We discuss methods to avoid this slowdown in Section 8.

Generation of shares In step (1) of the protocol each party uniformly picked a random n bit integer p_{i} as its secret share. The prime p was taken to be the sum of these shares. Since the sum of uniform independent random variables is not uniformly distributed, p is picked from a distribution with slightly less entropy than uniform. We show that this is not a problem. The sum p = ∑_{i} p_{i} is at most an n + log k bit number. One can easily show that p is chosen from a distribution with at least n bits of entropy (since the n least significant bits of p are a uniformly chosen n bit string). These log k bits of “lost” entropy can not help an adversary, since they can be easily guessed (the number of parties k is small, certainly k < n). This is formally stated in the next lemma.

A second issue is the fact that the shares p_{i} themselves leak some information about the factors of N. For instance, party i knows that p > p_{i}. We argue that this information does not help an adversary either.

The two issues raised above are dealt with in the following lemma. Let ℤ_{n}^{(2)} be the set of RSA moduli N = pq that can be output by our protocol above when k parties are involved. We assume k < log N.

Lemma 3.1 Suppose there exists a polynomial time algorithm A that given a random N ∈ ℤ_{n}^{(2)} chosen from the distribution above and the shares {p_{i}} of k − 1 parties, factors N with probability at least 1/n^{d}. Then there exists an expected polynomial time algorithm B that factors 1/n^{d+2} of the integers in ℤ_{n}^{(2)}.

Proof Sketch Given N ∈ ℤ_{n}^{(2)} algorithm B works by repeating the following two steps until N is factored: (1) pick random independent n bit integers p_{1}, …, p_{k−1}. (2) Run algorithm A on the input N and p_{1}, …, p_{k−1}. For 1/n^{d+2} of the integers in ℤ_{n}^{(2)}, after a polynomial number of iterations algorithm B will output a factorization of N. □

4 Distributed primality test

We begin the detailed discussion of the protocol with the distributed primality test (step 3). Party i has two secret n-bit integers p_{i}, q_{i}. All parties know N where N = pq = (∑ p_{i})(∑ q_{i}). They wish to determine if N is the product of two primes without revealing any information about the factors of N. We refer to this test as a distributed primality test. Our primality test is a probabilistic test [42, 39] carried out in both ℤ_{N}^{∗} and a quadratic extension of ℤ_{N}^{∗}.

Throughout the section we are assuming that p = q = 3 mod 4 (hence the resulting N = pq is a Blum integer). This can be arranged ahead of time by having party 1 pick shares p_{1} = q_{1} = 3 mod 4. All other parties pick shares p_{i} = q_{i} = 0 mod 4.

Before describing the test we briefly discuss the structure of the quadratic extension of ℤ_{N}^{∗} we will be using. We will be working in the twisted group 𝕋_{N} = (ℤ_{N}[x]/(x^{2} + 1))^{∗}/ℤ_{N}^{∗}. Suppose all prime factors of N are 3 mod 4. In this case, x^{2} + 1 is irreducible in ℤ_{N}[x] and ℤ_{N}[x]/(x^{2} + 1) is a quadratic extension of ℤ_{N}. A linear polynomial f(x) = αx + β in ℤ_{N}[x]/(x^{2} + 1) is invertible if and only if gcd(α, β, N) = 1. It follows that elements of 𝕋_{N} can be viewed as linear polynomials f(x) = αx + β ∈ ℤ_{N}[x] with gcd(α, β, N) = 1. Two linear polynomials f, g ∈ ℤ_{N}[x] represent the same element of 𝕋_{N} if f = ag for some a ∈ ℤ_{N}^{∗}. We note that elements of 𝕋_{N} can also be viewed as points on the projective line over ℤ_{N}.

Distributed primality test:

Step 1: The parties agree on a random g ∈ ℤ_{N}^{∗}. The value g is known to all k parties.

Step 2: Party 1 computes the Jacobi symbol of g over N. If (\frac{g}{N} ) ≠ 1 the protocol is restarted at step (1) and a new random g is chosen.

Step 3: Otherwise, party 1 computes v_{1} = g^{(N−p_{1}−q_{1}+1)/4} mod N. All other parties compute v_{i} = g^{(p_{i}+q_{i})/4} mod N. The parties exchange the v_{i} values with each other and verify that

v_{1} = ± ∏_{i=2}^{k} v_{i} (mod N)

If the test fails then the parties declare that N is not a product of two primes.

Step 4: The parties perform a Fermat test in the twisted group 𝕋_{N} = (ℤ_{N}[x]/(x^{2} + 1))^{∗}/ℤ_{N}^{∗}. To carry out the Fermat test in 𝕋_{N} the parties pick a random h ∈ 𝕋_{N}. Party 1 computes u_{1} = h^{N+p_{1}+q_{1}+1}. All other parties compute u_{i} = h^{p_{i}+q_{i}}. The parties then exchange the u_{i} values with each other and verify that

∏_{i=1}^{k} u_{i} = h^{N+p+q+1} = 1

If the test fails N is rejected. Otherwise they declare success.

Since p_{1} = q_{1} = 3 mod 4 and p_{i} = q_{i} = 0 mod 4 for i > 1, the exponents in the computation of the v_{i}’s (Step 3) are guaranteed to be integers after division by 4. The correctness and privacy of the protocol is proved in the next two lemmas. Lemma 4.1 Let N = pq be an integer with p ≡ q ≡ 3 mod 4. If N is a product of two distinct primes then success is declared in all invocations of the protocol. Otherwise, the parties declare that N is not a product of two primes with probability at least \frac{1}{2} (over the random choice of g and h). Proof Observe that in step (3) of the protocol we test that v_{1}/ ∏ v_{i} = ±1 mod N which amounts to testing g^{(N−p−q+1)/4} ≡ ±1 mod N.

Suppose p and q are distinct primes. In step (2) we verify that (\frac{g}{N} ) = 1. This implies (\frac{g}{p}) =

(\frac{g}{q} ). Also, since \frac{q−1}{2} and \frac{p−1}{2} are odd we have,

\{ \begin{matrix}g^{ϕ(N)/4} = (g^{\frac{p−1}{2}} )^{\frac{q−1}{2}} ≡ (\frac{g}{p})^{\frac{q−1}{2}} = (\frac{g}{p}) (mod p) \\ g^{ϕ(N)/4} = (g^{\frac{q−1}{2}} )^{\frac{p−1}{2}} ≡ (\frac{g}{q} )^{\frac{p−1}{2}} = (\frac{g}{q} ) (mod q) \end{matrix}

Since (\frac{g}{p}) = (\frac{g}{q} ) it follows that g^{ϕ(N)/4} ≡ ±1 mod N. Since ϕ(N) = N − p − q + 1 when p and q are prime, it follows that the test in Step 3 always succeeds.

Similarly, we show that when p and q are distinct primes the test in Step 4 succeeds. Since p ≡ q ≡ 3 mod 4 the polynomial x^{2} + 1 has no root in 𝔽_{p} and 𝔽_{q}. Therefore, 𝔽_{p}[x]/(x^{2} + 1) and 𝔽_{q}[x]/(x^{2} + 1) are quadratic extensions of 𝔽_{p} and 𝔽_{q} respectively. It follows that the group 𝕋_{p} = (ℤ_{p}[x]/(x^{2} + 1))^{∗}/ℤ_{p}^{∗} is of order p + 1. Similarly, |𝕋_{q}| = q + 1. By the Chinese Remainder Theorem, 𝕋_{N} = 𝕋_{p} × 𝕋_{q} and hence |𝕋_{N}| = (p + 1)(q + 1). We conclude that all h ∈ 𝕋_{N} satisfy h^{(p+1)(q+1)} = 1. Consequently, the test of Step 4 always succeeds.

To prove the converse, suppose at least one of p, q is not prime. That is, N = r_{1}^{d_{1}} ⋯ r_{s}^{d_{s}} is a non-trivial factorization of N with ∑ d_{i} ≥ 3 and s ≥ 1. Set e = (N −p−q +1)/4 = (p−1)(q −1)/4 to be the exponent used in step (3). Note that e is odd since p ≡ q ≡ 3 mod 4. Define the following two subgroups of ℤ_{N}^{∗}:

G = \{g ∈ ℤ_{N} s.t. (\frac{g}{n}) = 1\} and H = \{g ∈ G s.t. g^{e} = ±1 mod N\}

To prove the lemma we show that |H| ≤ \frac{1}{2}|G|. Since H is a subgroup of G it suffices to prove proper containment of H in G, i.e. prove the existence of g ∈ G \ H. There are four cases to consider.

Case 1. Suppose s ≥ 3. Let r_{2}, r_{3} be distinct prime factors of N such that d_{2} = d_{3} mod 2 (such a pair must exist by pigeon hole). Let r_{1} be a prime factor of N distinct from both r_{2} and r_{3} and let a be a quadratic non-residue modulo r_{3}. Define g ∈ ℤ_{N} to be an element satisfying

g ≡ 1 mod r_{1} and g ≡ −1 mod r_{2} and g ≡ \{ \begin{matrix}1 mod r_{3} & if & (\frac{−1}{r_{2}}) = 1 \\ a mod r_{3} & if & (\frac{−1}{r_{2}}) = −1 \end{matrix}

and g ≡ 1 mod r_{i} for i > 3. Observe that g ∈ G. Since e is odd g^{e} = g = 1 mod r_{1} and

g^{e} = g = −1 mod r_{2}. Consequently, g^{e} ≠ ±1 mod N i.e. g ∉ H.

Case 2. Suppose gcd(p, q) > 1. Then there exists an odd prime r such that r divides both p and q. Then r^{2} divides N implying that r divides ϕ(N). It follows that in ℤ_{N}^{∗} there exists an element g of order r. Since r is odd we have (\frac{g}{N} ) = (\frac{g^{r}}{N} ) = (\frac{1}{N} ) = 1, i.e. g ∈ G. Since r divides both p and q we know that r does not divide N − p − q + 1 = 4e. Consequently g^{4e} ≠ 1 mod N implying that g^{e} ≠ ±1 mod N. Hence, g ∉ H.

Case 3. The only way N = pq does not fall into both cases above is if p = r_{1}^{d_{1}} and q = r_{2}^{d_{2}} where r_{1}, r_{2} are distinct primes and at least one of d_{1}, d_{2} is bigger than 1 (case 2 handles N that are a prime power N = r^{d}). By symmetry we may assume d_{1} > 1. Since ℤ_{p}^{∗} is a cyclic group of order r_{1}^{d_{1}−1}(r_{1} − 1) it contains an element of order r_{1}^{d_{1}−1}. It follows that ℤ_{N}^{∗} also contains an element g of order r_{1}^{d_{1}−1}. As before, (\frac{g}{N} ) = 1, i.e. g ∈ G. If q ≠ 1 mod r_{1}^{d_{1}−1} then 4e = N − p − q + 1 is not divisible by r_{1}^{d_{1}−1}. Consequently, g^{4e} ≠ 1 mod N, i.e. g ∉ H.

Case 4. We are left with the case N = pq with p = r_{1}^{d_{1}}, q = r_{2}^{d_{2}}, d_{1} > 1 as above and q ≡ 1 mod r_{1}^{d_{1}−1}. Since p = q = 3 mod 4 we know that r_{1} = r_{2} = 3 mod 4. In this case it may indeed happen that H = G. We show that in this case, Step (4) of the primality test will fail with probability at least half (over the choice of h ∈ 𝕋_{N}).

Define the group H′ = \{h ∈ 𝕋_{N} s.t. h^{(p+1)(q+1)} = 1\}. We show that |H′| ≤ \frac{1}{2}|𝕋_{N}|. Since H′ is a subgroup of 𝕋_{N} it suffices to prove proper containment, i.e. we must exhibit an element w ∈ 𝕋_{N} \ H′. Since p = r_{1}^{d_{1}} the group 𝕋_{p} has order r_{1}^{d_{1}−1}(r_{1} + 1). Therefore it contains an element h of order r_{1}. It follows that there exists an element w ∈ 𝕋_{N} of order r_{1}. Since by assumption q ≡ 1 mod r_{1} we know that r_{1} does not divide q + 1. Hence r_{1} does not divide N +p+q +1 and therefore w^{N+p+q+1} = w^{(p+1)(q+1)} ≠ 1. This proves w ∈ 𝕋_{N} \H′ completing the proof of the lemma. □

We note that Step (4) of the protocol is needed to filter out integers that fall into Case 4 above. Indeed, such integers will pass steps (1)-(3). For example, consider integers N = pq with p = 3^{s} and q = 2 · 3^{s−1} + 1 with s odd and q prime. For these integers we have H = G where H, G are as defined in the body of the proof above. Consequently, such integers always pass steps (1)-(3) even though they are not a product of two distinct primes. However, they will fail step (4). In Section 4.1 we give an alternate approach for filtering out integers that fall into Case 4.

The following lemma shows that when N is the product of two distinct primes, the primality test protocol reveals no other information about the private shares of the participants. Lemma 4.2 Suppose p, q are prime. Then any coalition of k − 1 parties can simulate their view of the primality testing protocol. Consequently, the protocol is k − 1 private. Proof Since p, q are prime we know that v_{1} = ± ∏_{i=2}^{k} v_{i} mod N where v_{a}, v_{b} are defined as in step (3) of the protocol. Also, ∏ u_{i} = 1 where the u_{i}’s are defined in step (4). Let U be a coalition of k − 1 parties. Say party m is not a member of the coalition. The coalition’s view consists of ⟨u_{i}, v_{i}, N, g, h⟩ for i = 1, …, k and ⟨p_{i}, q_{i}⟩ for all i ≠ m.

We construct a simulator of the coalition’s view as follows: the simulator is given N, p_{i}, q_{i} for i ≠ m as input (this is the coalition’s input when the protocol is started). To simulate the coalition’s view, the simulator first picks a random g ∈ ℤ_{N}^{∗} with (\frac{g}{N} ) = 1 and a random h ∈ 𝕋_{N}. It then computes the u_{i}, v_{i} values for all i ≠ m using the p_{i}, q_{i} values it is given as input. Next the simulator must generate u_{m}, v_{m}. Generating u_{m} is trivial since u_{m} = (∏_{i≠m} u_{i})^{−1}. Generating v_{m} is a bit harder. From the proof of Lemma 4.1 it follows that

v_{1} = ∏_{i=2}^{k} v_{i} (mod N) implies (\frac{g}{p}) = (\frac{g}{q} ) = 1
v_{1} = − ∏_{i=2}^{k} v_{i} (mod N) implies (\frac{g}{p}) = (\frac{g}{q} ) = −1

That is, the sign of v_{1}/ ∏_{i=2}^{k} v_{i} leaks whether g is a quadratic residue modulo N. To simulate v_{m} the simulator computes v̂_{m} = v_{1}/ ∏_{i≠m} v_{i}. It then flips an unbiased coin and sets v_{m} = v̂_{m} or v_{m} = −v̂_{m} accordingly. The resulting distribution on v_{m} is computationally indistinguishable from the true distribution, assuming the hardness of quadratic residuosity modulo a Blum integer. To conclude, given that N is the product of two distinct primes, the set of values ⟨u_{i}, v_{i}, N, g, h⟩ produced by the simulator is computationally indistinguishable from a real transcript. Consequently, the coalition learns no information other than what it had at the beginning of the protocol. □

We note that step (2) of the protocol is crucial. Without it the condition of step (3) might fail (and reveal the factorization) even when p and q are prime. We also note that in practice the probability that a non RSA modulus passes even one iteration of this test is actually far less than a half.

4.1 An alternative to Step (4)

Step (4) of the distributed primality protocol is necessary to filter out integers that fall into Case 4 in the proof of Lemma 4.1. We describe an alternative simpler approach to filter out such integers. It’s advantage is that it requires less computation. It’s drawback is more communication between the parties.

Observe that N that fall into Case 4 satisfy gcd(N, p + q − 1) > 1. The alternative to Step (4) is to directly test this condition. To test this condition with no information leakage the parties do the following: each party picks a random r_{i} ∈ ℤ_{N} and keeps it secret. Using the protocol of the next section they compute

z = (∑_{i=1}^{k} r_{i}) (−1 + ∑_{i=1}^{k}(p_{i} + q_{i})) (mod N)

without leaking any information about the private shares p_{i}, q_{i} or r_{i}. Finally, the parties check if gcd(z, N) > 1. If so, N is rejected. Using the BGW method (Section 5.1) this approach is ⌊\frac{k−1}{2}⌋ private. All N that fall into case 4 are rejected. All that are a product of two distinct primes pass the test with overwhelming probability. We note that this alternate test requires far more communication than the proposed Step (4) in the previous section. In addition, it eliminates a few valid RSA moduli, i.e. moduli N = pq with p, q prime and q = 1 mod p.

5 Distributed computation of N

Next we describe the computation of N. Each party has a secret p_{i}, q_{i}. They wish to make the product N = (∑ p_{i})(∑ q_{i}) public without revealing any information about their private shares beyond what is revealed by the knowledge of N.

5.1 The BGW method

BenOr, Goldwasser and Wigderson [3] describe an elegant protocol for private evaluation of general functions for three or more parties. Their full technique is an overkill for the simple function we have in mind. We adapt their protocol to the computation at hand so as to minimize the amount of computation and communication between the parties. From here on, let P > N be some prime. Unless otherwise stated, all arithmetic operations are done modulo P. The protocol works as follows:

Step 1: Let l = ⌊\frac{k−1}{2}⌋. For all i = 1, …, k party i picks two random degree l polynomials f_{i}, g_{i} ∈ ℤ_{P} [x] satisfying f_{i}(0) = p_{i} and g_{i}(0) = q_{i}. In other words, the constant term of f_{i}, g_{i} are set to p_{i}, q_{i} and all other coefficients are chosen at random in ℤ_{P}. Similarly, party i picks a random degree 2l polynomial h_{i} ∈ ℤ_{p}[x] satisfying h_{i}(0) = 0.

Step 2: For all i = 1, …, k party i computes the 3k values:

∀j = 1, …, k : p_{i,j} = f_{i}(j) ; q_{i,j} = g_{i}(j) ; h_{i,j} = h_{i}(j)

Party i then privately sends the triple ⟨p_{i,j}, q_{i,j}, h_{i,j}⟩ to party j for all j ≠ i. Note that the p_{i,j} for j = 1, …, k are standard l-out-of-k Shamir secret sharings of p_{i}. The same holds for q_{i}.

Step 3: At this point, each party i has all of ⟨p_{j,i}, q_{j,i}, h_{j,i}⟩ for j = 1, …, k. Party i computes:

N_{i} = (∑_{j=1}^{k} p_{j,i}) · (∑_{j=1}^{k} q_{j,i}) + ∑_{j=1}^{k} h_{j,i} (mod P)

Party i broadcasts N_{i} to all other parties.

Step 4: At this point each of the parties has all values N_{i} for i = 1, …, k. Let α(x) be the polynomial

α(x) = (∑_{j} f_{j}(x)) (∑_{j} g_{j}(x)) + ∑_{j} h_{j}(x) (mod P)

Observe that α(i) = N_{i} and by definition of f_{i}, g_{i}, h_{i} we have α(0) = N. Furthermore, α(x) is a polynomial of degree 2l. We note that l is defined so that k ≥ 2l+1. Consequently, since all parties have at least 2l + 1 points on α(x) they can interpolate it and discover its coefficients. Finally, each party evaluates α(0) and obtains N mod P. Since N < P the parties learn the correct value of N.

From the description of the protocol it is clear that all parties learn the value N. We note that the protocol requires that at least three parties be involved. In the case of exactly three parties, linear polynomials are used and the protocol is 1-private.

The following lemma shows that no coalition of ⌊\frac{k−1}{2}⌋ parties learns any further information about the private shares. This statement holds in the information theoretic sense – no complexity assumptions are needed. For completeness we sketch the proof of the lemma and refer to [3] for the complete details. Lemma 5.1 Given N, any coalition of ⌊\frac{k−1}{2}⌋ parties can simulate the transcript of the protocol. Consequently, the protocol is ⌊\frac{k−1}{2}⌋ private.

Proof Sketch Set l = ⌊\frac{k−1}{2}⌋. By symmetry we may assume the coalition is made up of parties 1 … l. In what follows we consistently let the index i vary in i = 1, …, l, the index j vary in j = 1, …, k and the index r vary in r = l + 1, …, k. Then the coalition’s view consists of ⟨p_{i}, q_{i}, f_{i}, g_{i}, p_{i,j}, q_{i,j}, h_{i,j}, p_{r,i}, q_{r,i}, h_{r,i}, N_{j}, N⟩.

To simulate the coalition’s view, the simulator is given p_{i}, q_{i}, N as input. It first picks random f_{i}, g_{i}, h_{i} ∈ ℤ_{P} [x] with f_{i}(0) = p_{i}, g_{i}(0) = q_{i} and h_{i}(0) = 0. Next, it computes p_{i,j} = f_{i}(j), q_{i,j} = g_{i}(j) and h_{i,j} = h_{i}(j). It picks p_{r,i}, q_{r,i}, h_{r,i} as random independent elements of ℤ_{P} and computes N_{i} = (∑_{j} p_{i,j})(∑_{j} q_{i,j}) + ∑_{j} h_{i,j}. Next, it picks a random degree 2l polynomial α(x) ∈ ℤ_{P} [x] satisfying α(i) = N_{i} and α(0) = N. It completes the simulation by setting N_{r} = α(r). These values are a perfect simulation of the coalition’s view. □

The above protocol consists of one phase of the full BGW method. It differs from the BGW protocol in that there is no need for a truncation step. Also, we combine the addition and multiplication stages into one phase. The resulting computation is surprisingly efficient. Essentially, there is only one multi-precision multiplication performed by each party (the one in Step 3). We note that communication between the parties can be reduced by a factor of two using a variant of the protocol as described in [7, Section 4].

5.2 BGW Modulo non primes

In our description of the BGW protocol all arithmetic operations were carried out modulo a prime P > N. In the coming sections it will be useful to run the BGW protocol while working modulo a non prime P. That is, the k parties wish to compute N = (∑ p_{i})(∑ q_{i}) mod M for some integer M, not necessarily prime. One can easily show that if M has no prime divisors smaller than k then the protocol can be used as is. Indeed, all Lagrange coefficients used during the interpolation at Step (4) exist. Lemma 5.1 remains correct.

Running the protocol modulo M containing small factors require a slight modification. Write M = M_{1} · M_{2} where M_{1} has no prime factors smaller than k and M_{2} has only prime factors smaller than k. As mentioned above the protocol immediately works modulo M_{1}. The problem when working modulo M_{2} is that Shamir secret sharing (which is the basis of BGW) is not possible. For instance, consider the case when M_{2} = 3. It is not possible to use Shamir secret sharing in 𝔽_{3} among k > 3 parties since 𝔽_{3} does not contain enough points (in Shamir secret sharing each party must be given its own unique point). A simple solution is to run the entire protocol in an algebraic extension of 𝔽_{3} that contains more than k points. The simulation argument immediately extends to this case. In general, one can factor M_{2} into it’s prime factors and run the protocol in a large enough extension for each factor. Using the Chinese Remainder Theorem one can recover the value of N mod M.

5.3 Sharing the final outcome

In some cases (as in Section 7.2) we wish to have the parties evaluate the function N = (∑ p_{i})(∑ q_{i}); however the result should be additively shared among the parties rather than become publicly available. That is, at the end of the computation each party should have an M_{i} such that

∑_{i=1}^{k} M_{i} = (∑_{i=1}^{k} p_{i})(∑_{i=1}^{k} q_{i}) (mod P)

and no information is revealed about the private shares or the final result.

The modification to BGW in order to achieve the above goal is immediate. The parties do not perform Step 4 of the protocol and do not perform the broadcast described at the end of Step 3. Consequently, they each end up with a point on a polynomial α(x) of degree 2l that evaluates to N at x = 0. Using Lagrange interpolation we know that

N = α(0) = ∑_{i=1}^{k} λ_{i}(0)N_{i} (mod P)

where λ_{i}(x) = ∏_{j≠i} \frac{(x−j)}{(i−j)} is the appropriate Lagrange coefficient. Therefore, rather than broadcast N_{i} at the end of Step 3, party i simply sets M_{i} = λ(0)N_{i}. The resulting M_{i}’s are an additive sharing of N as required. As before, there is a simple simulation argument showing that any minority of parties obtains no information from this protocol.

6 Trial division

In this section, we consider the trial division step (Step 1b in Section 3). Let q = q_{1} + … + q_{k} be an integer shared among k parties. Let p be a small prime. To test if p divides q each party picks a random r_{i} ∈ ℤ_{p}. Using the BGW protocol (as described in Section 5.1) they compute qr = (∑ q_{i})(∑ r_{i}) mod p. If qr ≠ 0 then p does not divide q. Furthermore, since r is unknown to any minority of parties, qr provides no other information about q.

Note that in the above approach, a bad candidate q is always rejected. Unfortunately, a good candidate might also be rejected. Indeed, even if p does not divide q it is still possible that qr = 0 mod p. To alleviate this problem one can repeat the above test twice for each small prime

p. Then the probability that a good candidate is rejected is at most 1 − ∏_{p<B}(1 − \frac{1}{p^{2}} ) < \frac{1}{2}.

One caveat in the above approach is that the BGW protocol as described in Section 5.1 cannot be applied to test divisability of q by very small p, namely p ≤ k. The reason is that for such small p the field 𝔽_{p} does not contain enough points to do Shamir secret sharing among k parties. For such small p one must run the BGW protocol in an extension field of 𝔽_{p} that contains at least k + 1 elements, as explained in Section 5.2.

7 Shared generation of public/private keys

Once the parties successfully construct an RSA modulus N = pq = (∑ p_{i})(∑ q_{i}) they may wish to compute shares of d = e^{−1} mod ϕ(N) for a given encryption exponent e. We have two approaches for computing shares of d. The first only works for small e (say e < 1000) but is very efficient requiring very little communication between the parties. The second works for any e and is still efficient, but requires more communication.

Throughout the section we set ϕ = ϕ(N). Recall that the public modulus N = (∑ p_{i})(∑ q_{i})

satisfies ϕ(N) = ϕ = ∑_{i=1}^{k} ϕ_{i} where ϕ_{1} = N − p_{1} − q_{1} + 1 and ϕ_{i} = −p_{i} − q_{i} for i = 2, …, k. For all

i = 1, …, k party i can locally compute ϕ_{i}.

To compute shares of d the parties must invert e modulo ∑ ϕ_{i} without exposing their ϕ_{i}’s. Unfortunately, traditional inversion algorithms, e.g. extended gcd, involve computations modulo ∑ ϕ_{i}. We do not know how to efficiently perform modular arithmetic when the modulus is shared among the participants. Fortunately, there is a trick for computing e^{−1} mod ϕ with no modulo ϕ reductions. When only a single user is involved the inversion is done in three steps: (1) Compute ζ = ϕ^{−1} mod e. (2) Set T = −ζ · ϕ + 1. Observe that T ≡ 0 mod e. (3) Set d = T/e. Indeed d = e^{−1} mod ϕ since d · e ≡ 1 mod ϕ. There is no need for modulo ϕ reductions since e^{−1} mod ϕ can be immediately deduced from ϕ^{−1} mod e. Both methods rely on this observation.

7.1 Small public exponent

We begin by describing an efficient technique for generating shares of d when the public exponent e is small. The method leaks the value of ϕ(N) mod e (hence it can only be applied when e is small). On the plus side, it is k − 1 private.

Step 1: The parties jointly determine the value of l = ϕ mod e. Since l = ∑ ϕ_{i} mod e it is possible to compute l without revealing any other information about the private shares. To do so we use a protocol due to Benaloh [4] which is k − 1 private.

Step 2: Let ζ = l^{−1} mod e. Then, as explained above, d = (−ζ · ϕ + 1)/e. Each party i locally computes:

d_{i} = ⌊\frac{−ζ · ϕ_{i}}{e} ⌋

As a result we have d = ∑ d_{i} + r mod ϕ(N) where 0 ≤ r < k.

Step 3: The above sharing of d enables shared decryption [22] using the equality c^{d} ≡ c^{r} ∏ c^{d_{i}} mod N. Party 1 can determine the value of r by trying all possible values of 0 ≤ r ≤ k during a trial decryption.

The above approach leaks ϕ(N) mod e and r. This is a total of log e + log k bits.

7.2 Arbitrary public exponent

Unlike the previous technique, our second method for generating shares of d works for arbitrary public exponent e. It leaks less than 2 log k bits. This information cannot help an opponent since it can be easily guessed. Rather than exposing ϕ mod e and then inverting it (as we did above) we show how to invert ϕ mod e while it is shared among the parties. As a result, no information about ϕ is revealed. The protocol is \frac{k−1}{2} private.

Step 1. Each party picks a random r_{i} ∈ ℤ_{e}.

Step 2. Using the protocol of Section 5.2 they compute ψ = (∑ r_{i}) · (∑ ϕ_{i}) mod e. At the end of the computation ψ is known to all parties. If ψ is not invertible modulo e the protocol is restarted at Step 1.

Step 3. Each party locally computes ζ_{i} = r_{i}ψ^{−1} mod e. Observe ∑ ζ_{i} = (∑ r_{i})ψ^{−1} = ϕ^{−1} mod e. Hence, the parties are able to share the inverse of ϕ mod e without revealing any information.

Step 4. Next, the parties agree on a prime P > 2Ne. They view the shares 0 ≤ ζ_{i} < e as elements of ℤ_{P}. Using the modified BGW protocol of Section 5.3 they compute an additive sharing

∑_{i=1}^{k} T_{i} = −(∑ ζ_{i})(∑ ϕ_{i}) + 1 (mod P)

Each party has a T_{i} and any minority of parties learns no other information.

Step 5. From here on we regard the T_{i}’s as integers 0 ≤ T_{i} < P. Our objective is to ensure that over the integers

∑_{i=1}^{k} T_{i} = −(∑_{i=1}^{k} ζ_{i})(∑_{i=1}^{k} ϕ_{i}) + 1  (1)

We now that at the end of Step 4 we have ∑ T_{i} < kP. Therefore, ∑ T_{i} = sP + u where s < k and 0 ≤ u < P. Given a candidate value of s ∈ [0, k) party 1 can set d_{1} ← d_{1} − sP. If the given s is correct then 0 ≤ ∑ T_{i} < P and the above equality holds over the integers. To determine the correct s the protocol proceeds to Step 6 with each possible value of s until the trial decryption in Step 6 succeeds.

Step 6. Assuming equality (1) holds over the integers we know that e divides ∑ T_{i}. To see this observe that:

∑ T_{i} = −(∑ ζ_{i})(∑ ϕ_{i}) + 1 = −(∑ ϕ_{i})^{−1}(∑ ϕ_{i}) + 1 ≡ 0 (mod e)

Therefore, d = (∑ T_{i})/e. Each party i now sets d_{i} = ⌊T_{i}/e⌋. As a result we have d = ∑ d_{i} + r mod ϕ(N) where 0 ≤ r ≤ k. Party 1 can determine the value of r by trying all possible values of 0 ≤ r ≤ k during a trial decryption.

The protocol leaks the value of r and s. Hence, a total of at most 2 log k bits is exposed. The value of r is found using only one trial decryption: a gateway first picks a random message m ∈ ℤ_{N} and computes c = m^{e} mod N. It then asks the parties to decrypt c. Each party computes m_{i} = c^{d_{i}} mod N and sends the result to the gateway. By performing at most k multiplications the gateway finds an r ∈ [0, k) satisfying m = (∏ m_{i})c^{r} mod N. It then relates the value of r back to the parties who fix their shares of d accordingly. To determine s this procedure is repeated for each of the k candidate values of s. Recall that k is typically small (e.g. less than 10). Note 7.1: Observe that Step 5 of the above protocol is needed due to the fact that the BGW method is carried out modulo P. However, it is possible to carry out the BGW protocol of Step 4 directly over the integers, avoiding Step 5 altogether. This can be done using a variant of Shamir secret sharing over the integers (see [23, 24]). Let L = k!. Then, each party i picks two polynomials f_{i}, g_{i} ∈ ℤ[x] of degree ⌊\frac{k−1}{2}⌋ as follows: the constant terms are set to f_{0} = f(0) = Lζ_{i} and g_{0} = g(0) = Lϕ_{i}. All other coefficients are chosen at random from {0, L, 2L, …, L^{3}N^{2}}. By interacting with the other parties, each party i computes a point on the polynomial (∑ f_{i})(∑ g_{i}) over the integers. These points, multiplied by the appropriate Lagrange coefficients, become the additive sharing ∑ T_{i} of (∑ ζ_{i})(∑ ϕ_{i}) over the integers. Unfortunately, in this approach, the resulting shares d_{i} of the private key are of order N^{2} rather than N as in the above protocol. This results in a factor of two slowdown during threshold signature generation. On the positive side, there is no need to leak the value of s.

The computation of ϕ^{−1} mod e (steps 1-3 above) is based on a technique due to Beaver [2].

7.3 t-out-of-k sharing

The previous two subsections explain how one can obtain a k-out-of-k sharing of d. However, to provide fault-tolerance it is often desirable to have a t-out-of-k sharing enabling any subset of t parties to apply the private key. The simplest solution, due to T. Rabin [40], makes use of a generic technique for converting k-out-of-k sharing of a private RSA key into a t-out-of-k sharing scheme. T. Rabin’s approach immediately applies once our k-out-of-k sharing of d is obtained.

8 Optimizations

We describe several practical techniques to improve the performance of our distributed protocol. These optimizations are incorporated in an implementation of our protocol [34].

Sieving In Step (1) of our protocol (Section 3) the parties repeatedly pick a random shared integer p until they find one that is not divisible by small primes. For this they engage in an interactive trial division protocol. We briefly outline a more efficient approach. Let M be the product of all odd primes less than some bound B_{1}. Suppose the k parties could generate an additive sharing a = ∑ a_{i} of a random integer a in ℤ_{M}^{∗}. Party i could then set its share of p to be p_{i} = rM +a_{i} where r is some random number of the appropriate length to make p_{i} be an n-bit integer. The resulting candidate prime p = ∑ p_{i} is a random n-bit integer that is relatively prime to M. There is no need to run the trial division protocol on p with primes less than B_{1}. The only question that remains is how do the parties generate an additive sharing of a random integer a ∈ ℤ_{M}^{∗}? To do so, each party i generates a random element b_{i} ∈ ℤ_{M}^{∗}. Then a = ∏ b_{i} mod M is a random element of ℤ_{M}^{∗}. The parties then use the BGW method of Section 5.3 to convert the multiplicative sharing of a into an additive sharing. One caveat is that for this to work the BGW method must be made to work in ℤ_{M} (which is not a field). This is done as explained in Section 5.2.

Load balancing In Step (3) of the primality test party 1 computes v_{1} = g^{(N+1−p_{1}−q_{1})/4} mod N while all other parties only had to compute v_{i} = g^{(p_{i}+q_{i})/4} mod N. Notice that N + 1 is roughly 2n bits while p_{i} + q_{i} is only about n bits. Consequently, party 1 works twice as hard as the other parties. To even things out it makes sense to test k candidate N in parallel. In each of these tests the role of party 1 is played by a different party. This way g^{N+1} mod N is computed by a different party for each N. This results in better load balancing improving over all performance by up to a factor of two.

Parallel trial division Recall that once N is computed the parties perform trial division on it before invoking the distributed primality test (Step 2 in Section 3). The k parties can perform this trial division in parallel – each party is in charge of verifying that N is not divisible by some set of small primes. This can be efficiently done by hard-coding all primes p_{1}, p_{2}, …, p_{l} in the range [B_{1}, B_{2}] in a list. Party i is in charge of testing that N is not divisible by any primes p_{j} for all j ≡ i mod k. This factor of k speedup enables us to use a large bound B_{2}, increasing the effectiveness of trial division.

Fermat filter There is no need to run the full primality test of Section 4 on every candidate modulus N. Instead, one can do a Fermat test first and proceed to perform the full test only if the Fermat test succeeds. We refer to the test

g^{N−p−q+1} = g^{N+1−∑(p_{i}+q_{i})} = 1 mod N

as a Fermat test. If equality does not hold, then N is not a product of two primes. To carry out this test in zero-knowledge all k parties compute v_{i} = g^{p_{i}+q_{i}} mod N. They exchange v_{i}’s and verify that ∏ v_{i} = g^{N+1} mod N. This protocol is easily shown to be k − 1 private. It saves the computation of the Jacobi symbol of g for most integers N.

Avoiding quadratic slowdown In Section 3 we noted that our protocols suffer from a quadratic slowdown in comparison to single user generation of an RSA key. The main reason is that both primes p, q are generated at once. We briefly outline a potential solution. Consider the case of three parties, Alice, Bob and Carol. They could generate N as

N = p_{a}q_{b}(r_{a} + r_{b} + r_{c})

where Alice has p_{a}, r_{a} and p_{a} is an n-bit prime. Bob has q_{b}, r_{b} and q_{b} is an n-bit prime. Carol has r_{c}. The number of probes until r_{a} + r_{b} + r_{c} is found to be prime is just as in single user generation of N. Hence, we are able to avoid the quadratic slowdown. Furthermore, no single party knows the complete factorization of the resulting N. Unfortunately, this approach doesn’t scale well. To enable t-privacy N must be a product of t + 2 primes. Also note that in the example above, the parties must perform a distributed primality test to verify that N is the product of three primes. The techniques of this paper do not easily generalize to enable such a test. We note that one can use recent results of [8] to do just that: test that a shared modulus is the product of three primes without revealing its factorization.

9 Robustness

Throughout the paper we use a model in which parties honestly follow the protocol. This is fine when parties are honestly trying to generate a shared RSA key. For some applications it is desirable to make the protocol robust against active adversaries that cheat during the protocol. Since the RSA function is verifiable (the parties can simply check that they correctly decrypt encrypted messages) active adversaries are limited in the amount of damage they can cause. However, it may still be possible that a party cheat during the protocol and consequently be able to factor the resulting N. Similarly, a party can cheat and cause a non-RSA modulus to be incorrectly accepted.

Recently, Frankel, MacKenzie and Yung [24] showed how our protocol can be made to withstand ⌊\frac{k−1}{2}⌋ malicious parties. The protocol enables the parties to detect and exclude the malicious party. In practice, one could run our non-robust protocol until a modulus N is found which is believed to be a product of two primes. Then, the robust Frankel-MacKenzie-Yung protocol can be used to determine that no majority of parties cheated during the non-robust phase. For more results on robust generation of shared RSA keys see [5].

We describe a simple method for making our non-robust protocol robust when the number of participants is small (e.g. less than ten). Consider the case of four parties where at most one of them is malicious. One can run our non-robust protocol until a candidate modulus N is found. At this point the protocol is run four more times, once for each triplet of users. In the first run, party 1 shares her values p_{1}, q_{1} with the other three parties by writing p_{1} = p′_{2} + p′_{3} + p′_{4} and q_{1} = q′_{2} + q′_{3} + q′_{4} where p′_{j}, q′_{j} are random integers in the range [0, N]. Party 1 then sends p′_{i}, q′_{i} to party i for i = 2, 3, 4. Party i adds these values to its own p_{i}, q_{i}. Next, parties 2, 3, 4 run our non-robust protocol among the three of them (ignoring party 1). If the resulting N does not match the N computed when all four parties were involved, or if N turns out to not be an RSA modulus, the N is rejected and the parties announce that one of them is misbehaving. This experiment is repeated with all four triplets – each time exactly one party is excluded from the computation. Assuming at most one party is malicious, the resulting N must be a product of two large primes. Furthermore, the malicious party cannot know the factorization of N since at no point in the protocol does an honest party reveal any information about it’s share to another single party. We note that this approach enables the parties to detect cheating, but it does not help in detecting who the malicious party is.

In general, when k parties are engaged in our non-robust protocol, and c of them are malicious, the protocol can be made robust at the cost of \binom{k}{c} extra invocations. The resulting computation is ⌊\frac{k−c−1}{2}⌋ private. Clearly this approach can only be applied as long as both k and c are very small.

10 Summary and open problems

We presented techniques that allow three or more parties to generate an RSA modulus N = pq such that all parties are convinced that N is indeed a product of two primes; however none of them can factor N. Our methods achieves ⌊\frac{k−1}{2}⌋ privacy. We also show show how the parties can generate shares of a private decryption exponent to allow threshold decryption. To test that N is the product of two primes we presented a distributed double-primality test. We note that our test was recently extended to a triple-primality test [8] enabling k parties to test that N is the product of three primes, without revealing any information about the factors.

To demonstrate the effectiveness of our protocols we implemented them. Generating a 1024 bits shared RSA key among three 300MhZ Pentium machines takes 10 minutes. See [34] for a description of the implementation as well as detailed timing measurements.

An important open problem is the generation of shared keys of special form. For example, a modulus which is a product of “safe primes” (i.e., where both \frac{p−1}{2} and \frac{q−1}{2} are prime) has been considered for security purposes [29] as well as for technical reasons related to threshold cryptography [17, 27]. Currently, our techniques do not enable shared generation of moduli of special form. Progress in this directions would be very helpful.

A. Cocks’ multiplication method

The BGW protocol described in Section 5.1 achieves ⌊\frac{k−1}{2}⌋ privacy and is information theoretically secure. Cocks [11] describes a multiplication protocol that heuristically appears to provide k − 1 privacy. Unfortunately, Cocks’ protocol is far slower than the BGW method. Furthermore, it does not seem possible to prove its security using “natural” complexity assumptions. For completeness we describe a generalization of Cocks’ protocol. As in the settings of Section 5.1 each of the k parties has a private n-bit p_{i}, q_{i}. The parties wish to compute N = (∑ p_{i})(∑ q_{i}) without revealing any other information about their private shares.

Let E, D be a weakly-multiplicative homomorphic public key encryption scheme. E_{p}[m] encrypts a message m using the public key p, while D_{s}(c) decrypts a ciphertext c using the secret key s. The homomorphic property implies that given a ciphertext c_{1} = E_{p}[m_{1}] and a plaintext m_{2} there is an efficient algorithm to compute c = E_{p}[m_{1} · m_{2}]. Here we are assuming the plaintexts m_{1}, m_{2} lie in a ring R where R = ℤ/(Mℤ) for some integer M. Examples of multiplicatively homomorphic public key encryption schemes are RSA and ElGamal encryption [18]. In what follows we are assuming each of the participants has its own public/private key pair. We denote by E_{i}, D_{i} the pair belonging to party i. All parties can encrypt using E_{i} while only party i can decrypt using D_{i}. Also, we assume the plaintext ring R is larger than 2N.

Step 1: Each party i picks k − 1 random integers ⟨a_{i,1}, …, a_{i,i−1}, a_{i,i+1}, …, a_{k}⟩ in [0, |R|/2]. It sets b_{i} = ∑_{j≠i} a_{i,j}.

Step 2: Each party i sends ⟨E_{i}[p_{i}], E_{i}[q_{i}]⟩ to all other parties.

Step 3: For all j ≠ i party i does the following:

a. Using the homomorphic property it computes the three values

α_{i,j} = E_{j}[p_{i}q_{j}] , β_{i,j} = E_{j}[q_{i}p_{j}] , γ_{i,j} = E_{j}[a_{i,j}]

b. Each of α_{i,j}, β_{i,j}, γi, j is then broken into l shares, where l is a security parameter. The shares of α_{i,j} are constructed by picking random u_{1}, …, u_{l} ∈ R such that ∑ u_{i} = 1. Then α_{i,j,1}, …, α_{i,j,l} are defined as: α_{i,j,m} = E_{j}[u_{m}p_{i}q_{j}]. The β_{i,j} and γ_{i,j} are broken into l pieces in a similar way.

c. Party i sends the 3l values ⟨α_{i,j,m}, β_{i,j,m}, γ_{i,j,m}⟩ to party j in a random order. The value l should be chosen large enough so that the random order cannot be undone. This is the main reason this protocol is so much slower than the BGW method.

Step 4: For all j ≠ i party i receives 3l ciphertexts from party j. It decrypts all of them and computes their sum. A moments reflection shows that the sum comes out to be

S_{i,j} = p_{i}q_{j} + q_{j}p_{i} + a_{j,i}

Next, party i computes:

N_{i} = 2p_{i}q_{i} − b_{i} + ∑_{j≠i} S_{i,j}

Again, a moments reflection shows that

∑_{i=1}^{k} N_{i} = 2 ∑_{i,j} p_{i}q_{j} = 2 (∑ p_{i}) (∑ q_{i}) = 2N

Hence, an additive sharing of 2N is obtained. To complete the protocol, the parties may exchange the values N_{i} with each other and make the final value of N public.

When generating a 1024 bit modulus, Cocks states that one should use l on the order of 400. This implies that each party must perform 1200 · k public key decryptions at Step 4 (!) This is significantly slower than the BGW method (over 1000 times slower) where no encryption is used.

Although the protocol may provide k − 1 privacy, we cannot give a simulation proof. Note that a coalition of k − 1 parties learns both the value of N and the encryptions E_{i}[p_{i}], E_{i}[q_{i}] of the party not in the coalition. Providing a simulation for such a transcript seems unlikely under “natural” assumptions. Indeed, Coppersmith [12] shows that if one uses RSA for E_{i} (i.e. E_{i}(m) = m^{e_{i}} mod M_{i}) then there is an attack that factors N in time polynomial in e. Consequently, one cannot use low public exponent RSA as E_{i}. Similarly, it is not clear how to simulate the random permutation used in Step 3.

Throughout the paper, Cocks’ method can be used instead of BGW to compute the function N = (∑ p_{i})(∑ q_{i}). This substitution will make all our protocols heuristically k−1 private. However, we stick with the BGW protocol due to its superior performence and rigorous proof of security. Improving the performence of Cocks’ method and providing a rigorous protocol achieving k − 1 privacy are excellent open problems.

Part II

Generating a Product of Three Primes With an Unknown Factorization

Abstract We describe protocols for three or more parties to jointly generate a composite N = pqr which is the product of three primes. After our protocols terminate N is publicly known, but neither party knows the factorization of N. Our protocols require the design of a new type of distributed primality test for testing that a given number is a product of three primes.

11 Introduction

In this paper, we describe how three (or more) parties can jointly generate an integer N which is the product of three prime numbers (N = pqr). At the end of our protocol the product N is publicly known, but neither party knows the factorization of N. Our main contribution is a new type of probabilistic primality test that enables the three parties to jointly test that an integer N is the product of three primes without revealing the factorization of N. Our primality test simultaneously uses two groups: the group ℤ_{N}^{∗} and the twisted multiplicative group 𝕋_{N} = (ℤ_{N}[x]/(x^{2} + 1))^{∗}/ℤ_{N}^{∗}.

The main motivation for this problem comes from cryptography, specifically the sharing of an RSA key. Consider classical RSA: N = pq is a public modulus, e is a public exponent, and d is secret where de = 1 mod φ(N). At a high level, a digital signature of a message M is obtained by computing M^{d} mod N. In some cases, the secret key d is highly sensitive (e.g. the secret key of a Certification Authority) and it is desirable to avoid storing it at a single location. Splitting the key d into a number of pieces and storing each piece at a different location avoids this single point of failure. One approach (due to Frankel [22]) is to pick three random numbers satisfying d = d_{1} + d_{2} + d_{3} mod φ(N) and store each of the shares d_{1}, d_{2}, d_{3} at one of three different sites. To generate a signature of a message M, site i computes S_{i} = M^{d_{i}} mod N for i = 1, 2, 3 and sends the result to a combiner. The combiner multiplies the S_{i} and obtains the signature S = S_{1}S_{2}S_{3} = M^{d} mod N. If one or two of the sites are broken into, no information about the private key is revealed. An important property of this scheme is that it produces standard RSA signatures; the user receiving the signature is totally unaware of the extra precautions taken in protecting the private key. Note that during signature generation the secret key is never reconstructed at a single location.

To provide fault tolerance, one slightly modifies the above technique to enable any two of the three sites to generate a signature. This way if one of the sites is temporarily unavailable the Certification Authority can still generate signatures using the remaining two sites. If the key was only distributed among two sites, the system would be highly vulnerable to faults.

We point out that classic techniques of secret sharing [41] are inadequate in this scenario. Secret sharing requires one to reconstruct the secret at a single location before it can be used, hence introducing a single point of failure. The technique described above of sharing the secret key such that it can be used without reconstruction at a single location is known as Threshold Cryptography. See [26] for a succinct survey of these ideas and nontrivial problems associated with them.

An important question left out of the above discussion is key generation. Who generates the RSA modulus N and the shares d_{1}, d_{2}, d_{3}? Previously the answer was a trusted dealer would generate N and distribute the shares d_{1}, d_{2}, d_{3} to the three sites. Clearly this solution is undesirable since it introduces a new single point of failure — the trusted dealer. It knows the factorization of N and the secret key d; if it is compromised, the secret key is revealed. Recently, Boneh and Franklin [7] designed a protocol that enables three (or more) parties to jointly generate an RSA modulus N = pq and shares d_{1}, d_{2}, d_{3} of a private key. At the end of the protocol the parties are assured that N is indeed the product of two large primes; however, none of them know its factorization. In addition, each party learns exactly one of d_{1}, d_{2}, d_{3} and has no computational information about the other shares. Thus, there is no need for a trusted dealer. We note that Cocks [11] introduced a heuristic protocol enabling two parties to generate a shared RSA key.

In this paper we design an efficient protocol enabling three (or more) parties to generate a modulus N = pqr such that neither party knows the factorization of N. Once N is generated the same techniques used in [7] can be used to generate shares d_{1}, d_{2}, d_{3} of a private exponent. For this reason, throughout the paper we focus on the generation of the modulus N = pqr and forgo discussion of the generation of the private key. The methods of [7] do not generalize to generate a modulus with three prime factors and new techniques had to be developed for this purpose.

We remark that techniques of secure circuit evaluation [3, 10, 45] can also be used to solve this problem; however, these protocols are mostly theoretical and result in extremely inefficient algorithms.

12 Motivation

The problem discussed in the paper is a natural one and thus our solution is of independent interest. Nonetheless, the problem is well motivated by a method for improving the efficiency of shared generation of RSA keys. To understand this we must briefly recall the method used by Boneh and Franklin [7]. We refer to the three parties involved as Alice, Bob, and Carol. At a high level, to generate a modulus N = pq, the protocol works as follows:

Step 1. Alice picks two random n bit integers p_{a}, q_{a}, Bob picks two random n bit integers p_{b}, q_{b} and Carol picks two random n bit integers p_{c}, q_{c}. They keep these values secret.

Step 2. Using a private distributed computation they compute the value

N = (p_{a} + p_{b} + p_{c})(q_{a} + q_{b} + q_{c}).

At the end of the computation, N is publicly available; however no other information about the private shares is revealed. This last statement is provable in an information-theoretic sense.

Step 3. The three parties perform a distributed primality test to test that N is the product of exactly two primes. As before, this step provably reveals no information about the private shares.

Step (3), the distributed primality test, is a new type of probabilistic primality test which is one of the main contributions of [7]. Step (2) is achieved using an efficient variation of the BGW [3] protocol.

A drawback of the above approach is that both factors of N are simultaneously tested for primality. Hence, the expected number of times step (3) is executed is O(n^{2}). This is much worse than single-user generation of N where the two primes are first generated separately by testing O(n) candidates and then multiplied together. When generating a 1024-bit modulus, this results in significant slowdown when compared with single-user generation. To combat this quadratic slowdown, one may try the following alternate approach.

Step 1. Alice picks a random n-bit prime p and a random n-bit integer r_{a}. Bob picks a random n-bit prime q and a random n-bit integer r_{b}. Carol picks a random n-bit integer r_{c}. They keep these values secret.

Step 2. Using a private distributed computation they compute the value

N = pq(r_{a} + r_{b} + r_{c})

At the end of the computation, N is publicly available; however no other information about the private shares is revealed.

Step 3. The three parties use the results of this paper to test that N is the product of exactly three primes. This step provably reveals no information about the private shares.

At the end of the protocol neither party knows the full factorization of N. In addition, this approach does not suffer from the quadratic slowdown observed in the previous method. Consequently, it is faster by roughly a factor of 50 (after taking effects of trial division into account). As before, step (2) is carried out by an efficient variant of the BGW protocol.

Instead of solving the specific problem of testing that N = pq(r_{a} + r_{b} + r_{c}) is a product of three primes we solve the more general problem of testing that

N = (p_{a} + p_{b} + p_{c})(q_{a} + q_{b} + q_{c})(r_{a} + r_{b} + r_{c})

is a product of three primes without revealing any information about the private shares. This primality test is the main topic of this paper.

For the sake of completeness we point out that in standard single-party cryptography there are several advantages to using an RSA modulus N = pqr rather than the usual N = pq (the size of the modulus is the same in both cases). First, signature generation is much faster using the Chinese Remainder Theorem (CRT). When computing M^{d} mod N one only computes M^{d mod p−1} mod p for all three factors. Since the numbers (and exponents) are smaller, signature generation is about twice as fast as using CRT with N = pq. Another advantage is that an attack on RSA due to Wiener [44] becomes less effective when using N = pqr. Wiener showed that for N = pq if d < N^{1/4} one can recover the secret key d from the public key. When N = pqr the attack is reduced to d < N^{1/6} and hence it may be possible to use smaller values of d as the secret key. Finally, we note that the fastest factoring methods [32] cannot take advantage of the fact that the factors of N = pqr are smaller than those of a standard RSA modulus N = pq.

13 Preliminaries

In this section, we explain the initial setup for our new probabilistic primality test and how it is obtained. We then explain a basic protocol which we use in the later parts of the paper. At first reading, the reader may wish to skip to Sect. 14 and take on faith that the necessary setup is attainable.

13.1 Communication and Privacy Model

The communication and privacy model assumed by our protocol are as follows:

Full connectivity Any party can communicate with any other party. This is a typical setup on a local network or the Internet.

Private and authenticated channels Messages sent from party A to party B are private and cannot be tampered with en route. This simply states that A and B share a secret key which they can use for encryption and authentications.

Honest parties We assume all parties are honest in their following of the protocol. This is indeed the case when they are truly trying to create a shared key. This assumption is used by both [7] and [11]. We note that some recent work [24] makes the protocol of [7] robust against cheating adversaries at the cost of some slowdown in performance (roughly a factor of 100). These robustness results apply to the protocols described in this paper as well.

Collusion Our protocol is 1-private. That is to say that a single party learns no information about the factorization of N = pqr. However, if two of the three parties collude they can recover the factors. For three parties this is fine since our goal is to enable two-out-of-three signature generation. Hence, two parties are always jointly able to recover the secret key. More generally, when k parties participate in our primality test protocol, one can achieve ⌊\frac{k−1}{2}⌋-privacy. That is, any minority of parties learns no information about the factors of N.

13.2 Generation of N

In the previous section, we explained that Alice, Bob, and Carol generate N as

N = (p_{a} + p_{b} + p_{c})(q_{a} + q_{b} + q_{c})(r_{a} + r_{b} + r_{c}),

where party i knows p_{i}, q_{i}, r_{i} for i = a, b, c and keeps these shares secret while making N publicly available. To compute N without revealing any other information about the private shares, we use the BGW protocol [3]. For the particular function above, the protocol is quite efficient; it requires three rounds of communication and a total of six messages. The protocol is informationtheoretically secure, i.e. other than the value of N, party i has no information about the shares held by other parties. This is to say the protocol is 1-private.

We do not go into the details of how the BGW protocol is used to compute N since it is tangential to the topic of this paper. For our purpose, it suffices to assume that N is public while the private shares are kept secret.

An important point is that our primality test can only be applied when p_{a}+p_{b}+p_{c} = q_{a}+q_{b}+q_{c} = r_{a} + r_{b} + r_{c} = 3 mod 4. Hence, the parties must co-ordinate the two lower bits of their shares ahead of time so that the sums are indeed 3 modulo 4. Indeed, this means that a priori each party knows the two least significant bits of the other’s shares.

13.3 Sharing of (p − 1)(q − 1)(r − 1) and (p + 1)(q + 1)(r + 1)

Let p = p_{a} + p_{b} + p_{c}, q = q_{a} + q_{b} + q_{c}, and r = r_{a} + r_{b} + r_{c}. We define φ̂ = (p − 1)(q − 1)(r − 1). Since p, q, and r are not necessarily prime, φ̂ may not equal φ(N). Our protocol requires that the value φ̂ be shared additively among the three parties. That is, φ̂ = φ_{a} + φ_{b} + φ_{c}, where only party i knows φ_{i} for i = a, b, c.

An additive sharing of φ̂ is achieved by observing that φ̂ = N − pq − pr − qr + p + q + r − 1. To share φ̂, it suffices to represent pq + pr + qr using an additive sharing A + B + C among the three parties. The additive sharing of φ̂ is then

φ_{a} = N − A + p_{a} + q_{a} + r_{a} − 1 ; φ_{b} = −B + p_{b} + q_{b} + r_{b} ; φ_{c} = −C + p_{c} + q_{c} + r_{c}.

The conversion of pq + pr + qr into an additive sharing A + B + C is carried out using a simple variant of the BGW protocol used in the computation of N. The BGW protocol can be used to compute the value pq; however, instead of making the final result public the BGW variant shares the result additively among the three parties. The details of this variant can be found in [7, Section 6.2].

As before, we do not give the full details of the protocol for converting pq + pr + qr into an additive sharing. Since we wish to focus on the primality test, will assume that an additive sharing of φ̂ is available in the form of φ_{a} + φ_{b} + φ_{c}.

In addition to a sharing of φ̂, we also require an additive sharing of ψ̂ = (p + 1)(q + 1)(r + 1). Once an additive sharing of pq + pr + qr is available it is trivial to generate an additive sharing of ψ̂. Simply set

ψ_{a} = N + A + p_{a} + q_{a} + r_{a} + 1 ; ψ_{b} = B + p_{b} + q_{b} + r_{b} ; ψ_{c} = C + p_{c} + q_{c} + r_{c}.

13.4 Comparison Protocol

Our primality test makes use of what we call a comparison protocol. Let A be a value known to Alice, B a value known to Bob, and C a value known to Carol. We may assume A, B, C ∈ ℤ_{N}^{∗}. The protocol enables the three parties to test that ABC = 1 mod N without revealing any other information about the product ABC. We give the full details of the protocol in this section.

Let P > N be some prime known to all parties. The protocol proceeds as follows:

Step 1. Carol picks a random element C_{1} ∈ ℤ_{N}^{∗} and sets C_{2} = CC_{1}^{−1} mod N. Clearly C = C_{1}C_{2} mod N. Carol then sends C_{1} to Alice and C_{2} to Bob.

Step 2. Alice sets A′ = AC_{1} and Bob sets B′ = (BC_{2})^{−1} mod N. Both values A′ and B′ can be viewed as integers in the range [0, N). The problem is now reduced to testing whether A′ = B′ (as integers) without revealing any other information about A and B.

Step 3. Alice picks a random c ∈ ℤ_{P}^{∗} and d ∈ ℤ_{P}. She sends c and d to Bob. Alice then computes h(A′) = cA′ + d mod P and sends the result to Carol. Bob computes h(B′) = cB′ + d mod P and sends the result to Carol.

Step 4. Carol tests if h(A′) = h(B′) mod P. If so, she announces that ABC = 1 mod N. Otherwise she announces ABC ≠ 1 mod N.

The correctness and privacy of the protocol are stated in the next two lemmata. Correctness is elementary and is stated without proof. Lemma 13.1 Let A, B, C ∈ ℤ_{N}^{∗}. At the end of the protocol, the parties correctly determine if ABC = 1 mod N or ABC ≠ 1 mod N. Lemma 13.2 The protocol is 1-private. That is, other than the result of the test, each party learns no new information. Proof To prove the protocol is 1-private, we provide a simulation argument for each party’s view of the protocol. Alice’s view of the protocol is made up of the values A, C_{1}, c, d, h(A′), and the final result of the test. These values can be easily simulated by picking C_{1} at random in ℤ_{N}^{∗}, picking c at random in ℤ_{P}^{∗} and d at random in ℤ_{P}. This is a perfect simulation of Alice’s view. A simulation argument for Bob is the same, mutatis mutandis.

Simulating Carol’s view is more interesting. Carol’s view consists of C, C_{1}, C_{2}, h(A′), h(B′), and the result of the test. The key observation we make is that h(A′) and h(B′) reveal no information about A and B, since they are either equal or are random independent elements of ℤ_{P}. Which of the two actually occurs is determined by the result of the test. The independence follows since the family of hash functions h(x) = cx + d mod P is a universal family of hash functions (i.e. knowing neither c nor d, the values h(x) and h(y) are independent for any x, y ∈ ℤ_{P}).

To simulate Carol’s view, the simulator picks C_{1}, C_{2} ∈ ℤ_{N}^{∗} at random so that C = C_{1}C_{2} mod N. Then, depending on the results of the test, it either picks the same random element of ℤ_{P} twice or picks two random independent elements of ℤ_{P}. This is a perfect simulation of Carol’s view. This proves that Carol gains no extra information from the protocol since, given the outcome of the test, she can generate the values sent by Alice and Bob herself. □

14 The Probabilistic Primality Test

We now describe the main primality test. As discussed in the previous section, our primality test applies once the following setup is achieved:

Shares Each party i has three secret n-bit values p_{i}, q_{i}, and r_{i} for i = a, b, c.

The modulus N = (p_{a} + p_{b} + p_{c})(q_{a} + q_{b} + q_{c})(r_{a} + r_{b} + r_{c}) is public. We set p = p_{a} + p_{b} + p_{c}, q = q_{a} + q_{b} + q_{c}, and r = r_{a} + r_{b} + r_{c}. Throughout this section, we are assuming that p = q = r = 3 mod 4. Thus, the parties must a priori co-ordinate the two least significant bits of their shares so that this condition holds.

Sharing φ̂, ψ̂ The parties share (p − 1)(q − 1)(r − 1) as φ_{a} + φ_{b} + φ_{c} and (p + 1)(q + 1)(r + 1) as ψ_{a} + ψ_{b} + ψ_{c}.

Given this setup, they wish to test that p, q, and r are distinct primes without revealing any of p, q, and r. At this point, nothing is known about p, q, and r other than that p = q = r = 3 mod 4.

Throughout the section, we use the following notation:

φ̂ = φ_{a} + φ_{b} + φ_{c} = (p − 1)(q − 1)(r − 1)
ψ̂ = ψ_{a} + ψ_{b} + ψ_{c} = (p + 1)(q + 1)(r + 1)

Clearly, if N is a product of three distinct primes, then φ(N) = φ̂ and ψ(N) = ψ̂. Otherwise, these equalities may not hold.

Our primality test is made up of four steps. At the beginning of each section, we state what each step tests. In the subsequent subsections, we explain how each step is carried out without revealing any information about the factors of N.

Step 1. The parties pick a random g ∈ ℤ_{N}^{∗} and jointly test that g^{φ_{a}+φ_{b}+φ_{c}} = 1 mod N. If the test fails, N is rejected. This step reveals no information other than the outcome of the test. We refer to this step as a Fermat test in ℤ_{N}^{∗} (see Sect. 14.2 for further details).

Step 2. The parties perform a Fermat test in the twisted group 𝕋_{N} defined as (ℤ_{N}[x]/(x^{2} + 1))^{∗}/ℤ_{N}^{∗}. Notice that x^{2} + 1 is irreducible modulo N, since p = q = r = 3 mod 4. If N is the product of three distinct primes then the order of 𝕋_{N} is ψ(N) = (p+1)(q+1)(r+1). To carry out the Fermat test in 𝕋_{N}, the parties pick a random g ∈ 𝕋_{N} and jointly test that g^{ψ_{a}+ψ_{b}+ψ_{c}} = 1 (see Sect. 14.2 for further details). If the test fails, N is rejected. This step reveals no information other than the outcome of the test.

Step 3. The parties jointly test that N is the product of at most three prime powers. The implementation of this step is explained in Sect. 14.1. If the test fails, N is rejected.

Step 4. The parties jointly test that

gcd(N, p + q + r) = 1.

This step reveals no information other than the outcome of the test. The implementation of this step is explained in Sect. 14.3. If the test fails, N is rejected. Otherwise, N is accepted as the product of three primes.

The following fact about the twisted group 𝕋_{N} = (ℤ_{N}[x]/(x^{2} + 1))^{∗}/ℤ_{N}^{∗} is helpful in the proof of the primality test. Fact 14.1 Let N be an integer and k a prime such that k^{2}|N. Then, k divides both φ(N) and ψ(N). Proof Let α ≥ 2 be the number of times k divides N, i.e. N = k^{α}w where gcd(k, w) = 1. Then φ(N) = k^{α−1}(k − 1)φ(w) and, hence, k divides φ(N).

To see that k divides ψ(N) = |𝕋_{N}|, note that 𝕋_{N} ≅ 𝕋_{k^{α}} × 𝕋_{w}. When k = 3 mod 4, we know that x^{2} + 1 is irreducible in ℤ_{k} and, hence, |𝕋_{k^{α}}| = k^{α−1}(k + 1). It follows that k divides ψ(N). When k = 1 mod 4, we have |𝕋_{k^{α}}| = k^{α−1}(k − 1) and, again, k divides ψ(N). □

We can now prove that the aforementioned four steps are indeed a probabilistic test for proving that N is a product of three primes. Theorem 14.2 Let N = pqr = (p_{a} +p_{b} +p_{c})(q_{a} +q_{b} +q_{c})(r_{a} +r_{b} +r_{c}), where p = q = r = 3 mod 4 and gcd(N, p + q + r) = 1. If N is a product of three primes, it is always accepted. Otherwise, N is rejected with probability at least half. The probability is over the random choices made in steps 1–4 above.

Proof Suppose p, q, and r are distinct primes. Then, steps (1), (2), and (3) clearly succeed. Step (4) succeeds by assumption. Hence, in this case, N always passes the test (as required).

Suppose N is not the product of three distinct primes. Assume, for the sake of deriving a contradiction, that N passes all four steps with probability greater than 1/2. Since N passes step (3) with probability greater than 1/2 we know that N = z_{1}^{α_{1}}z_{2}^{α_{2}}z_{3}^{α_{3}} for three primes z_{1}, z_{2}, and z_{3} (not necessarily distinct). Since N passes step (4) we know gcd(N, p + q + r) = 1. Define the following two groups:

G = {g ∈ ℤ_{N}^{∗} | g^{φ_{a}+φ_{b}+φ_{c}} = 1} and
H = {g ∈ 𝕋_{N} | g^{ψ_{a}+ψ_{b}+ψ_{c}} = 1} .

Clearly, G is a subgroup of ℤ_{N}^{∗} and H is a subgroup of the twisted group 𝕋_{N}. By showing that at least one of G or H is a proper subgroup, we will prove that either step (1) or (2) fails with probability at least 1/2. There are two cases to consider:

Case 1: p, q, and r are not pairwise relatively prime. Without loss of generality, we may assume that gcd(p, q) > 1. Let k be a prime factor of gcd(p, q). Recall that N is odd, so k > 2 (since k divides N).

Since N = pqr we know that k^{2}|N. Hence, by Fact 14.1, k|φ(N) and k|ψ(N). We claim that either k does not divide φ̂ or k does not divide ψ̂. To see this, observe that if k|φ̂ and k|ψ̂, then k divides ψ̂ − φ̂ = p(2q + 2r) + q(2r) + 2. Since k divides both p and q, we conclude that k|2, which contradicts k > 2.

First, we examine when k does not divide φ̂. Since k is a prime factor of φ(N), there exists an element g ∈ ℤ_{N}^{∗} of order k. However, since k does not divide φ̂ we know that gφ̂ ≠ 1. Hence, g ∉ G proving that G is a proper subgroup of ℤ_{N}^{∗}. If k does not divide ψ̂ a similar argument proves that H is a proper subgroup of the twisted group 𝕋_{N}.

Case 2: p, q, and r are pairwise relatively prime. We can write p = z_{1}^{α}, q = z_{2}^{β}, and r = z_{3}^{γ} with z_{1}, z_{2}, and z_{3} distinct primes. By assumption, we know that one of α, β, or γ is greater than 1. Without loss of generality, we may assume α > 1.

We first observe that none of the z_{i} can divide gcd(φ̂, ψ̂). Indeed, if this were not the case, then z_{i} would divide φ̂ + ψ̂ = 2(N + p + q + r). But then, since z_{i} divides N, it must also divide p + q + r, contradicting that gcd(N, p + q + r) = 1 (as tested in step (4)).

We now know that either z_{1} does not divide φ̂ or it does not divide ψ̂. However, since z_{1}^{2} divides N, we obtain, by Fact 14.1, that z_{1}|φ(N) and z_{1}|ψ(N). We can now proceed as in case (1) to prove that either G is a proper subgroup of ℤ_{N}^{∗} or H is a proper subgroup of 𝕋_{N}.

□

Clearly, most integers N that are not a product of three primes will already fail step (1) of the test. Hence, steps (2–4) are most likely executed only once a good candidate N is found.

Notice that the condition gcd(N, p + q + r) = 1 is necessary. Without it, the theorem is false as can be seen from the following simple example: p = w^{3}, q = aw^{2} + 1, and r = bw^{2} − 1 where w, q, r are three odd primes with p = q = r = 3 mod 4. In this case, N = pqr will always pass steps 1–3, even though it is not a product of three distinct primes.

14.1 Step 3: Testing that N = p^{α}q^{β}r^{γ}

Our protocol for testing that N is a product of three prime powers borrows from a result of van de Graaf and Peralta [38]. Our protocol works as follows:

Step 0. From our construction of φ̂, we know that it is divisible by 8. However, the individual shares φ_{a}, φ_{b}, and φ_{c} which sum to φ̂ may not all be divisible by 8. To correct this, Alice generates two random numbers a_{1}, a_{2} ∈ ℤ_{8} such that a_{1} + a_{2} = φ_{a} mod 8. She sends a_{1} to Bob and a_{2} to Carol. Alice sets φ_{a} ← φ_{a} − a_{1} − a_{2}, Bob sets φ_{b} ← φ_{b} + a_{1} and Carol set φ_{c} ← φ_{c} + a_{2}. Observe that, at this point,

\frac{φ̂}{8} = \frac{φ_{a}}{8} + ⌊\frac{φ_{b}}{8} ⌋ + ⌈\frac{φ_{c}}{8} ⌉ .

Step 1. The parties first agree on eight random numbers g_{1}, g_{2}, …, g_{8} in ℤ_{N}^{∗}, all with Jacobi symbol +1.

Step 2. For i, j ∈ {1, 2, …, 8}, we say that i is equivalent to j (this defines equivalence classes of {1, 2, …, 8}) if

(\frac{g_{i}}{g_{j}} )^{\frac{φa+φ_{b}+φc}{8}} = 1 (mod N).

Since all three parties know g_{i} and g_{j}, they can test if i is equivalent to j as follows:

1. Alice computes A = (g_{i}/g_{j})^{φ_{a}/8} mod N, Bob computes B = (g_{i}/g_{j})^{⌊φ_{b}/8⌋} mod N, and Carol computes C = (g_{i}/g_{j})^{⌈φ_{c}/8⌉} mod N.

2. Using the comparison protocol of Sect. 13.4, they then test if ABC = 1 mod N. The comparison protocol reveals no information other than whether or not ABC = 1 mod N.

Step 3. If the number of equivalence classes is greater than four, N is rejected. Otherwise, N is accepted.

Testing that the number of equivalences classes is at most four requires at most twenty-two invocations of the comparison protocol. Note that we restrict our attention to the elements g_{i} with Jacobi symbol +1 for efficiency’s sake. Without this restriction, the number of equivalence classes to check for is eight and, thus, many more applications of the comparison protocol would be necessary.

The following lemma shows that when N is a product of three distinct primes, it is always accepted. When N has more than three prime factors, it is rejected with probability at least 1/2. Note that if N is a product of three prime powers, it will always be accepted by this protocol. We will use the following notation:

J = \{g ∈ ℤ_{N}^{∗} | (\frac{g}{N} ) = +1\}
Q = {g ∈ J | g is a quadratic residue in ℤ_{N}^{∗}}

The index of Q in J is 2^{d(N)−1} or 2^{d(N)} (exactly when N is a perfect square), where d(N) is the number of distinct prime factors of N.

Lemma 14.3 Let N = pqr be an integer with p = q = r = 3 mod 4. If p, q, and r are distinct primes, then N is always accepted. If the number of distinct prime factors of N is greater than three, then N is rejected with probability at least half. Proof If N is the product of three distinct primes, then the index of Q in J is four. Two elements g_{1}, g_{2} ∈ ℤ_{N}^{∗} belong to the same coset of Q in J if and only if g_{1}/g_{2} is a quadratic residue, i.e. if and only if (g_{1}/g_{2})^{φ(N)/8} = 1 mod N. Since, in this case, φ(N) = φ̂ = φ_{a} + φ_{b} + φ_{c}, step (2) tests if g_{i} and g_{j} are in the same coset of Q. Since the number of cosets is four, there are exactly four equivalence classes and, thus, N is always accepted.

If N contains at least four distinct prime factors, we show that it is rejected with probability at least 1/2. Define

Q̂ = {g ∈ J | g^{φ̂/8} = 1 (mod N)} .

Since, in this case, φ̂ may not equal φ(N), the group Q̂ need not be the same as the group Q.

We now show that the index of Q̂ in J is at least eight. Since p = q = r = 3 mod 4, we know that φ̂/8 is odd (since φ̂ = (p − 1)(q − 1)(r − 1) ). Notice that f g ∈ J satisfies g^{x} = 1 for some odd x, g must be a quadratic residue (a root is g^{(x+1)/2}). Hence, Q̂ ⊆ Q and hence is a subgroup of Q. Since the index of Q in J is at least eight, it follows that the index of Q̂ in J is at least eight.

It remains to show that when the index of Q̂ in J is at least eight, N is rejected with probability at least 1/2. In step (2), two elements g_{1}, g_{2} ∈ J are said to be equivalent if they belong to the same coset of Q̂ in J. Let R be the event that all 8 elements g_{i} ∈ J chosen randomly in step (1) fall into only four of the eight cosets. Then

Pr[R] ≤ \binom{8}{4} · (\frac{1}{2})^{8} ≈ 0.27 < \frac{1}{2}.

N is accepted only when the event R occurs. Since R occurs with probability less than 1/2, the number N is rejected with probability at least 1/2 as, required. □

Next, we prove that the protocol leaks no information when N is indeed the product of three distinct primes. In case N is not of this form, the protocol may leak some information; however, in this case, N is discarded and is of no interest. To prove that the protocol leaks no information we rely on a classic cryptographic assumption (see [6]) called Quadratic Residue Indistinguishability (QRI). This cryptographic assumption states that when N = pq with p = q = 3 mod 4, no polynomial time algorithm can distinguish between the groups J and Q defined above. In other words, for any polynomial time algorithm A and any constant c > 0,

| Pr_{g∈J}[A(g) = “yes”] − Pr_{g∈Q}[A(g) = “yes”]| < \frac{1}{(log N)^{c}} .

Lemma 14.4 If N is a product of three distinct primes, then the protocol is 1-private, assuming QRI. Proof Sketch To prove that each party learns no information other than that N is a product of three prime powers, we provide a simulation argument. We show that each party can simulate its view of the protocol; hence, whatever values it receives from its peers, it could have generated itself. By symmetry, we need only consider Alice. Alice’s view of the protocol consists of the elements g_{1}, g_{2}, …, g_{8} and bit values b_{i,j} indicating whether (g_{i}/g_{j})φ̂ = 1 (recall that we already gave a simulation algorithm for the comparison protocol in Sect. 13.4). Thus, Alice learns whether or not each g_{i}/g_{j} is a quadratic residue. We argue that, under QRI, this provides no computational information (since it can be simulated). To simulate Alice’s view, the simulation algorithm works as follows: it picks eight random elements g_{1}, g_{2}, …, g_{8} ∈ J. It then randomly associates with each g_{i} a value in the set {0, 1, 2, 3}. This value represents the coset of Q in which g_{i} lies. The simulator then says that g_{i}/g_{j} is a quadratic residue if and only if the value associated with g_{i} is equal to that associated with g_{j}. Under QRI, the resulting distribution on g_{1}, g_{2}, …, g_{8}, b_{1,1}, b_{1,2}, …, b_{8,8} is computationally indistinguishable from Alice’s true view of the protocol.

We note that the value a_{1} ∈ ℤ_{8} that Alice sends Bob in step (0) is an element of ℤ_{8} chosen uniformly at random. Hence, Bob can simulate it trivially. Similarly, Carol can trivially simulate a_{2} ∈ ℤ_{8}. □

14.2 Implementing a Fermat Test with No Information Leakage

We briefly show how to implement a Fermat test in ℤ_{N}^{∗} without leaking any extra information about the private shares. The exact same method works in the twisted group 𝕋_{N} as well. To check that g ∈ ℤ_{N}^{∗} satisfies g^{φ_{a}+φ_{b}+φ_{c}} = 1 mod N, we perform the following steps:

Step 1. Each party computes R_{i} = g^{φ_{i}} mod N (i = a, b, c).

Step 2. They test that R_{a}R_{b}R_{c} = 1 mod N by simply revealing the values R_{1}, R_{2}, and R_{3}. Accept N if the test succeeds. Otherwise, reject.

Clearly, the protocol succeeds if and only if gφ̂ = 1 mod N. We show that it leaks no other information. Lemma 14.5 If N = pqr is the product of three distinct primes, then the protocol is 2-private. Proof We show that no two parties learn any information about the private share of the third (other than that gφ̂ = 1 mod N). By symmetry, we may restrict our attention to Alice and Bob. Since, by assumption, N is the product of three distinct primes, we know that gφ̂ = 1 mod N. Hence, g^{φ_{a}+φ_{b}} = g^{−φ_{c}}. To simulate the value received from Carol, the simulation algorithm simply computes R_{c} = g^{−φ_{a}−φ_{b}}. Indeed, this is a perfect simulation of Alice and Bob’s view. Thus, they learn nothing from Carol’s message since they could have generated it themselves. □

14.3 Step 4: Zero-Knowledge Test that gcd(N, p + q + r) = 1

Our protocol for this step is based on a protocol similar to the one used in the computation of N. We proceed as follows:

Step 1. Alice picks a random y_{a} ∈ ℤ_{N}, Bob picks a random y_{b} ∈ ℤ_{N}, and Carol picks a random y_{c} ∈ ℤ_{N}.

Step 2. Using the BGW protocol as in Sect. 13.2, they compute

R = (p_{a} + q_{a} + r_{a} + p_{b} + q_{b} + r_{b} + p_{c} + q_{c} + r_{c})(y_{a} + y_{b} + y_{c}) mod N.

At the end of the protocol, R is publicly known; however, no other information about the private shares is revealed.

Step 3. Now that R is public, the parties test that gcd(R, N) = 1. If not, N is rejected. Otherwise, N is accepted.

Lemma 14.6 If N is the product of three distinct n-bit primes p, q, and r, with gcd(N, p+q +r) = 1, then N is accepted with probability 1 − ϵ for some ϵ < 1/2^{n−3}. Otherwise, N is always rejected. Proof Clearly, if gcd(N, p + q + r) > 1 then gcd(R, N) > 1 and therefore N is always rejected. If gcd(N, p + q + r) = 1, then N is rejected only if gcd(N, y_{a} + y_{b} + y_{c}) > 1. Since y_{a} + y_{b} + y_{c} is a random element of ℤ_{N}, this happens with probability less than (1/2)^{n−3}. □

Lemma 14.7 If N is the product of three distinct n-bit primes p, q, and r, with gcd(N, p+q +r) = 1, then the protocol is 1-private. Proof Note that, since the BGW protocol is 1-private, the above protocol can be at best 1private. By symmetry, we need only show how to simulate Alice’s view. Alice’s view consists of her private shares p_{a}, q_{a}, y_{a} and the number R. Since R is independent of her private shares, the simulator can simulate Alice’s view by simply picking R in ℤ_{N} at random. This is a perfect simulation. □

15 Extensions

One can naturally extend our protocols in two ways. First, one may allow more than three parties to generate a product of three primes with an unknown factorization. Second, one may wish to design primality tests for testing that N is a product of k primes for some small k. We briefly discuss both extensions below.

Our protocols easily generalize to allow any number of parties. When k parties are involved, the protocols can be made ⌊\frac{k−1}{2}⌋-private. This is optimal in the information-theoretic sense and follows from the privacy properties of the BGW protocol. The only complexities in this extension are the comparison protocol of Sect. 13.4 and Step (0) of Sect. 14.1. Both protocols generalize to k parties; however, they require a linear (in k) number of rounds of communication.

Securely testing that N is a product of k primes for some fixed k > 3 seems to be harder. Our results apply when k = 4 (indeed Theorem 14.2 remains true in this case). For k > 4, more complex algorithms are necessary. This extension may not be of significant interest since it is not well motivated and requires complex protocols.

Another natural question is whether only two parties can generate a product of three primes with an unknown factorization. The answer appears to be yes, although the protocols cannot be information-theoretically secure. Essentially, one needs to replace the BGW protocol for computing N with a two-party private multiplication protocol. This appears to be possible using results of [11].

16 Conclusions and Open Problems

Our main contribution is the design of a probabilistic primality test that enables three (or more) parties to generate a number N with an unknown factorization and test that N is the product of three distinct primes. The correctness of our primality test relies on that we simultaneously work in two different subgroups of ℤ_{N}[x]/(x^{2} + 1)^{∗}, namely ℤ_{N}^{∗} and the twisted multiplicative group 𝕋_{N}.

Our protocol generalizes to an arbitrary number of parties k and achieves ⌊\frac{k−1}{2}⌋-privacy — the best possible in an information-theoretic setting.

Recall that our primality test can be applied to N = pqr whenever p = q = r = 3 mod 4. We note that simple modifications enable one to apply the test when p = q = r = 1 mod 4 (essentially, this is done by reversing the roles of ℤ_{N}^{∗} and the twisted group). However, it seems that one of these restrictions is necessary; we do not know how to carry out the test without the assumption that p = q = r mod 4. The assumption plays a crucial role in the proof of Lemma 14.3.

A natural question to ask is whether more advanced primality testing techniques can be used to improve the efficiency of our test. For instance, recent elegant techniques due to Grantham [30] may be applicable in our scenario as well.

References

[1] N. Alon, Z. Galil and M. Yung, “Dynamic-resharing verifiable secret sharing,” ESA 1995.

[2] D. Beaver, “Security, fault tolerance, and communication complexity in distributed systems,” Ph.D. thesis, Harvard University, May 1990.

[3] M. Ben-Or, S. Goldwasser, A. Wigderson, “Completeness theorems for non-cryptographic fault tolerant distributed computation”, STOC 1988, pp. 1–10.

[4] J. Benaloh (Cohen), “Secret sharing homomorphisms: keeping shares of a secret secret,” Crypto ’86, 251-260.

[5] S. Blackburn, S. Blake-Wilson, M. Burmester, S. Galbraith, “Secure construction of shared RSA keys”, preprint.

[6] M. Blum and S. Goldwasser. An efficient probabilistic public key encryption scheme that hides all partial information. In Proceedings of Advances in Cryptology: CRYPTO ’84, pages 289–302. Lecture Notes in Computer Science, Springer-Verlag, New York, 1985.

[7] D. Boneh, M. Franklin, “Efficient generation of shared RSA keys”, in Proceedings Crypto’ 97, pp. 425–439.

[8] D. Boneh, J. Horwitz, “Generating a product of three primes with and unknown factorization”, Proc. of the third Algorithmic Number Theory Symposium (ANTS), 1998, pp.

[9] J. Carter and M. Wegman, ”Universal classes of hash functions”, J. Comput. Syst. Sci. 18 (1979), 143–154.

[10] D. Chaum, C. Crépeau, and I. Damgård, “Multiparty unconditionally secure protocols,” ACM STOC 1988, 11-19.

[11] C. Cocks, “Split knowledge generation of RSA parameters”, Available from the author

cliff cocks@cesg.gov.uk.

[12] D. Coppersmith, “Private Communications”.

[13] N. De Bruijn, ”On the number of uncanceled elements in the sieve of Eratosthenes”, Proc. Neder. Akad. Wetensch, vol. 53, 1950, pp. 803–812. Reviewed in LeVeque Reviews in Number Theory, Vol. 4, Section N-28, p. 221.

[14] A. DeSantis, Y. Desmedt, Y. Frankel, M. Yung, “How to share a function securely”, STOC 1994, pp. 522–533.

[15] Y. Desmedt, “Threshold cryptography,” European Transactions on Telecommunications and Related Technologies, Vol. 5, No. 4, July-August 1994, pp. 35–43.

[16] Y. Desmedt, G. Di Crescenzo, M. Burmester, “Multiplicative non-abelian sharing schemes and their applications to threshold cryptography”, Asiacrypt ’94, pp. 21–32.

[17] Y. Desmedt and Y. Frankel, “Shared generation of authenticators and signatures”, Crypto ’91, 457–469.

[18] T. ElGamal, “A public key cryptosystem and a signature scheme based on the discrete logarithm”, IEEE Transactions on Information Theory, 31(4):469–472, 1985.

[19] R. Fagin, M. Naor, P. Winkler, “Comparing information without leaking it”, CACM, Vol 39, No. 5, May 1996, pp. 77–85.

[20] U. Feige, A. Fiat, and A. Shamir, “Zero-knowledge proofs of identity,” Journal of Cryptology 1 (1988), 77-94.

[21] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” Crypto ’86, 186-194.

[22] Y. Frankel, “A practical protocol for large group oriented networks”, Eurocrypt 89, pp. 56–61.

[23] Y. Frankel, P. MacKenzie, M. Yung, “Optimal resilience proactive proactive public key cryptosystems”, FOCS 1997.

[24] Y. Frankel, P. MacKenzie, M. Yung, “Robust efficient distributed RSA key generation”, STOC 1998, pp. 663–672.

[25] M. Franklin and S. Haber, “Joint encryption and message-efficient secure computation,” Journal of Cryptology, 9 (1996), 217-232.

[26] P. Gemmel, “An introduction to threshold cryptography”, in CryptoBytes, a technical newsletter of RSA Laboratories, Vol. 2, No. 7, 1997.

[27] R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, “Robust and efficient sharing of RSA functions”, Crypto 96, pp. 157–172.

[28] O. Goldreich, S. Micali, A. Wigderson, “How to play any mental game”, STOC 1987, pp. 218–229.

[29] J. Gordon, “Strong primes are easy to find”, Eurocrypt 84, pp. 216–223.

[30] J. Grantham. A probable prime test with high confidence. Available online

    (http://www.clark.net/pub/grantham/pseudo/).

[31] L. Guillou and J. Quisquater, “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory,” Eurocrypt ’88, 123-128.

[32] A. Lenstra, H. W. Lenstra ed, “The development of the number field sieve”, Lecture Notes in Computer Science 1554, Springer-Verlag, 1994.

[33] H. W. Lenstra, “Factoring integers with elliptic curves”, Annals of Mathematics, 126:649– 673, 1987.

[34] M. Malkin, T. Wu, D. Boneh, “Experimenting with shared RSA key generation”, preprint.

[35] K. Ohta and T. Okamoto, “A modification of the Fiat-Shamir scheme,” Crpto ’88, 232-243.

[36] H. Ong and C. Schnorr, “Fast signature generation with a Fiat Shamir-like scheme,” Eurocrypt ’90, 432-440.

[37] T. Pederson, “A threshold cryptosystem without a trusted party,” Proceedings of Eurocrypt 91, pp. 522–526.

[38] R. Peralta and J. van de Graaf. A simple and secure way to show the validity of your public key. In Proceedings of Advances in Cryptology: CRYPTO ’87, pages 128–134. Lecture Notes in Computer Science, Springer-Verlag, New York, 1988.

[39] M. Rabin, “Probabilistic algorithm for testing primality”, J. of Number Theory, vol. 12, pp. 128–138, 1980.

[40] T. Rabin, “A simplified approach to threshold and proactive RSA”, Proceedings of Crypto’ 98.

[41] A. Shamir, “How to share a secret”, Comm. of the ACM, Vol. 22, 1979, pp. 612–613.

[42] R. Solovay, V. Strassen, “A fast monte carlo test for primality”, SIAM journal of computing, vol. 6, pp. 84–85, 1977.

[43] M. Wegman and J. Carter, “New hash functions and their use in authentication and set equality”, J. Comput. Syst. Sci. 22 (1981), 265–279.

[44] M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36(3):553-558, 1990.

[45] A. Yao, “How to generate and exchange secrets”, FOCS 1986, pp. 162–167.