A Trapdoor Permutation Equivalent to Factoring

A Trapdoor Permutation Equivalent to Factoring [Published in H.Imai and Y.Zheng,Eds.,Public-Key Cryptography,vol.1560 of Lecture Notes in Computer Science,pp.219–222,Springer-Verlag,1999.]

Pascal Paillier1,2

1Gemplus Card International,Cryptography Department

34rue Guynemer,92447Issy-les-Moulineaux,France

pascal.paillier@https://www.doczj.com/doc/df11896364.html,

2ENST,Computer Science Department

46rue Barrault,75634Paris Cedex13

paillier@inf.enst.fr

Abstract.In Eurocrypt’98[1],Okamoto et al.exhibited a new trapdoor

function based on the use of a special moduli(p2q)allowing easy discrete

logarithm computations.The authors proved that the scheme’s resistance

to chosen-plaintext attacks is equivalent to factoring n.Unfortunately,

the proposed scheme su?ers from not being a permutation(the expansion

rate is～=3),and hence cannot be used for public-key signatures.

In this paper,we show how to re?ne the function into a trapdoor per-

mutation that can be used for signatures.Interestingly,our variant still

remains equivalent to factoring and seems to be the second known trap-

door permutation(Rabin-Williams’scheme[3]being the?rst)provably

as secure as a primitive problem.

1The Okamoto-Uchiyama Cryptosystem

In Eurocrypt’98,Okamoto and Uchiyama proposed a new public-key cryptosys-tem based on the ability of computing discrete logarithms in a particular sub-

is

https://www.doczj.com/doc/df11896364.html,ly,if p is a large prime andγp?Z?

p2

γp={x

thenγp has a group structure with respect to the multiplication modulo p2and γp=p.The function log(.):γp?→Z p which associates(x?1)/p to x is clearly well-de?ned onγp and presents interesting homomorphic properties.In particular,

?x,y∈γp log(xy mod p2)=log(x)+log(y)mod p

whereby,as a straightforward generalization,

?g∈γp,m∈Z p log(g m mod p2)=m log(g)mod p.

2Pascal Paillier

Key Setup.Generate two k-bit primes p and q(typically3k=1023)and set n=p2q.Randomly select and publish a number g

g p=g p?1mod p2

is of order p in Z?

p2and keep g p secret(note that g p∈γp).Similarly,choose

g

h=g n mod n.

The triple(n,g,h)forms the public key.The secret key is(p,q). Encryption.Pick r

c=g m h r mod n.

Decryption.Proceed as follows:

1.c =c p?1mod p2=g m(p?1)g nr(p?1)=g m p mod p2,

2.m=log(c )log(g p)?1mod p.

We refer the reader to[1]for a thorough description of the scheme.Although provably equivalent to factoring[5]as far as chosen-plaintext attacks are con-cerned,the scheme su?ers from the fact that ciphertexts are about three times longer than plaintexts.As a result,it is impossible to use[1]’s trapdoor as a signature scheme.

The next section shows how to extend the scheme to a trapdoor permutation [4]over Z?n.Interestingly,the security analysis presented in section3shows that the new encryption function is still as secure as factoring.

2The New Trapdoor Function

Using the same notations as before,let the message be3k?2-bit long and de?ne m=m1||m2where m1<2k?1,m2<22k?1and||stands for concatenation.The encryption procedure is as follows.

Encryption.Split m into m1and m2and encrypt by:

c=g m1m n2mod n.

This presents an expension rate of:

ρ=log()2n

3k

,

A Trapdoor Permutation Equivalent to Factoring3

which is very close to1for common values of k.

https://www.doczj.com/doc/df11896364.html,pute

c =c p?1mo

d p2=g m1p mod p2,

and

m1=log(c )log(g p)?1mod p,

as in[1]and

1.deduce m n2mod pq=g?m1c mod pq

2.obtain m2mod pq=(m n2mod pq)n?1mod(p?1)(q?1)mod pq

3.conclude by m=m1||m2.

3Equivalence to Factoring

In this section,we prove the one-wayness of our encryption function under the factoring assumption:

Theorem1.Inverting the new encryption function is equivalent to factoring n. Proof(Sketch).Assuming that there exists a probabilistic polynomial time Tur-ing machine M which decrypts ciphertexts for a given(n,g)with a non-negligible probability,we transform M into a PPT machine M that factors n with non-negligible probability.We directly re-use the proof arguments from Theorem6 of[1]for showing the statistical closeness of distributions of ciphertexts.Feeding M with g z mod n for random(k+1)-bit numbers z,we need a single correct answer m=m1||m2to recover a nontrivial factor of n by gcd(z?m1,n).

Alternatively,the encryption and decryption functions can be used for digital signatures as well.To achieve this,a signer computes the signature s=s1||s2of the message m such that

g s1s n2=h(m)mod n,

where h is a collision-free one-way hash function.Note however that since s1∈Z p and s2∈Z?pq,some information about p and q will leak out at each signature. Namely,collecting N signatures(of arbitrary messages)will allow an attacker to recover O(log(N))bits of p.We therefore recommand to regularly re-generate the scheme’s parameters,possibly according to an internal counter.

It is worthwhile noticing that our scheme presents underlying homomorphic properties which could be useful for designing distributed cryptographic proto-cols(multi-signatures,secret sharing,threshold cryptography and so forth).

4Further Research

Okamoto-Uchiyama’s trapdoor technique is inherently new in the sense that it profoundly di?ers from RSA and Di?e-Hellman.It makes no doubt that this technique could be declined in various ways for designing new public-key cryp-tosystems in near future.

4Pascal Paillier

References

1.T.Okamoto and S.Uchiyama,A New Public-Key Cryptosystem as secure as Factor-

ing,LNCS1403,Advances in Cryptology,Proceedings of Eurocrypt’98,Springer-Verlag,pp.308–318,1998.

2.W.Di?e and M.Hellman,New Directions in Cryptography,IEEE Transaction on

Information Theory,IT-22,6,pp.644–654,1995.

3.M.Rabin,Digitalized Signatures and Public-Key Functions as Intractable as Fac-

torization,Technical Report No.212,MIT Laboratory of Computer Science,Cam-bridge,pp.1–16,1979.

4.L.Goubin and J.Patarin,Trapdoor One-Way Permutations and Multivariate Poly-

nomials,Proceedings of ICICS’97,LNCS1334,Springer-Verlag,pp356–368,1997.

5. E.Okamoto and R.Peralta,Faster Factoring of Integers of a Special Form,IEICE

Trans.Fundamentals,Vol.E79-A,No4,pp489–493,1996.