Efficient generation of shared RSA keys.
We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus 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. All results are presented in the honest but curious scenario (passive adversary).
Introduction
We present e-cient protocols for a number of parties to jointly generate an RSA modulus
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 which none of the participants
know the factorization. A good example is the original Fiat-Shamir authentication protocol
[19] where all parties use the same modulus N , but none of them know its factorization. For
other examples see [18, 23, 28, 30, 31]. 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 [24] for a survey. Let pq be an
RSA modulus and d; e be signing and verication exponents respectively, i.e. de
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 [35], 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 [20]: pick random d i 's satisfying
and give d i to party i. Abstractly,
to sign a message m each party computes s 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
Supported by darpa contract #F30602-97-C-0326
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 Certicate Authority. Constructions providing a t-out-of-k RSA threshold signatures
schemes can be found in [16, 13, 21, 34].
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 [32], but not for RSA.
The paper is organized as follows: we give a high level description of our protocol in Section 2.
In Sections 3{5 we explain the various stages for generating a modulus with an unknown
factorization. In Section 6 we describe protocols that given a public exponent e, generate shares
of the corresponding private key 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 6.3. We discuss various practical improvements
of our protocol in Section 7.
We note that generic secure circuit evaluation techniques, e.g. [38, 26, 3, 9] 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 ine-cient.
1.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.
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
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 is often called the honest but curious scenario. In Section 8 we discuss some results
showing how this assumption can be relaxed. Recently, Frankel, MacKenzie and Yung [22]
showed how our protocol can be made robust against b k 1
malicious parties.
Collusion Our protocol is b k 1c private. That is, any coalition of size at most b k 1c learns no
information about the factorization of pq. However, a coalition of more than b k 1c 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 is limited to achieving b k 1c 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 [10]. 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) satised by our protocol we provide a simulation
argument for each of its components.

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 public/private pair of
exponents 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 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
k is not divisible by any prime less than some bound B 1 . Details are
given in Section 5. If this step fails repeat step (a).
Denote the secret values picked at the rst iteration by , and at the second iteration
by
(2) Using a private distributed computation the k parties compute
Other than the value of N , this step reveals no further information about the secret values
. Details are given in Section 4.
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
(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 3.
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 6.
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
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
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 rst 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
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 eectiveness of trial
division. Suppose a random n-bit number p passes the trial division test where all primes less than
are tested. We take How likely is p to be prime? Using a classic
result due to Mertens, DeBruijn [12] shows that asymptotically
Pr[p prime j trial division up to
Hence, when bits and 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 7.
Generation of shares In step (1) of the protocol each party uniformly picks a random n bit
integer p i as its secret share. The prime p is 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
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 signicant 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 Z (2)
n be the set of RSA
that can be output by our protocol above when k parties are involved. We assume
k < log N .
Lemma 2.1 Suppose there exists a polynomial time algorithm A that given a random N 2 Z
(2)
chosen from the distribution above and the shares hp
at least 1=n d . Then there exists an expected polynomial time algorithm B that factors 1=4k 3 n d of
the integers in Z (2)
n .
Assuming the hardness of factoring, the lemma shows that even an adversary who is given N
and the private shares of k 1 parties cannot factor the modulus N generated by the protocol.
The proof of the lemma is somewhat tedious and is given in Appendix B so as not to distract the
reader from the main thrust of the paper.
3 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 parties know N where
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 [36, 33] carried out in both Z
N and a quadratic extension of Z
N .
Throughout the section we are assuming that (hence the resulting
Blum integer). This can be arranged ahead of time by having party 1 pick shares
All other parties pick shares
Before describing the test we brie
y discuss the structure of the quadratic extension of Z
N we
will be using. We will be working in the twisted group
N . Suppose all
prime factors of N are 3 mod 4. In this case, x irreducible in ZN [x] and ZN
a quadratic extension of ZN . A linear polynomial
and only if gcd(; ; It follows that elements of TN can be viewed as linear polynomials
linear polynomials f; g 2 ZN [x] represent the
same element of TN if ag for some a 2 Z
N . We note that elements of TN can also be viewed
as points on the projective line over ZN .
Distributed primality test:
1: The parties agree on a random g 2 Z
N . The value g is known to all k parties.
Step 2: Party 1 computes the Jacobi symbol of g over N . If g
the protocol is restarted at
step (1) and a new random g is chosen.
Step 3: Otherwise, party 1 computes
. All other parties compute
. The parties exchange the v i values with each other and verify that
Y
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 .
To carry out the Fermat test in TN the parties pick a random h 2 TN . Party 1 computes
. The parties then exchange the u i
values with each other and verify that
Y
If the test fails N is rejected. Otherwise they declare success.
the exponents in the computation of
the v i 's (Step are guaranteed to be integers after division by 4. The correctness and privacy of
the protocol is proved in the next two lemmas.
Lemma 3.1 Let 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 1
2 (over the random choice of g and h).
Proof Observe that in step (3) of the protocol we test that v
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 g
1. This implies
. Also, since q 1and p 1are odd we have,
q 1=
(mod p)
(mod q)
Since
it follows that g (N)=4  1 mod N . Since
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
no root in F p and F q . Therefore, F p [x]=(x
and F q are quadratic extensions of F p and F q respectively. It follows that the group
p is of order p + 1. Similarly, jT q 1. By the Chinese Remainder
Theorem, 1). We conclude that all h 2 TN satisfy
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,
ds s is a
non-trivial factorization of N with
to be the exponent used in step (3). Note that e is odd since p  q  3 mod 4. Dene the following
two subgroups of Z
To prove the lemma we show that jHj  1jGj. Since H is a subgroup of G it su-ces to prove proper
containment of H in G, i.e. prove the existence of g 2 G n 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 (such a
must exist by the pigeonhole principle). 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 . Dene g 2 ZN to be an element
satisfying
a mod r 3 if
and 3. Observe that g 2 G. Since e is odd
Consequently, g e 6= 1 mod N i.e. g 62 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 Z
there exists an
element g of order r. Since r is odd we have g
G. Since
r divides both p and q we know that r does not divide N Consequently
implying that g e 6= 1 mod N . Hence, g 62 H.
Case 3. The only way does not fall into both cases above is if
1 and
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 By symmetry we may assume d 1 > 1. Since Z
p is a cyclic
group of order r d 1 1
contains an element of order r d 1 1
1 . It follows that Z
N also
contains an element g of order r d 1 1
1 . As before, g
G. If q 1 is not divisible by r d 1 1
1 . Consequently, g 4e 6= 1 mod N , i.e. g 62 H.
Case 4. We are left with the case
above and q
1 . Since we know that r 4. In this case it may
indeed happen that 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 2 TN ).
Dene the group H 1g. We show that jH 0 j  1jT N j. Since H 0
is a subgroup of TN it su-ces to prove proper containment, i.e. we must exhibit an element
1 the group T p has order r d 1 1
1). Therefore it contains an
element h of order r 1 . It follows that there exists an element w 2 TN 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 completing
the proof of the lemma.
We note that Step (4) of the protocol is needed to lter out integers that fall into Case 4 above.
Indeed, such integers will pass steps (1)-(3). For example, consider integers
and prime. For these integers we have are
as dened 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 3.1 we give an alternate approach for ltering 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 3.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
where the v i 's are dened as in
step (3) of the protocol. Also,
the u i 's are dened 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
We construct a simulator of the coalition's view as follows: the simulator is given
for (this is the coalition's input when the protocol is started). To simulate the
coalition's view, the simulator rst picks a random g 2 Z
N with g
It then computes the u using the values it is given as input. Next the
simulator must generate um Generating um is trivial since um = (
i6=m Generating v m
is a bit harder. From the proof of Lemma 3.1 it follows that
That is, the sign of v
is a quadratic residue modulo N . To simulate v m
the simulator computes
It then
ips an unbiased coin and sets v
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 hu 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.
3.1 An alternative to Step (4)
Step (4) of the distributed primality protocol is necessary to lter out integers that fall into Case 4
in the proof of Lemma 3.1. We describe an alternative simpler approach to lter out such integers.
It requires less computation, although there is more communication between the parties.
Observe that if N falls into Case 4 then 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 2 ZN and keeps it secret. Using the protocol of the next
section they compute
(mod N)
without leaking any information about the private shares . Finally, the parties check if
gcd(z; N) > 1. If so, N is rejected. Using the BGW method (Section 4.1) this approach is b k 1c
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 eliminates a few valid RSA
moduli, i.e. moduli prime and
4 Distributed computation of N
Next we describe the computation of N . Each party has a secret They wish to make the
product
revealing any information about their private shares
beyond what is revealed by the knowledge of N .
4.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:
c. For all picks two random degree l polynomials
In other words, the constant term of f
are set to p i ; q i and all other coe-cients are chosen at random in Z P . Similarly, party i picks
a random degree 2l polynomial h
Step 2: For all computes the 3k values:
Party i then privately sends the triple hp i;j ; q i;j ; h i;j i to party j for all j 6= i. Note that the
are standard l-out-of-k Shamir secret sharings of p i . The same holds for
Step 3: At this point, each party i has all of hp
Party i broadcasts N i to all other parties.
Step 4: At this point each of the parties has all values N i for be the
polynomial
Observe that by denition of f Furthermore, (x) is
a polynomial of degree 2l. We note that l is dened so that k  2l +1. Consequently, since all
parties have at least 2l 1 points on (x) they can interpolate it and discover its coe-cients.
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 b k 1
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 4.1 Given N , any coalition of b k 1c parties can simulate the transcript of the protocol.
Consequently, the protocol is b k 1c private.
Proof Sketch Set 1c. By symmetry we may assume the coalition is made up of
In what follows we consistently let the index i vary in l, the index j vary
in and the index r vary in k. Then the coalition's view consists of
To simulate the coalition's view, the simulator is given as input. It rst picks random
(j). It picks p r;i ; q r;i ; h r;i as random independent elements of Z P and computes
picks a random degree 2l polynomial (x) 2 Z P [x]
satisfying 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 diers 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 e-cient. 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 [6, Section 4].
4.2 BGW Modulo non primes
In our description of the BGW protocol all arithmetic operations were carried out modulo a prime
. 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
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 coe-cients used during the interpolation at
Step (4) exist. Lemma 4.1 remains correct.
Running the protocol modulo M containing small factors require a slight modication. Write
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 3. It is not possible to use Shamir secret sharing in F 3
among k > 3 parties since F 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 F 3 that contains more than k points. The simulation argument immediately extends
to this case. In general, one can factor M 2 into its 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 .
4.3 Sharing the nal outcome
In some cases (as in Section 6.2) we wish to have the parties evaluate the function
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
and no information is revealed about the private shares or the nal result.
The modication 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 Using Lagrange interpolation we know that
(i is the appropriate Lagrange coe-cient. Therefore, rather than broadcast
N i at the end of Step 3, party i simply sets M . 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.
5 Trial division
In this section, we consider the trial division step (Step 1b in Section 2). Let
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 2 Z p . Using the BGW protocol (as described in Section 4.1) they compute
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
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
Y
One caveat in the above approach is that the BGW protocol as described in Section 4.1 cannot
be applied to test divisibility of q by very small p, namely p  k. The reason is that for such small
p the eld F 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 eld of F p that contains at least k +1
elements, as explained in Section 4.2.
6 Shared generation of public/private keys
Once the parties successfully construct an RSA modulus
may wish to
compute shares of for a given encryption exponent e. We have two approaches
for computing shares of d. The rst only works for small e (say e < 1000) but is very e-cient
requiring very little communication between the parties. The second works for any e and is still
e-cient, but requires more communication.
Throughout the section we set Recall that the public modulus
k. For all
locally compute  i .
To compute shares of d the parties must invert e modulo
exposing their  i 's.
Unfortunately, traditional inversion algorithms, e.g. extended gcd, involve computations modulo
. We do not know how to e-ciently 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. Observe that T  0 mod e. (3) Set Indeed
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.
6.1 Small public exponent
We begin by describing an e-cient 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.
1: The parties jointly determine the value of
it is possible
to compute l without revealing any other information about the private shares. To do so we
use a simple protocol due to Benaloh [4] which is k 1 private.
Step 2: Let Each party i locally
computes:
i
e
As a result we have
Step 3: The above sharing of d enables shared decryption [20] using the equality c d  c r
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 bits.
6.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 k 1private.
Step 1. Each party picks a random r i 2 Z e .
Step 2. Using the protocol of Section 4.2 they
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
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 Z P . Using the modied BGW protocol of Section 4.3 they compute an additive sharing
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
We know that at the end of Step 4 we have
Therefore,
Given a candidate value of s 2 [0;
If the given s is correct then 0
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
To see this
observe that:
Therefore,
Each party i now sets d As a result we have
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 rst picks a random message
It then asks the parties to decrypt c. Each party computes
and sends the result to the gateway. By performing at most k multiplications the
gateway nds an r 2 [0;
It then relates the value of r back to
the parties who x 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 6.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 [21, 22]). Let picks two polynomials
as follows: the constant terms are set to f
other coe-cients are chosen at random from f0; g. By
interacting with the other parties, each party i computes a point on the polynomial (
over the integers. These points, multiplied by the appropriate Lagrange coe-cients, become the
additive sharing
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].
6.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 [34], 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.
Optimizations
We describe several practical techniques to improve the performance of our distributed protocol.
These optimizations are incorporated in an implementation of our protocol [29].
Sieving In Step (1) of our protocol (Section 2) the parties repeatedly pick a random shared integer
until they nd one that is not divisible by small primes. For this they engage in an interactive
trial division protocol. We brie
y outline a more e-cient 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 i of a random integer a in Z
M . Party i could then set its share of p to be
random number of the appropriate length to make p i be an n-bit
integer. The resulting candidate prime
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
. The only question that remains is how do the parties generate an additive sharing of a
random integer a 2 Z
To do so, each party i generates a random element b i 2 Z
M . Then
is a random element of Z
M . The parties then use the BGW method of
Section 4.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 ZM (which is not a eld).
This is done as explained in Section 4.2.
Load balancing In Step (3) of the primality test party 1 computes
while all other parties only had to compute v . Notice that N + 1 is
roughly 2n bits while 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 dierent party. This way g N+1 mod N
is computed by a dierent 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 2). 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 e-ciently done by hard-coding all primes
in the range [B 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 eectiveness of trial division.
Fermat lter There is no need to run the full primality test of Section 3 on every candidate
modulus N . Instead, one can do a Fermat test rst and proceed to perform the full test only
if the Fermat test succeeds. We refer to the test
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
and verify that
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 2 we noted that our protocols suer 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 brie
y outline a potential solution. Consider the
case of three parties, Alice, Bob and Carol. They could generate N as
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 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 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 [7] to do just that: test that a shared
modulus is the product of three primes without revealing its factorization.
8 Robustness
Throughout the paper we use a model in which parties honestly follow the protocol. This is ne
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 veriable (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 [22] showed how our protocol can be made to withstand
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 rst run,
with the other three parties by writing
4 and
are random integers in the range [0; N ]. Party 1 then sends p 0
to party i for these values to its own 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 its 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 k
c
extra invocations. The resulting computation is
private. Clearly this approach can only be applied as long as both k and c are very small.
9 Summary and open problems
We presented techniques that allow three or more parties to generate an RSA modulus
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 b k 1c 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 [7] enabling k parties to test that N is the product
of three primes, without revealing any information about the factors.
To demonstrate the eectiveness of our protocols we implemented them. Generating a 1024
bits shared RSA key among three 300MhZ Pentium machines takes 90 seconds. See [29] 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 p 1and q 1are prime) has
been considered for security purposes [27] as well as for technical reasons related to threshold
cryptography [16, 25]. Currently, our techniques do not enable shared generation of moduli of
special form. Progress in this directions would be very helpful.

Acknowledgments

We thank Don Beaver for helpful discussions on our results.



--R








"Universal classes of hash functions"



"On the number of uncanceled elements in the sieve of Eratosthenes"

























", FOCS 1986, pp. 162-167. A. Cocks' multiplication method The BGW protocol described in Section 4.1 achieves b k 1 2 c privacy and is information theoretically secure. Cocks [10] 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"
and

--TR
Strong primes are easy to find
How to play ANY mental game
How to prove yourself: practical solutions to identification and signature problems
sharing homomorphisms: keeping shares of a secret secret
A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory
Zero-knowledge proofs of identity
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Multiparty unconditionally secure protocols
The knowledge complexity of interactive proof systems
Non-cryptographic fault-tolerant computing in constant number of rounds of interaction
A modification of the Fiat-Shamir scheme
A practical protocol for large group oriented networks
Fast signature generation with a Fiat ShamirMYAMPERSANDmdash;like scheme
How to share a function securely
Robust efficient distributed RSA-key generation
How to share a secret
Two Party RSA Key Generation
Secure Computation (Abstract)
Shared Generation of Authenticators and Signatures (Extended Abstract)
Robust and Efficient Sharing of RSA Functions
A Simplified Approach to Threshold and Proactive RSA
Generation of Shared RSA Keys by Two Parties
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary
Knowledge Generation of RSA Parameters
Generating a Product of Three Primes with an Unknown Factorization
Optimal-resilience proactive public-key cryptosystems
Security, fault tolerance, and communication complexity in distributed systems

--CTR
Jaimee Brown , Juan M. Gonzalez Nieto , Colin Boyd, Efficient and secure self-escrowed public-key infrastructures, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore
Dan Boneh , Xuhua Ding , Gene Tsudik, Fine-grained control of security capabilities, ACM Transactions on Internet Technology (TOIT), v.4 n.1, p.60-82, February 2004
primality testing;threshold cryptography;RSA;multiparty computation