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.