Paillier\'s cryptosystem revisited

Paillier’s Cryptosystem Revisited 

Dario Catalano

Universita´ di Catania Catania, Italy

[email protected]

Rosario Gennaro Nick Howgrave-Graham

Phong Q. Nguyen

IBM Research Yorktown Heights, NY, USA

´ Ecole normale superieure ´ Paris, France

frosario,nahggwatson.ibm. om

ABSTRACT We re-examine Paillier's ryptosystem, and show that by

hoosing a parti ular dis rete log base g , and by introdu ing an alternative de ryption pro edure, we an extend the s heme to allow an arbitrary exponent e instead of N . The use of low exponents substantially in reases the eÆ ien y of the s heme. The semanti se urity is now based on a new de isional assumption, namely the hardness of de iding whether an element is a \small" e-th residue modulo N 2 . We also show how to use Paillier's original ryptosystem to build a trapdoor ommitment s heme. This new s heme is information-theoreti ally private, and omputationally binding (this property holds under the assumption that the RSA fun tion with exponent N is hard to invert). A novel property of this new ommitment s heme is that most of the work an be done oine before knowing the message one wants to ommit to. On e the message is known only two multipli ations are required. This is the rst trapdoor ommitment s heme with this online-oine eÆ ien y property whi h is also length-preserving.

1. INTRODUCTION Paillier's ryptosystem [28℄ is the latest member of a family of publi -key probabilisti en ryption s hemes [17, 7, 1, 25, 27, 28℄ based on a dis rete log trapdoor modulo a large integer hard to fa tor. In su h s hemes, the message spa e is a ring M of modular residues and iphertexts are in the group G (denoted multipli atively) of invertible elements of some parti ular ring of integers modulo a number hard to fa tor. The en ryption of a message m is always a group element of the form E (m; r) = g m re 2 G where e is some publi integer, g some xed publi element in

Work done while visiting the IBM T.J. Watson Resear h Center

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission by the authors. CCS’01, November 5-8, 2001, Philadelphia, Pennsylvania, USA. Copyright by the authors.

[email protected]

G , and r is hosen at random in some parti ular multipli ative subgroup R of G . Sin e R is a subgroup, su h

s hemes have an additive homomorphi property: an en ryption of m1 + m2 an be obtained from any en ryption of m1 and m2 , as E (m1 ; r1 )E (m2 ; r2 )  E (m1 +m2 ; r1 r2 ). This property is very useful in the ontext of ele troni voting (see [1, 13, 11℄), veri able en ryption (see [30, 13℄) and threshold s hemes (see [11, 14℄). Interestingly, those s hemes turn out to be easily proved semanti ally se ure under appropriate assumptions (usually stronger than fa toring). This family began seventeen years ago with Goldwasser and Mi ali [17℄ when they introdu ed the notion of probabilisti en ryption. We denote by Zn the ring of integers modulo n, and by Zn the orresponding group of invertible elements, whose order is Euler's fun tion (n) and whose exponent is Carmi hael's fun tion (n). The Goldwasser-Mi ali s heme [17℄ is based on quadrati residues: it sele ts M = Z2, G = R = ZN where N = pq is an RSA-type modulus, e = 2 and the base g as a pseudosquare modulo N . The semanti se urity follows from the quadrati residuosity assumption. The Benaloh-Fis her s heme [1, 7℄ later improved the very limited bandwidth of the Goldwasser-Mi ali s heme by using higher-order residues: it uses the same groups G = R = ZN where N = pq is a produ t of two large primes, but this time, M = 2Ze, e is a small prime number dividing (N ) su h that e does not divide (N ), and g is a non e-th residue modulo N . The semanti se urity is proved under the prime residuosity assumption. However, the de ryption is ineÆ ient as it applies some kind of exhaustive sear h, implying that e must be very small. In 1998, Na

a he and Stern [25℄ proposed a variant of the Benaloh-Fis her s heme whi h allows high bandwidth. This is a hieved by taking e not as a prime but as a produ t of small primes e1 ; : : : ; ep su h that (N ) is divisible by e but by none of the e2i 's, and g is non ei -th residue modulo N , for all i. The semanti se urity is still proved under the prime residuosity assumption. At the same time, Okamoto and U hiyama [27℄ proposed a very dierent improvement of the Benaloh-Fis her s heme by hanging of group stru ture. They sele ted G = R = ZN with N = p2 q instead of N = pq as in Goldwasser-Mi ali, Benaloh-Fis her and Na

a he-Stern, and they use M = Zp, e = N and g su h that the order of g p modulo p2 is p. They showed that if the s heme

is not one-way, one an fa tor N . The semanti se urity is proved under the p-subgroup assumption, but unfortunately there exist very simple hosen- iphertext atta ks that an re over the fa torization of N . The s heme rea hes bandwidths similar to Na

a he-Stern, however the de ryption is more eÆ ient. Paillier re ently proposed in [28℄ an extension of the Okamoto-U hiyama s heme where N is an usual RSAmodulus and working in a dierent group. More pre isely, N = pq , M = ZN , G = ZN 2 , R = ZN , e = N and g is an element of order divisible by N . The semanti se urity is proved under the de isional omposite residuosity assumption: Given N = pq , it is hard to de ide whether an element in ZN 2 is an N -th power of an element in ZN 2. The resulting system is more eÆ ient than the previously mentioned s hemes. Besides, no adaptive hosen iphertext atta ks re overing the se ret key is known. For those reasons, Paillier's ryptosystem is urrently the best

andidate of a ryptosystem with additive homomorphy.

1.1 Our results Better Effi ien y in Paillier's S heme. The main drawba k of Paillier's ryptosystem is its ost. The ost of both en ryption and de ryption is essentially that of one exponentiation in ZN 2 with exponent roughly N (the produ t of two exponentiations in the en ryption an be done in roughly the same time as one exponentiation). Sin e the semanti se urity does not depend on g , one

an hoose any g su h as one improving performan es. Paillier suggested g = 2 in [28℄, but it makes more sense to sele t g = 1 + N as noti ed in [11℄. Indeed, 1 + N has order N , and for all m, (1+ N )m  1+ mN mod N 2 . But this does not really ae t the omplexities of en ryption or de ryption in the original Paillier s heme: we still have to perform one modular exponentiation in ZN 2 for both en ryption and de ryption. The main ontribution of this paper is the remark that the hoi e of 1 + N has a very interesting advantage over an arbitrary hoi e of g : it enables an alternative de ryption pro ess (as eÆ ient as the original de ryption pro ess, and perhaps more natural) whi h in turn enables to

hoose freely the exponent e, instead of e = N . The alternative de ryption pro ess onsists of looking at the iphertext  rN (1+mN ) mod N 2 , modulo N . This yields

 rN mod N , whi h by an RSA de ryption (modulo N , with publi exponent N ) dis loses r. Putting r in the original iphertext equation provides the original plaintext m. From this des ription, it is lear that we ould have hosen any e oprime to (N ) in the en ryption and de ryption, and not just e = N as in the original Paillier s heme. The situation is reminis ent of the history of the RSA ryptosystem. Indeed, it is now publi ly known that resear hers working for the British Government had se retly dis overed RSA with publi exponent N before the invention of the RSA ryptosystem (with any exponent); see [6℄ for a ni e a

ount of this. Naturally, the semanti se urity of the new s heme an be proven under a new de isional assumption, namely the de isional small residuosity assumption: Given N = pq , it is hard to de ide whether an element in ZN 2 is an e-th power of an element in f0; : : : ; N 1g (modulo N 2 ). We

thoroughly analyze the se urity of this new assumption. The drawba k of this improvement in eÆ ien y is that the new s heme loses some interesting properties of Paillier's original ryptosystem. For example our new s heme is not additively homomorphi in general. We also ompare a modi ed variant of our s heme, semanti ally se ure under the same assumptions, to the s heme proposed by Point heval in [29℄. We observe that our new s heme is

onsiderably more eÆ ient in en ryption and almost identi al in de ryption times. With regards to Paillier's original s heme, we also show how to build a new trapdoor ommitment s heme whi h is information theoreti ally private, and omputationally binding. The latter property holds under the assumption that the RSA fun tion with exponent N is hard to invert. A novel property of this new ommitment s heme is that most of the work an be done oine before knowing the message one wants to ommit to. On e the message is known only two multipli ations are required. To our knowledge, this is the rst trapdoor ommitment s heme with this online-oine eÆ ien y property whi h is also length-preserving. The main appli ation is in the area of

hameleon signatures (introdu ed in [23℄). A New Trapdoor Commitment S heme.

2. PRELIMINARIES Notation. In the following we denote with N the set of natural numbers and with R+ the set of positive real numbers. We say that a fun tion negl : N ! R+ is negligible i for every polynomial P (n) there exists a n0 2 N s.t. for all n > n0 , negl(n)  1=P (n). We denote with PRIMES (k) the set of primes of length k. If A is a set, then a A indi ates the pro ess of sele ting a at random and uniformly over A (whi h in parti ular assumes that A an be sampled eÆ iently). If N is an RSA modulus (i.e. N = pq with p; q primes), then we denote with RSA[N; e℄ the RSA fun tion with exponent e. Paillier's S heme. Let N = pq be an RSA modulus and onsider the multipli ative group ZN 2 . Let g be an element of order at least N in ZN 2 . Paillier [28℄ onsiders the following fun tion

Fg : ZN  ZN ! ZN 2

Fg (r; m) = rN gm mod N 2 Paillier in [28℄ proves the following statements:





The fun tion Fg is a trapdoor permutation. The trapdoor information is the fa torization of N . Inverting Fg is equivalent to inverting RSA[N; N ℄.

The en ryption s heme Er (m) = Fg (r; m) (i.e. r is the randomness and m is the message) is semanti ally se ure under the N -residuosity assumption (see below).

The N -residuosity assumption informally says that given a random element in ZN 2 we are not able to dete t if it is an N -residue or not.

3. OUR NEW SCHEME The rst thing to noti e in Paillier's s heme is that one

an set g = 1 + N , sin e the order of this element in ZN 2 is exa tly N . But on e we set g = 1 + N it be omes apparent that there is no need to limit ourselves to the exponent N in the rst argument of the fun tion F . This led us to the following de nition. For a random e 2 ZN su h that g d(e; (N 2 )) = 1 we de ne the following fun tion

Ee : ZN  ZN ! ZN 2

Ee (r; m) = re (1 + mN ) mod N 2 Noti e rst of all that this modi ation greatly improves the eÆ ien y of the s heme, sin e now we an use e 2) s.t. g: :d(e; (N 2 )) = 1; 7 6 e ZN means that it is also polynomially indistinguishable, i.e. 7 = negl ( n ) Pr 6 5 4 x ZN ; y xe mod N 2 ; for every two messages m0 and m1 (m0 6= m1 ), it is not A(N; y) = x possible to eÆ iently distinguish between en ryptions of m0 and en ryptions of m1 . In parti ular onsider the ase Note that we are onje turing assumption 3.1 to hold for in whi h m0 = 0 and m1 = 1. An en ryption of m0 is every e > 2. We dis uss the se urity of this assumption

0 = r0e mod N 2 in Se tion 4. For now let us show how to use it to prove the se urity of our s heme. with r0 2 ZN . On the other hand an en ryption of m1 is

Lemma 3.1. Under Assumption 3.1 the fun tion Ee is a trapdoor permutation. The trapdoor information is the fa torization of N . e Proof. Ee is learly a permutation sin e if r (1+mN ) = e 2  (1 + N ) mod N , we an take this equation modulo N and obtain that r =  (sin e r;  < N ). This implies m = . The above observation also shows how to invert Ee , when given the fa torization of N . Given = Ee (r; m) one obtain r = ( mod N )1=e mod N and then m a

ordingly. The above also shows how to invert Ee given an ora le for RSA[N; e℄. Now it is very easy to see how to solve the small eroot problem when given an ora le that inverts Ee . Given y = xe mod N 2 where x 2 ZN simply sets = y (1 + mN ) for a random m and give it to the ora le that inverts Ee .

It is well known that a trapdoor fun tion is not readily usable for en ryption, sin e it may leak partial information A Semanti ally Se ure En ryption S heme.

given by

1 = r1e + r1e N mod N 2 with r1 2 ZN . Observe that 0 is a small e-residue modulo N 2 and 1 is not. This is be ause Ee is a permutation.

As a matter of fa t, sin e every en ryption of zero is a small e-residue, assuming 1 a small residue would imply that it has to be su h that 1 = r0 e1 mod N 2 for some r0 1 2 ZN . In su h a ase 1 would have two dierent preimages thus ontradi ting the fa t that Ee is a permutation. Consequently semanti se urity implies that the de isional small e-residuosity problem is intra table (i.e. Assumption 3.2). Conversely, assume, for the sake of ontradi tion that the s heme is not semanti ally se ure. This means that there exists a probabilisti polynomial time adversary T that su

eeds in the following game with non-negligible probability. T arbitrarily hooses two messages m0 and m1 and asks an en ryption ora le to produ e the iphertext , from

either m0 or m1 . The en ryption ora le works as follows. He hooses a random bit b and en rypts mb . Then he sends the orresponding iphertext to T . We say that T su

eeds, if given , he an eÆ iently de ide if is either an en ryption of m0 or an en ryption of m1 with non negligible probability. Now we want to onstru t a probabilisti polynomial time algorithm D (a de ider) for the small residuosity problem. D re eives as input a value z and it is supposed to de ide if z is a small residue or not. In parti ular z

ould be either a small residue modulo N 2 or a random element in ZN 2 . The idea of the proof is that D works as an en ryption ora le for T and a

ordingly to T 's response de ides if z is a small residue or not. More pre isely D, works as follows

D(z; m0 ; m1 )

1. 2. 3. 4. 5.

hoose b at random in f0; 1g z (1 + mb N ) mod N 2 0 let b be T 's response on input if b0 = b output YES else output no

The underlying idea of the above algorithm is that if z is a small residue the obtained iphertext is a valid iphertext for mb . In this ase we know that T has a non negligible advantage in guessing b. On the other hand if z is a random element, is an invalid iphertext and T annot guess b better than at random. More pre isely, being z a random element in ZN 2 , it an be written as

z = (r0 )e (1 + s0 N ) mod N for r0 2R ZN and s0 2R ZN . Thus it is possible to write as

= (r0 )e (1 + (s0 + mb mod N )N ) mod N 2

Note that, in the above relation, s0 hides mb perfe tly and thus T annot guess b better than at random.

4. SECURITY ANALYSIS In this se tion we give eviden e as to why one should

onsider the \small roots assumption" se ure, at least in its omputational setting. Sin e this is a new assumption, we are not able to redu e it to another supposedly hard problem (su h as fa toring), but rather we explain that this problem has been dire tly studied in the literature, and summarize the best known atta ks for it (showing their inability to break our system). The problem of nding small solutions of low degree modular polynomials was rst looked at (in a disguised form) by H astad in [20℄, and then later by Vallee, Girault and ToÆn in [31℄. However in both of these works, the full power of latti e redu tion te hniques was not utilized. A breakthrough was obtained by Coppersmith in [9℄: he proved that, given a polynomial p of degree d su h that the g d of its oeÆ ients is oprime with N , all x0 su h that p(x0 ) = 0 mod N and jx0 j < N 1=d an be found in time polynomial in log N and d (using latti e redu tion te hniques).

Coppersmith's result sparked a lot of resear h in the

ommunity, in various dierent dire tions, see for example [22, 3, 4, 21, 8, 26℄, however no improvement to the the bound of N 1=d has been made. In fa t, there are examples of omposite moduli N (see [8℄) for whi h the te hnique, as it stands, annot hope to be improved on (be ause there are exponentially many solutions, see [26℄). In [8℄, Coppersmith explains that this does not ne essarily mean that the bound annot be improved on for spe i moduli N , indeed it may even be possible to improve on the bound for all the moduli not in this ex eptional set. However, on the ounter side, there is no eviden e to suggest su h algorithms exist when the fa torization remains unknown, despite undoubted resear h in to this area. This is true even when the fa torization has a spe ial form; as in our ase of a perfe t square. One way to look on Coppersmith's result is the following. Given a polynomial xd = mod N , we an nd a solution x0 if it is parti ularly small, sin e it will not \wrap around" modulo N . More expli itly if we are assured that jx0 j < N 1=d then = xd0 over the integers, so all we need do is al ulate x0 = 1=d to nd x. Coppersmith's result is a generalization to all polynomials of degree d su h that the g d is oprime with N . There is at present no algorithm that will solve the problem in polynomial time up to the bound N 1=d+Æ , when the fa torization of N is unknown. It is interesting to noti e that the se urity of the Mi aliS hnorr pseudorandom bit generator based on RSA [24℄ is

losely related to this apparent diÆ ulty. More pre isely, this generator is se ure under the following assumption: the distribution xe modulo N for random r-bit sequen es x (where r = n bn(1 2=e) and n is the bit-length of N ) is indistinguishable by all polynomial-time statisti al tests from the uniform distribution of integers in the interval [0; N 1℄. We will now be expli it about the impli ations of Coppersmith's bound on our Assumption 3.1. To break this assumption we must nd an x < N given w = xe mod N 2 . Coppersmith's result states that this is possible, in polynomial time, for all jxj < (N 2 )1=e = N 2=e . Thus when jxj < N the problem appears to require exponential work for all e > 2, where the te hnique used is to enumerate through the top bits of x leaving just (1=e + ") log2 N of the bottom bits for Coppersmith's theorem to dis over. Thus for any e > 2 our assumption appears to be valid, e.g. even for e = 3 we require (N 2 )1=2 1=3 = N 1=3 work. Although this analysis does not identify a strong weakness with exponent 3, we still re ommended that one use e = 216 + 1, sin e exponentiation is still relatively heap in this ase, but the omputational problem seems ompletely intra table. Regarding Assumption 3.2, we assume that the de isional problem is not substantially easier to solve than its omputational version. Although this is ommon in this area of ryptography, we emphasize that it is a \big leap of faith". The urrent state of ryptanalyti resear h however does not seem to endanger this assumption. It would be extremely interesting to know exa tly how valid the de isional assumption is.

5. A CONNECTION WITH POINTCHEVAL’S ENCRYPTION SCHEME In this se tion we highlight an interesting onne tion between our en ryption s heme and the s heme proposed by Point heval in [29℄. The goal is (still) to show that our modi ed s heme is semanti ally se ure, but we an use a proof te hnique similar to Point heval. Thus this work highlights an essential dieren e between the two s hemes, namely the diering underlying mathemati al assumptions that are used. We start by abstra ting the ideas given in [29℄. Let f () be a trapdoor one-way fun tion and g () be another fun tion with the following pseudo-randomness property: the distribution of (f (k); g (k)) indu ed by a random k annot be distinguished (by a polynomially bounded adversary) from a randomly distributed pair (f (k); r). Then the en ryption E (m) = (f (k); g (k)  m) is semanti ally se ure. Essentially this follows be ause one may use the advantage of an adversary in guessing between the en ryption of two messages m0 and m1 , to give oneself an advantage in guessing between the distributions (f (k); r) and (f (k); g (k)) by en rypting mi using the given distribution, and seeing if i is returned. Given the above statement, the tri k is to nd an f () and g () whi h satisfy the above properties, at least under the assumption of a believable hard mathemati al problem. In [29℄ Point heval uses the pair f (k) = ke mod N and g (k) = (k + 1)e mod N and rather than use the  of the above theorem, he uses multipli ation in ZN . He

ites the work of [10℄ to suggest that this is a hard mathemati al problem (at least in the omputational setting) when e is suÆ iently large. Our s heme does not immediately seem to be in a format amenable to this te hnique, however we an modify it slightly to t the mould. For any r < N , let ra and rb be su h that re = ra + rb N mod N 2 . To en rypt a message m 2 ZN with randomness r 2 ZN we ompute Er (m) = (ra ; rb m). Clearly distinguishing (ra ; rb ) from random is equivalent to distinguishing re , for r < N from a random element in ZN 2 , and this is our original assumption. Thus it follows from Point heval's reasoning, that this too is a semanti ally se ure en ryption s heme. We brie y onsider the eÆ ien y issues between our s heme, and that of Point heval. In order for Point heval to partially justify that the distribution (re mod N; (r + 1)e mod N ) is indistinguishable from the uniform distribution, one must use an exponent of at least e > 260 (see [29℄). However, as shown in se tion 4, in our s heme we may use an e = 216 + 1 or even e = 3; the penalty is that we work modulo N 2 . Multipli ation modulo an n bit modulus, is navely an n2 operation, although asymptoti ally is an be made to be an O(n log n) operation by the use of fast Fourier transformations. Thus the ost of exponentiating modulo N 2 is between 2 and 4 times slower than exponentiating (to the same exponent) modulo N . The ost of exponentiation on the other hand is between log e and 2 log e depending on the addition hain that is used. Thus one an expe t Effi ien y issues.

that an exponent in the order of 260 will take about 90 multipli ations (using the binary addition hain), whilst e = 3 takes just 2 multipli ations, and e = 216 + 1 takes just 17 multipli ations1 . Let t be the time for a multipli ation modulo N . To nd re mod N 2 in our s heme, thus takes time between 2  2t = 4t and 4  17t = 68t. The modular redu tion to ra and rb an also be done in roughly time t, and the en ryption adds another t, so, in en ryption, our s heme takes time between 6t and 70t. On the other hand Point heval performs two (larger) exponentiations modulo N in en ryption and one multipli ation (for the message), whi h will take time between 121t and 241t. Our s heme is

learly more eÆ ient in en ryption. In de ryption both s hemes de rypt the rst entry in the pair to nd the randomness, and use this to retrieve the message from the se ond entry. However in our s heme we must follow all the steps of en ryption, while Point heval only needs to do one modular exponentiation. Regardless our s heme is still probably slightly more eÆ ient, but, when e is small, the omplexity of the de ryption algorithm is ompletely dominated by the rst stage of re overing the randomness, and so to all pra ti al purposes, the s hemes are identi al in de ryption speed.

6. A NEW TRAPDOOR COMMITMENT SCHEME In this se tion we present a new trapdoor ommitment s heme whi h is based on the original Paillier's en ryption fun tion. The se urity of this ommitment s heme is equivalent to the hardness of RSA[N; N ℄. An interesting property of our proposed ommitment s heme is that it is very eÆ ient to ompute, when some pre omputation time is allowed. More spe i ally, to

ommit to a message m the sender needs to ompute only two modular multipli ations and use a pre omputed value. This value, is independent of m and thus an be

omputed before m is know. This pre omputation requires a single modular exponentiation. Thus even in luding the pre omputation time, our new s heme is omparable in eÆ ien y with all the other trapdoor ommitment s hemes in the literature. A trapdoor ommitment s heme (sometimes also alled a hameleon ommitment) is a fun tion asso iated with a pair of publi and private keys (the latter also alled the trapdoor of the ommitment). This is basi ally a ollision-resistant hash fun tion, meaning that, unless one knows the trapdoor, it is infeasible to nd two inputs that map to the same value. However if one knows the trapdoor, ollisions an be easily found. More formally, a trapdoor ommitment s heme is a triplet (G ; C ; D). Trapdoor Commitments.

G

is a randomized key generation algorithm. On input a se urity parameter k it outputs a pair of publi and private keys: G (1k ) = (pk; sk).

1 We are ignoring the fa t that squarings are slightly more eÆ ient than general modular multipli ations.





The fun tion C is the ommitment fun tion whi h depends on P K C : PK  M  R ! C where P K; M; R; C are the publi key, message, randomness and ommitted values spa es respe tively. Thus C (pk; m; r) = .

The fun tion D is the ollision- nding fun tion, D : SK  C  M ! R on input the trapdoor information, a ommitted value and a message it nds the orresponding random string. I.e. given = C (pk; m; r) for any message m0 we have D(sk; ; m0 ) = r0 su h that

= C (pk; m0 ; r0 ). The requirements that we make on these fun tions are the following: 1. (G ; C ; D) are all omputable in polynomial time. 2. No eÆ ient algorithm, on input just the publi key,

an nd two messages m 6= m0 and two random strings r 6= r0 su h that C (pk; m; r) = C (pk; m0 ; r0 ) ex ept with non-negligible probability. 3. For any message m, the distribution indu ed by the fun tion C over C (i.e. the distribution f = C (pk; m; r)gr2R must be indistinguishable from uniform. In the last ondition the term \indistinguishable" an be intended in the usual three ways: either the distributions are identi al, or they are statisti ally indistinguishable or

omputationally indistinguishable (see [18℄). Previous Work on Trapdoor Commitments. The notion of trapdoor ommitments was introdu ed by Brassard, Chaum and Crepeau [15℄ in the ontext of zeroknowledge arguments. It is well known that trapdoor

ommitments an be based on the existen e of law-free trapdoor permutations [19℄. A spe i implementation presented in [19℄ is based on fa toring. It requires a number of modular squarings in ZN whi h is proportional to the length of the message. A well known trapdoor ommitment based on the hardness of omputing dis rete logarithms is due to Boyar et al. [5℄. This s heme requires a full modular exponentiation (or alternatively here also a number of multipli ations whi h is proportional to the length of the message). The above s hemes require the bulk of the omputation to be done online, i.e. when the message is known. It would be ni e to move as mu h omputation as possible to an oine stage, before the message is known. No way to do this is known for the above ommitments. Our s heme a hieves exa tly this ni e property, without losing in the overall eÆ ien y. It requires only 2 multipli ations online, while a full exponentiation (i.e. a number of multipli ations proportional to the length of the message) is needed for the oine part. Remark 1: Online-Oine EÆ ien y. It should be pointed out that any ommitment C an be transformed into another one C 0 that has the online-oine eÆ ien y property.

C 0 works as follows: in the oine phase the sender ommits to a random string s with randomness r using C . Let  = C (s; r). When m is known then the sender ommits to it by sending  and = m  s. Noti e however

that this will in rease the length of the ommitment. Our s heme is the rst ommitment s heme whi h is dire tly online/oine and does not in rease the length of the ommitted value.

6.1 Our New Trapdoor Commitment In this se tion we des ribe the trapdoor ommitment s heme based on Paillier's original en ryption s heme. Key Generation. The key generation omputes a random RSA modulus N = pq . It then sele ts  2R ZN and 2R ZN nf0g and sets h = N (1 + N ) mod N 2 . Noti e that h = F1+N (; ), where F is Paillier's trapdoor permutation. Sin e  and are hosen uniformly and at random, the h onstru ted above is uniformly distributed in ZN 2 . The publi key is (N; h), the trapdoor is the fa torization of N . The Commitment Fun tion.

To ommit to a message

m 2 ZN , we use two random values r 2R ZN and s 2R ZN and set

C (m; r; s) = (1 + mN )rN hs mod N 2

We prove below that this is a se ure trapdoor ommitment s heme, but for now let us remark on the oine/online eÆ ien y property. Noti e that the ommitter an ompute rN hs in advan e before knowing m. The ost of this pre omputation is slightly larger than a single exponentiation (using te hniques for simultaneous exponentiations). On e m is known the ommitment an be omputed with only two modular multipli ations. Theorem 6.1. Under the assumption that inverting RSA[N; N ℄ is hard, the above fun tion C is a trapdoor ommitment s heme. Proof. We rst prove that C indu es the uniform distribution, then we show that by knowing the fa torization of N one an open the ommitment in any desired way and nally we show that an adversary that opens the ommitment in two ways an be used to invert RSA[N; N ℄. Noti e that from the de nition of C we have that for any message m, = (1+mN )Fh (r; s) where (r; s) are uniformly distributed and Fh is Paillier's original trapdoor permutation. Thus is also uniformly distributed.

Uniform Distribution.

The Collision-Finding Fun tion. Given a ommitment 2 ZN 2 and a message m0 2 ZN we need to nd r0 ; s0 su h that = (1 + m0 N )(r0 )N hs with the help of knowing the fa torization of N . Noti e that (r0 ; s0 ) = F 1 ( (1 + m0 N ) 1 mod N 2 ) 0

h

where Fh is Paillier's trapdoor permutation with parameter h (whi h is well de ned sin e we hose h of order at least N ). Thus (r0 ; s0 ) exists and they are unique and an be found by inverting Fh whi h is a polynomial-time task when given the fa torization of N .

Se urity based on RSA[N; N ℄. Let us assume that we have an eÆ ient algorithm A that on input N; h nds two triplets m; r; s and m0 ; r0 ; s0 , with m 6= m0 su h that (1 + mN )rN hs = (1 + m0 N )(r0 )N hs mod N 2 . A rst step in the proof is to show how to use A to nd  2 ZN and 2 ZN su h that h = N (1 + N ) mod N 2 . Indeed by plugging in this de nition of h we get that (rs )N [1+(m+ s)N ℄ = (r0 s )N [1+(m0 + s0 )N ℄ mod N 2 0

0

or by re alling the de nition of Paillier's original trapdoor permutation F1+N

F1+N (rs ; m + s) = F1+N (r0 s ; m0 + s0 ) Sin e F1+N is a permutation we have that 0

rs = r0 s mod N 0

(1)

and

m + s = m0 + s0 mod N From the latter equation we obtain (sin e m 6= m0 implies s 6= s0 ). Now let Æ = s s0 . From Equation 1 we get that Æ = 0 r r 1 mod N . Moreover we know (from the de nition of h) that N = h mod N . Sin e g d(Æ; N ) = 1 (otherwise we fa tor N ) we an nd integers a; b su h that aÆ + bN =

1. Thus

the signer, who thus an ontrol to whom the signed do ument is being dis losed. Signers are able to on rm valid signatures and deny invalid ones. A trusted third party (a judge) may be invoked in ase the signer refuses to

ooperate. Chameleon Signatures remove the need for intera tive proto ols in the veri ation of signatures. A hameleon signature instead is a re ipient-spe i string whi h will

onvin e only the re ipient and nobody else. Yet, the sender may de ide later to transform this signature into a traditional universally veri able one (a pro edure alled

onversion whi h an also be applied to undeniable signatures). The in reased eÆ ien y is obtained at the ost of a small restri tion in fun tionality. With respe t to undeniable signatures, hameleon ones are slightly weaker be ause of their re ipient-spe i nature (for example, they leak the fa t that sender and re eiver have been ex hanging messages). See [23℄ for a dis ussion on these issues. The basi idea of [23℄ to onstru t hameleon signatures is to use a traditional signature s heme, but ombined with a trapdoor ommitment. More spe i ally:



the re ipient R owns the publi key for a trapdoor

ommitment T CR ; she holds in se ret the trapdoor information tR .



The sender S owns a publi key P KS for a se ure signature s heme; he holds in se ret the mat hing se ret key SKS .



To sign a message M , the signer hooses some randomness r and omputes m = T CR (M; r) and then

omputes the signature  on m.

 = aÆ+bN = (r0 r 1 )a hb mod N

We have shown that an adversary A that breaks the ommitment an be used to invert F1+N on h. We know that the fun tion F1+N is random self-redu ible [2℄. We also

hose h at random among the elements of order at least N in ZN 2 . But this is a polynomially large fra tion of the elements of ZN 2 . Thus we an use A to invert F1+N everywhere. The laim of the theorem follows from Paillier's observation that inverting F1+N is equivalent to invert RSA[N; N ℄.

6.2 Application to Chameleon Signatures Chameleon Signatures were introdu ed in [23℄. They are intended to solve a on dentiality problem in typi al digital signatures solution. When a sender, transmits a do ument signed with his publi key, to a re eiver, he's not only authenti ating the do ument to the re eiver but also allowing her to show the do ument to a third party to onvin e the latter that it really ame from the signer. Although this non-repudiation property of digital signatures is one of their strongest advantages, in some s enarios it might

reate unwanted on dentiality problems. Think of on dential do uments that should not be leaked before a

ertain date ( ontra ts, sto k mergers, earning reports). In these ase what is ne essary is a way to prevent unauthorized dis losure of the signed do ument, but at the same time a way to enfor e non-repudiation using some spe ial me hanism. Undeniable signatures were introdu ed in [16℄ to address the above problem. In their solution, veri ation of a digital signature is an intera tive proto ol that in ludes

Short History.

Clearly sin e the re eiver knows tR , she an laim that m is the \hash" of any message M 0 . Thus she will not be able to onvin e a third party of the validity of the signature M 0 ;  . Using our new trapdoor

ommitment s heme it is thus possible to onstru t a

hameleon signature s heme whi h enjoys the \onlineoine" eÆ ien y property. The idea is to ombine our trapdoor ommitment with a online-oine signature s heme, that is a signature s heme that an be pre omputed in almost its entirety before the message is known and then \ ompleted" with some easy algebrai operation. Several examples of this kind of undeniable signatures already exist (DSS and ElGamal being probably the best known ones). See also [12℄ whi h formalized the on ept and proposed a generi solution.

Online-Offline Effi ien y.

7. CONCLUSIONS We presented a new variant of Paillier's ryptosystem that greatly improves its eÆ ien y. We also des ribed an interesting onne tion between a modi ed version of our s heme and Point heval's en ryption te hnique. Again our resulting ryptosystem proved to be more eÆ ient. We have also shown how to use Paillier's s heme to onstru t a new trapdoor ommitment s heme. This s heme is the rst trapdoor ommitment that allows the sender to

pre ompute all the expensive omputation before the message is known, and then omplete it with only two modular multipli ations. The main appli ation of the above is the onstru tion of the rst online-oine hameleon signature s heme. The results of this paper ni ely exploit the ri h mathemati al stru ture behind Paillier's original s heme. We also believe that other interesting results an be obtained. For example it would be interesting to investigate if further exploitation of Paillier's ideas ould yield an eÆ ient solution for se ure en ryption against hosen- iphertext atta ks in the standard model. We remark that in the random ora le model there are standard te hniques for

hosen- iphertext se urity that apply to both Paillier's s heme and our variants.

[12℄ [13℄ [14℄

[15℄ [16℄

Acknowledgements The authors would parti ularly like to thank Ran Canetti for his generi thoughts on online-oine trapdoor ommitments.

8. REFERENCES [1℄ J. D. C. Benaloh. Veri able Se ret-Ballot Ele tions. PhD thesis, Yale University, 1987. [2℄ M. Blum and S. Mi ali How to generate

ryptographi ally strong sequen es of pseudo random bits. SIAM Journal of Computing Vol.13, No.4:850-864, 1984. [3℄ D. Boneh and G. Durfee. Cryptanalysis of RSA with private key d less than n0:292 . IEEE Trans. Inf. Th., 46(4):1339{1349, July 2000. [4℄ D. Boneh, G. Durfee, and N. Howgrave-Graham. Fa toring n = pr q for larger r. In Pro . of Crypto '99, volume 1666 of LNCS, pages 326{337. Springer, 1999. [5℄ J.F. Boyar, S.A. Kurtz, and M.W. Krentel. A dis rete logarithm implementation of perfe t zero-knowledge blobs. J. of Cryptology, 2(2):63{76, 1990. [6℄ CESG. The history of non-se ret en ryption. Available at http://www. esg.gov.uk/about/nse ret.htm. [7℄ J. D. Cohen and M. Fis her. A robust and veri able

ryptographi ally se ure ele tion s heme. In Pro . of the 26th FOCS. IEEE, 1985. [8℄ D. Coppersmith. Finding small solutions to small degree polynomials. In Pro . of CaLC '01. To appear. [9℄ D. Coppersmith. Finding a small root of a univariate modular equation. In Pro . of Euro rypt '96, volume 1070 of LNCS, pages 155{165. Springer, 1996. [10℄ D. Coppersmith, M. Franklin, J. Patarin, and M. Reiter. Low-exponent RSA with related messages. In Pro . of Euro rypt '96, volume 1070 of LNCS, pages 1{9. Springer-Verlag, 1996. [11℄ I. Damg ard and M. Jurik. A generalization, a simpli ation and some appli ations of Paillier's

[17℄ [18℄ [19℄

[20℄ [21℄ [22℄ [23℄ [24℄ [25℄

[26℄ [27℄

[28℄

[29℄

probabilisti publi -key system. In Pro . of PKC '2001, volume 1992 of LNCS. Springer-Verlag, 2001. S. Even, O. Goldrei h, S. Mi ali. On{Line/O{Line Digital Signatures. J. of Cryptology, 9(1):35{67, 1996. P. A. Fouque, G. Poupard, and J. Stern. Sharing De ryption in the Context of Voting or Lotteries. In Finan ial Crypto '00, LNCS. Springer-Verlag, 2000. P. A. Fouque and J. Stern. One Round Threshold Dis rete-Log Key Generation without Private Channels. In Pro . of PKC '01, volume 1992 of LNCS. Springer-Verlag, 2001. G. Brassard, D. Chaum, and C. Crepeau. Minimum dis losure proofs of knowledge. JCSS, 37(2):156{189, 1988. D. Chaum and H. Van Antwerpen. Undeniable Signatures. Pro eedings of CRYPTO'89, vol.435 of LNCS, pp. 212{217. S. Goldwasser and S. Mi ali. Probabilisti en ryption. Journal of Computer and System S ien es, 28:270{299, 1984. S. Goldwasser, S. Mi ali, and C. Ra ko. The knowledge omplexity of intera tive proof systems. SIAM J.Comput., 18(1):186{208, 1989. S. Goldwasser, S.Mi ali, and R.L.Rivest. A digital signature s heme se ure against adaptive

hosen-message atta ks. SIAM J.Comput., 17(2):281{308, 1988. J. H astad. Solving simultaneous modular equations of low degree. SIAM J. Computing, 17(2):336{341, 1988. N. Howgrave-Graham. Approximate integer

ommon divisors. In Pro . of CaLC '01, volume 2146 of LNCS. Springer-Verlag, 2001. N.A. Howgrave-Graham. Computational Mathemati s Inspired by RSA. PhD thesis, University of Bath, 1999. H. Kraw zyk and T. Rabin. Chameleon Signatures. Pro eedings of NDSS 2000, pp.143{154. S. Mi ali and C.P. S hnorr. EÆ ient, perfe t random number generators. In Pro . of Crypto '88, volume 403 of LNCS. IACR, Springer-Verlag, 1990. D. Na

a he and J. Stern. A new publi key

ryptosystem based on higher residues. In Pro . of 5th Symposium on Computer and Communi ations Se urity. ACM, 1998. P.Q. Nguyen and J.Stern.. The two fa es of latti es in ryptology. In Pro . of CaLC '01, volume 2146 of LNCS. Springer-Verlag, 2001. T. Okamoto and S. U hiyama. A new publi -key

ryptosystem as se ure as fa toring. In Pro . of Euro rypt '98, volume 1403 of LNCS. IACR, Springer-Verlag, 1998. P. Paillier. Publi key ryptosystems based on

omposite degree residuosity lasses. In Pro . of Euro rypt '99, volume 1592 of LNCS, pages 223{238. IACR, Springer-Verlag, 1999. D. Point heval. New publi key ryptosystems based on the dependent{RSA problems. In Pro . of

Euro rypt '99, volume 1592 of LNCS. IACR, Springer-Verlag, 1999. [30℄ G. Poupard and J. Stern. Fair en ryption of RSA keys. In Pro . of Euro rypt '2000, volume 1807 of LNCS. IACR, Springer-Verlag, 2000. [31℄ B. Vallee, M. Girault, and P. ToÆn. How to guess l'th roots modulo n by redu ing latti e bases. In Pro . of AAECC-6, volume 357 of LNCS, pages 427{442. Springer, 1988.