Paillier's cryptosystem revisited

ABSTRACT

We re-examine Paillier's cryptosystem, and show that by choosing a particular discrete log base g, and by introducing an alternative decryption procedure, we can extend the scheme to allow an arbitrary exponent e instead of N. The use of low exponents substantially increases the efficiency of the scheme. The semantic security is now based on a new decisional assumption, namely the hardness of deciding whether an element is a "small" e-th residue modulo N².We also show how to use Paillier's original cryptosystem to build a trapdoor commitment scheme. This new scheme is information-theoretically private, and computationally binding (this property holds under the assumption that the RSA function with exponent N is hard to invert). A novel property of this new commitment scheme is that most of the work can be done offline before knowing the message one wants to commit to. Once the message is known only two multiplications are required. This is the first trapdoor commitment scheme with this online-offline efficiency property which is also length-preserving.

REFERENCES

• 1: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, 1987
• 2: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 3: D Boneh and G Durfee.Cryptanalysis of RSA with private key d less than n0 .292IEEE Trans. Inf.Th.,46(4):1339 -1349,July 2000.
• 4: Dan Boneh , Glenn Durfee , Nick Howgrave-Graham, Factoring N = prq for Large r, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.326-337, August 15-19, 1999
• 5: Joan F. Boyar , Stuart A. Kurtz, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology, v.2 n.2, p.63-76, 1990
• 6: CESG.The history of non-secret encryption. Available at http://www.cesg.gov.uk/about/nsecret.htm
• 7: J.D.CohenandM.Fischer.Arobustandveri .able cryptographically secure election scheme.In Proc. of the 26th FOCS IEEE,1985.
• 8: Don Coppersmith, Finding Small Solutions to Small Degree Polynomials, Revised Papers from the International Conference on Cryptography and Lattices, p.20-31, March 29-30, 2001
• 9: D Coppersmith.Finding a small root of a univariate modular equation.In Proc.ofErocrypt '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 Proc.of E rocrypt '96 ,volume 1070 of LNCS ,pages 1 -9.Springer-Verlag,1996.
• 11: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 12: S.Even,O Goldreich,S Micali.On -Line/O .-Line Digital Signatures.J.of Cryptology ,9(1):35 -67, 1996.
• 13: Pierre-Alain Fouque , Guillaume Poupard , Jacques Stern, Sharing Decryption in the Context of Voting or Lotteries, Proceedings of the 4th International Conference on Financial Cryptography, p.90-104, February 20-24, 2000
• 14: Pierre-Alain Fouque , Jacques Stern, One Round Threshold Discrete-Log Key Generation without Private Channels, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.300-316, February 13-15, 2001
• 15: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 16: David Chaum , Hans van Antwerpen, Undeniable signatures, Proceedings on Advances in cryptology, p.212-216, July 1989, Santa Barbara, California, United States
• 17: S.Goldwasser and S.Micali.Probabilistic encryption.Journal of Computer and System Sciences ,28:270 -299,1984.
• 18: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 19: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 20: Johan Hastad, Solving simultaneous modular equations of low degree, SIAM Journal on Computing, v.17 n.2, p.336-341, April 1988 [doi>10.1137/0217019]
• 21: Nick Howgrave-Graham, Approximate Integer Common Divisors, Revised Papers from the International Conference on Cryptography and Lattices, p.51-66, March 29-30, 2001
• 22: N.A.Howgrave-Graham.Computational Mathematics Inspired by RSA PhD thesis, University of Bath,1999.
• 23: H.Krawczyk and T.Rabin.Chameleon Signatures. Proceedings of NDSS 2000,pp.143 -154.
• 24: S. Micali , C. P. Schnorr, Efficient, perfect random number generators, Proceedings on Advances in cryptology, p.173-198, February 1990, Santa Barbara, California, United States
• 25: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 26: Phong Q. Nguyen , Jacques Stern, The Two Faces of Lattices in Cryptology, Revised Papers from the International Conference on Cryptography and Lattices, p.146-180, March 29-30, 2001
• 27: T.Okamoto and S.Uchiyama.A new public-key cryptosystem as secure as factoring.In Proc.of Eurocrypt '98 ,volume 1403 of LNCS .IACR, Springer-Verlag,1998.
• 28: P Paillier.Public key cryptosystems based on composite degree residuosity classes.In Proc.of Eurocrypt '99 ,volume 1592 of LNCS ,pages 223 -238.IACR,Springer-Verlag,1999.
• 29: D.Pointcheval.New public key cryptosystems based on the dependent -RSA problems.In Proc.of Eurocrypt '99 ,volume 1592 of LNCS .IACR, Springer-Verlag,1999.
• 30: G.Poupard and J Stern.Fair encryption of RSA keys In Proc.of Eurocrypt '2000 ,volume 1807 of LNCS IACR,Springer-Verlag,2000.
• 31: Philippe Toffin , Marc Girault , Brigitte Vallée, How to Guess l-th Roots Modulo n by Reducing Lattice Bases, Proceedings of the 6th International Conference, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.427-442, July 04-08, 1988

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems; Standards (e.g., DES, PGP, RSA)

General Terms:
Algorithms, Performance, Security