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.
2ENST,Computer Science Department
46rue Barrault,75634Paris Cedex13
st.fr
Abstract.In Eurocrypt’98[1],Okamoto hibited a new trapdoor
function bad on the u of a special moduli(p2q)allowing easy discrete
logarithm computations.The authors proved that the scheme’s resistance
to chon-plaintext attacks is equivalent to factoring n.Unfortunately,
the propod scheme suffers from not being a permutation(the expansion
rate is∼=3),and hence cannot be ud for public-key signatures.
In this paper,we show how to refine the function into a trapdoor per-
mutation that can be ud for signatures.Interestingly,our variant still
remains equivalent to factoring and ems to be the cond known trap-
土豆烧牛腩door permutation(Rabin-Williams’scheme[3]being thefirst)provably
as cure as a primitive problem.
1The Okamoto-Uchiyama Cryptosystem
In Eurocrypt’98,Okamoto and Uchiyama propod a new public-key cryptosys-tem bad on the ability of computing discrete logarithms in a particular sub-
is
group.Namely,if p is a large prime andγp⊂Z∗
p2
γp={x<p2|x=1mod p},
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-defined onγp and prents 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 t n=p2q.Randomly lect and publish a number g<n such that
g p=g p−1mod p2
is of order p in Z∗
p2and keep g p cret(note that g p∈γp).Similarly,choo
g <n at random and publish
描写枫叶的诗句h=g n mod n.
The triple(n,g,h)forms the public key.The cret key is(p,q). Encryption.Pick r<n uniformly at random and encrypt the k-bit message m by:
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 chon-plaintext attacks are con-cerned,the scheme suffers from the fact that ciphertexts are about three times longer than plaintexts.As a result,it is impossible to u[1]’s trapdoor as a signature scheme.
The next ction shows how to extend the scheme to a trapdoor permutation [4]over Z∗n.Interestingly,the curity analysis prented in ction3shows that the new encryption function is still as cure as factoring.
2The New Trapdoor Function
Using the same notations as before,let the message be3k−2-bit long and define 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 prents an expension rate of:
ρ=log()2n
3k
印度河流向,
A Trapdoor Permutation Equivalent to Factoring3
which is very clo to1for common values of k.
Decryption.Compute
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
3Equivalence to Factoring
In this ction,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-u the proof arguments from Theorem6 of[1]for showing the statistical cloness 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 ud 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 prents underlying homomorphic properties which could be uful for designing distributed cryptographic proto-cols(multi-signatures,cret sharing,threshold cryptography and so forth).
4Further Rearch
Okamoto-Uchiyama’s trapdoor technique is inherently new in the n that it profoundly differs from RSA and Diffie-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 cure as Factor-
ing,LNCS1403,Advances in Cryptology,Proceedings of Eurocrypt’98,Springer-Verlag,pp.308–318,1998.
2.W.Diffie 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.
