Generating a Product of Three Primes with
an Unknown Factorization
Dan Boneh and Jeremy Horwitz
Computer Science Department, Stanford University, Stanford, CA 94305-9045
fdabo,horwitzg@cs.stanford.edu




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. We explain the cryptographic motivation and
origin of this problem.

1 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 ZN and the twisted
multiplicative group TN = (ZN x]=(x2 + 1)) =ZN .
The main motivation for this problem comes from cryptography, speci cally
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 Certi cation
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 di erent location
avoids this single point of failure. One approach (due to Frankel 7]) is to pick
three random numbers satisfying d = d1 + d2 + d3 mod '(N) and store each of
the shares d1 d2 d3 at one of three di erent sites. To generate a signature of a
message M, site i computes Si = M di mod N for i = 1 2 3 and sends the result
to a combiner. The combiner multiplies the Si and obtains the signature S =
S1 S2 S3 = 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 modi es 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 Certi cation 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 14] 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 9] 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 d1 d2 d3 ? Previously the answer
was a trusted dealer would generate N and distribute the shares d1 d2 d3 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 2] designed a protocol that enables three (or more) parties to jointly
generate an RSA modulus N = pq and shares d1 d2 d3 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 d1 d2 d3 and has no computational information
about the other shares. Thus, there is no need for a trusted dealer. We note
that Cocks 5] introduced a heuristic protocol enabling two parties to generate
a shared RSA key.
In this paper we design an e cient 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 2] can be used to generate
shares d1 d2 d3 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 2] do not generalize to generate
a modulus with three prime factors and new techniques had to be developed for
this purpose. Our main results are described in Section 4
We remark that techniques of secure circuit evaluation 1, 4, 16] can also be
used to solve this problem however, these protocols are mostly theoretical and
result in extremely ine cient algorithms.

2 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 e ciency of shared generation of RSA keys. To understand
this we must brie y recall the method used by Boneh and Franklin 2]. 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 pa qa, Bob picks two random
n bit integers pb qb and Carol picks two random n bit integers pc qc . They
keep these values secret.
Step 2. Using a private distributed computation they compute the value
N = (pa + pb + pc )(qa + qb + qc ):
At the end of the computation, N is publicly available however no other in-
formation 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 primal-
ity test which is one of the main contributions of 2]. Step (2) is achieved using
an e cient variation of the BGW 1] protocol.
A drawback of the above approach is that both factors of N are simulta-
neously tested for primality. Hence, the expected number of times step (3) is
executed is O(n2 ). This is much worse than single-user generation of N where
the two primes are rst generated separately by testing O(n) candidates and
then multiplied together. When generating a 1024-bit modulus, this results in
signi cant slowdown when compared with single-user generation.
To combat this quadratic slowdown, one may try the following alternate ap-
proach.
Step 1. Alice picks a random n-bit prime p and a random n-bit integer ra. Bob
picks a random n-bit prime q and a random n-bit integer rb . Carol picks a
random n-bit integer rc . They keep these values secret.
Step 2. Using a private distributed computation they compute the value
N = pq(ra + rb + rc )
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 su er from the quadratic slowdown observed in
the previous method. Consequently, it is faster by roughly a factor of 50 (after
taking e ects of trial division into account). As before, step (2) is carried out by
an e cient variant of the BGW protocol.
Instead of solving the speci c problem of testing that N = pq(ra + rb + rc )
is a product of three primes we solve the more general problem of testing that
N = (pa + pb + pc)(qa + qb + qc)(ra + rb + rc )
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 cryp-
tography 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 Theo-
rem (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 15] becomes less e ective 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 12] cannot take advantage of the fact
that the factors of N = pqr are smaller than those of a standard RSA modulus
N = pq.

3 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 rst reading, the reader may wish to skip to
Section 4 and take on faith that the necessary setup is attainable.

3.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 pro-
tocol. This is indeed the case when they are truly trying to create a shared
key. This assumption is used by both 2] and 5]. We note that some recent
work 8] makes the protocol of 2] 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
ne 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
b k;1 c-privacy. That is, any minority of parties learns no information about
2
the factors of N.

3.2 Generation of N


In the previous section, we explained that Alice, Bob, and Carol generate N as
N = (pa + pb + pc )(qa + qb + qc )(ra + rb + rc )
where party i knows pi qi ri for i = a b c and keeps these shares secret while
making N publicly available. To compute N without revealing any other infor-
mation about the private shares, we use the BGW protocol 1]. For the particular
function above, the protocol is quite e cient it requires three rounds of commu-
nication and a total of six messages. The protocol is information-theoretically
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 su ces 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
pa + pb + pc = qa + qb + qc = ra + rb + rc = 3 mod 4. Hence, the parties must
coordinate 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 signi cant bits of the other's shares.

3.3 Sharing of (p ; 1)(q ; 1)(r ; 1) and (p + 1)(q + 1)(r + 1)
Let p = pa + pb + pc, q = qa + qb + qc , and r = ra + rb + rc . We de ne
' = (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 su ces 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+pa +qa +ra ;1 'b = ;B+pb +qb +rb 'c = ;C+pc +qc +rc :
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 nal result public the BGW variant shares the result additively among the
three parties. The details of this variant can be found in 2, 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,
we 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
= N +A+pa +qa +ra +1 = B+pb +qb +rb = C +pc +qc +rc :
a b c


3.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 2 ZN . 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 C1 2 ZN and sets C2 = CC1;1 mod N.
Clearly C = C1 C2 mod N. Carol then sends C1 to Alice and C2 to Bob.
Step 2. Alice sets A0 = AC1 and Bob sets B0 = (BC2 );1 mod N. Both values
A0 and B 0 can be viewed as integers in the range 0 N). The problem is now
reduced to testing whether A0 = B 0 (as integers) without revealing any other
information about A and B.
Step 3. Alice picks a random c 2 ZP and d 2 ZP . She sends c and d to Bob.
Alice then computes h(A0 ) = cA0 + d mod P and sends the result to Carol.
Bob computes h(B 0 ) = cB 0 + d mod P and sends the result to Carol.
Step 4. Carol tests if h(A0 ) = h(B0 ) mod P. If so, she announces that ABC =
1 mod N. Otherwise she announces ABC 6= 1 mod N.
The correctness and privacy of the protocol are stated in the next two lem-
mata. Correctness is elementary and is stated without proof.
Lemma 1. Let A B C 2 ZN. At the end of the protocol, the parties correctly
6
determine if ABC = 1 mod N or ABC = 1 mod N.
Lemma 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, C1 , c, d, h(A0 ), and the nal result of the test. These values can be
easily simulated by picking C1 at random in ZN , picking c at random in ZP and
d at random in ZP . 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, C1 ,
C2 , h(A0 ), h(B 0 ), and the result of the test. The key observation we make is
that h(A0 ) and h(B 0 ) reveal no information about A and B, since they are either
equal or are random independent elements of ZP . 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 2 ZP ).
To simulate Carol's view, the simulator picks C1 C2 2 ZN at random so that
C = C1 C2 mod N. Then, depending on the results of the test, it either picks the
same random element of ZP twice or picks two random independent elements
of ZP . 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
u
t
can generate the values sent by Alice and Bob herself.

4 The Probabilistic Primality Test
We are ready to describe our main result, the probabilistic 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 pi , qi , and ri for i = a b c.
The modulus N = (pa + pb + pc)(qa + qb + qc)(ra + rb + rc) is public. We set
p = pa + pb + pc , q = qa + qb + qc , and r = ra + rb + rc . Throughout this
section, we are assuming that p = q = r = 3 mod 4. Thus, the parties must
a priori coordinate the two least signi cant 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. In the subsequent subsections, we
explain how each of these steps is carried out without revealing any information
about the factors of N.
Probabilistic test that N is a product of three primes:
Step 1. The parties pick a random g 2 ZN 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
ZN (see Section 4.2 for details).
Step 2. The parties perform a Fermat test in the twisted group TN de ned as
(ZN x]=(x2 + 1)) =ZN . Notice that x2 + 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 TN is (N) =
(p + 1)(q + 1)(r + 1). To carry out the Fermat test in TN , the parties pick
a random g 2 TN and jointly test that g a+ b + c = 1 (see Section 4.2 for
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 Section 4.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 Section 4.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 TN = (ZN x]=(x2 + 1)) =ZN is
helpful in the proof of the primality test.
Fact 1. Let N be an integer and k a prime such that k2 N. Then, k divides
both '(N) and jTN j.
2 be the number of times k divides N, i.e. N = k w where
Proof. Let
gcd(k w) = 1. Then '(N) = k ;1 (k ; 1)'(w) and, hence, k divides '(N).
To see that k divides jTN j, note that TN = Tk Tw . When k = 3 mod 4,
we know that x2 + 1 is irreducible in Zk and, hence, jTk j = k ;1 (k + 1). It
follows that k divides jTN j. When k = 1 mod 4, we have jTk j = k ;1 (k ; 1)
and, again, k divides jTN j. t
u
We can now prove that the aforementioned four steps are indeed a proba-
bilistic test for proving that N is a product of three primes.
Theorem 2. Let N = pqr = (pa + pb + pc)(qa + qb + qc)(ra + rb + rc), 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 = z1 1 z2 2 z3 3 for three primes z1 , z2 , and z3 (not necessarily distinct).
Since N passes step (4) we know gcd(N p + q + r) = 1. De ne the following two
groups:
G = g 2 ZN g'a +'b +'c = 1 and
H = g 2 TN g a + b + c = 1 :
Clearly, G is a subgroup of ZN and H is a subgroup of the twisted group TN .
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 k2 N. Hence, by Fact 1, k '(N) and k jTN j.
We claim that either k does not divide ' or k does not divide ^. To see this,
^
^, then k divides ^ ; ' = p(2q + 2r) + q(2r) + 2.
observe that if k ' and k
^ ^
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 2 ZN of order k. However, since k does not
divide ' we know that g' 6= 1. Hence, g 62 G proving that G is a proper
^
^
subgroup of ZN . If k does not divide ^ a similar argument proves that H is
a proper subgroup of the twisted group TN .
Case 2: p, q, and r are pairwise relatively prime. We can write p = z1 , q = z2 ,
and r = z3 with z1 , z2 , and z3 distinct primes. By assumption, we know
that one of , , or is greater than 1. Without loss of generality, we may
assume > 1.
We rst observe that none of the zi can divide gcd(' ^). Indeed, if this
^
^ = 2(N + p + q + r). But
were not the case, then zi would divide ' + ^
then, since zi 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 z1 does not divide ' or it does not divide ^.
^
2 divides N, we obtain, by Fact 1, that z1 '(N) and z1 jTN j.
However, since z1
We can now proceed as in case (1) to prove that either G is a proper subgroup
of ZN or H is a proper subgroup of TN .
t
u
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 = w3 ,
q = aw2 + 1, and r = bw2 ; 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.

4.1 Step 3: Testing that =
N pqr


Our protocol for testing that N is a product of three prime powers borrows from
a result of van de Graaf and Peralta 11]. 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 a1 a2 2 Z8 such
that a1 + a2 = 'a mod 8. She sends a1 to Bob and a2 to Carol. Alice sets
'a 'a ; a1 ; a2 , Bob sets 'b 'b + a1 and Carol set 'c 'c + a2 .
Observe that, at this point,
' = 'a + j 'b k + l 'c m :
^
88 8 8
Step 1. The parties rst agree on eight random numbers g1 g2 : : : g8 in ZN,
all with Jacobi symbol +1.
Step 2. For i j 2 f1 2 : : : 8g, we say that i is equivalent to j (this de nes
equivalence classes of f1 2 : : : 8g) if
'a +'b +'c
gi 8
= 1 (mod N):
gj
Since all three parties know gi and gj , they can test if i is equivalent to j as
follows:
1. Alice computes A = (gi =gj )'a =8 mod N,
Bob computes B = (gi =gj )b'b =8c mod N, and
Carol computes C = (gi =gj )d'c =8e mod N.
2. Using the comparison protocol of Section 3.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 gi with Jacobi symbol +1 for e ciency'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 neces-
sary.
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:
g = +1o
n
J = g 2 ZN N
Q = g 2 J g is a quadratic residue in ZN
The index of Q in J is 2d(N);1 or 2d(N) (exactly when N is a perfect square),
where d(N) is the number of distinct prime factors of N.
Lemma 1. 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 g1 g2 2 ZN belong to the same coset of Q in J if and only if
g1 =g2 is a quadratic residue, i.e. if and only if (g1 =g2)'(N)=8 = 1 mod N. Since,
in this case, '(N) = ' = 'a + 'b + 'c , step (2) tests if gi and gj 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. De ne
n o
^
Q = g 2 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
^ ^
if g 2 J satis es 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 g1 g2 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 gi 2 J chosen randomly in step (1) fall into only four
of the eight cosets. Then
1 8 0:27 < 1 :
8
Pr R] 4 2 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. u
t
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 3]) 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 de ned
above. In other words, for any polynomial time algorithm A and any constant
c > 0,
Pr A(g) = \yes"] ; g2Q A(g) = \yes"] < (log1N)c :
Pr
g2J

Lemma 2. 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 g1 g2 : : : g8
and bit values bi j indicating whether (gi =gj )' = 1 (recall that we already gave
^
a simulation algorithm for the comparison protocol in Section 3.4). Thus, Alice
learns whether or not each gi =gj 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 g1 g2 : : : g8 2 J. It then randomly associates with each gi
a value in the set f0 1 2 3g. This value represents the coset of Q in which gi
lies. The simulator then says that gi =gj is a quadratic residue if and only if
the value associated with gi is equal to that associated with gj . Under QRI,
the resulting distribution on g1 g2 : : : g8 b1 1 b1 2 : : : b8 8 is computationally
indistinguishable from Alice's true view of the protocol.
We note that the value a1 2 Z8 that Alice sends Bob in step (0) is an element
of Z8 chosen uniformly at random. Hence, Bob can simulate it trivially. Similarly,
Carol can trivially simulate a2 2 Z8. u
t
4.2 Implementing a Fermat Test with No Information Leakage
We brie y show how to implement a Fermat test in ZN without leaking any
extra information about the private shares. The exact same method works in
the twisted group TN as well.
To check that g 2 ZN satis es g'a+'b +'c = 1 mod N, we perform the following
steps:
Step 1. Each party computes Ri = g'i mod N (i = a b c).
Step 2. They test that RaRb Rc = 1 mod N by simply revealing the values R1,
R2 , and R3 . 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 3. 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 re-
^
strict 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 com-
putes Rc = 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
t
u
it themselves.

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


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 ya 2 ZN, Bob picks a random yb 2 ZN, and Carol
picks a random yc 2 ZN .
Step 2. Using the BGW protocol as in Section 3.2, they compute
R = (pa + qa + ra + pb + qb + rb + pc + qc + rc )(ya + yb + yc ) mod N:
At the end of the protocol, R is publicly known however, no other informa-
tion 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 4. 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=2n;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 ya +
yb + yc) > 1. Since ya + yb + yc is a random element of ZN , this happens with
u
t
probability less than (1=2)n;3 .
Lemma 5. 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 1-private. By symmetry, we need only show how to simulate Alice's
view. Alice's view consists of her private shares pa , qa , ya and the number R.
Since R is independent of her private shares, the simulator can simulate Alice's
t
u
view by simply picking R in ZN at random. This is a perfect simulation.
5 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 fac-
torization. Second, one may wish to design primality tests for testing that N is a
product of k primes for some small k. We brie y discuss both extensions below.
Our protocols easily generalize to allow any number of parties. When k parties
are involved, the protocols can be made b k;1 c-private. This is optimal in the
2
information-theoretic sense and follows from the privacy properties of the BGW
protocol. The only complexities in this extension are the comparison protocol of
Section 3.4 and Step (0) of Section 4.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 xed k > 3 seems to
be harder. Our results apply when k = 4 (indeed Theorem 2 remains true in this
case). For k > 4, more complex algorithms are necessary. This extension may
not be of signi cant 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 5].


6 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 di erent subgroups
of ZN x]=(x2 + 1) , namely ZN and the twisted multiplicative group TN . Our
protocol generalizes to an arbitrary number of parties k and achieves b k;1 c-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 modi cations enable one to apply the test
when p = q = r = 1 mod 4 (essentially, this is done by reversing the roles of
ZN 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 1.
A natural question to ask is whether more advanced primality testing tech-
niques can be used to improve the e ciency of our test. For instance, recent
elegant techniques due to Grantham 10] may be applicable in our scenario as
well.
References
1. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-
cryptographic fault tolerant distributed computation. In Proceedings of the 20th
Annual ACM Symposium on Theory of Computing, pages 1{10. ACM Press, 1988.
2. D. Boneh and M. Franklin. E cient generation of shared RSA keys. In Proceedings of
Advances in Cryptology: CRYPTO '97, pages 425{439. Lecture Notes in Computer
Science, Springer-Verlag, New York, 1998.
3. M. Blum and S. Goldwasser. An e cient 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.
4. D. Chaum, C. Crepeau, and I. Damgard. Multiparty unconditionally secure proto-
cols. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing,
pages 11{19. ACM Press, 1988.
5. C. Cocks. Split knowledge generation of RSA parameters. Available from the author
(cliff cocks@cesg.gov.uk).
6. R. Fagin, M. Naor, and P. Winkler. Comparing information without leaking it.
Communications of the ACM, 39(5):77{85, May 1996.
7. Y. Frankel. A practical protocol for large group oriented networks. In Proceedings
of Advances in Cryptology: EUROCRYPT '88, pages 56{61. Lecture Notes in Com-
puter Science, Springer-Verlag, New York, 1990.
8. Y. Frankel, P. MacKenzie, and M. Yung. Robust e cient distributed RSA key gen-
eration. Preprint.
9. P. Gemmel. An introduction to threshold cryptography. CryptoBytes (a technical
newsletter of RSA Laboratories), 2(7), 1997.
10. J. Grantham. A probable prime test with high con dence. Available online
(http://www.clark.net/pub/grantham/pseudo/).
11. 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.
12. A. Lenstra and H. W. Lenstra ed. The development of the number eld sieve.
Lecture Notes in Computer Science 1554, Springer-Verlag, 1994.
13. H. W. Lenstra. Factoring integers with elliptic curves. Annals of Mathematics,
126:649{673, 1987.
14. A. Shamir. How to share a secret. Communications of the ACM, 22(11):612{613,
November 1979.
15. M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on
Information Theory, 36(3):553-558, 1990.
16. A. Yao. How to generate and exchange secrets. In Proceedings of the 27th Annual
ACM Symposium on Theory of Computing, pages 162{167. IEEE Press, 1986.