The Bit Security of Paillier’s Encryption Scheme and Its Applications

  • Dario Catalano
  • Rosario Gennaro
  • Nick Howgrave-Graham
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


At EuroCrypt'99, Paillier proposed a new encryption scheme based on higher residuosity classes. The new scheme was proven to be one-way under the assumption that computing N-residuosity classes in Z * N 2 is hard. Similarly the scheme can be proven to be semantically secure under a much stronger decisional assumption: given wZ * N 2 it is hard to decide if w is an N-residue or not.

In this paper we examine the bit security of Paillier’s scheme. We prove that, if computing residuosity classes is hard, then given a random w it is impossible to predict the least significant bit of its class significantly better than at random. This immediately yields a way to obtain semantic security without relying on the decisional assumption (at the cost of several invocations of Paillier's original function).

In order to improve efficiency we then turn to the problem of simultaneous security of many bits. We prove that Paillier's scheme hides nb (up to O(n)) bits if one assumes that computing the class c of a random w remains hard even when we are told that c < 2b. We thoroughly examine the security of this stronger version of the intractability of the class problem.

An important theoretical implication of our result is the construction of the first trapdoor function that hides super-logarithmically (up to O(n)) many bits. We generalize our techniques to provide sufficient conditions for a trapdoor function to have this property.


Encryption Scheme Inversion Algorithm Probabilistic Polynomial Time Trapdoor Function Trapdoor Permutation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    W. Alexi, B. Chor, O. Goldreich and C. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM J. Computing, 17(2):194–209, April 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    J.C. Benaloh. Verifiable Secret-Ballot Elections. Ph.D. Thesis, Yale University, 1988.Google Scholar
  3. 3.
    M. Blum and S. Goldwasser. An efficient probabilistic public-key encryption scheme which hides all partial information. Proc. of Crypto '84, LNCS vol. 196, pages 289–302Google Scholar
  4. 4.
    M. Blum and S. Micali. How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM Journal on Computing, Vol. 13, No. 4:850–864, 1984zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    R. Fischlin and C.P. Schnorr. Stronger Security Proofs for RSA and Rabin Bits. J. of Cryptology, 13(2):221–244, Spring 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    O. Goldreich and L. Levin A hard-core predicate for all one-way functions. Proc. 21 st ACM Symposium on Theory of Computing, 1989Google Scholar
  7. 7.
    S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS, 28(2):270–299, April 1984.zbMATHMathSciNetGoogle Scholar
  8. 8.
    J. Hastad, A. W. Schrift and A. Shamir. The Discrete Logarithm Modulo a Composite Hides O(n) Bits. JCSS Vol. 47, pages 376–404, 1993.zbMATHMathSciNetGoogle Scholar
  9. 9.
    T. Okamoto and S. Uchiyama. A New Public-Key Cryptosystem as Secure as Factoring In Advances in Cryptology-Eurocrypt '97, LNCS vol. 1233, Springer, 1997, pages 308–318.Google Scholar
  10. 10.
    P. Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Advances in Cryptology-Eurocrypt '99, LNCS vol. 1592, Springer, 1997, pages 223–238.Google Scholar
  11. 11.
    S. Patel and G. S. Sundaram. An Efficient Discrete Log Pseudo Random Generator. In Advances in Cryptology-CRYPTO '98, LNCS vol. 1492, Springer, 1998, pages 304–315.CrossRefGoogle Scholar
  12. 12.
    M. Rabin. Digital Signatures and Public Key Encryptions as Intractable as Factorization. MITT echnical Report no. 212, 1979Google Scholar
  13. 13.
    R. Rivest, A. Shamir and L. Adelman. A Method for Obtaining Digital Signature and Public Key Cryptosystems. Comm. of ACM, 21 (1978), pp. 120–126zbMATHCrossRefGoogle Scholar
  14. 14.
    A. Yao. Theory and Applications of Trapdoor Functions. IEEE FOCS, 1982.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Dario Catalano
    • 1
  • Rosario Gennaro
    • 2
  • Nick Howgrave-Graham
    • 2
  1. 1.Dipartimento di Matematica e InformaticaUniversitá di CataniaCatania
  2. 2.IBM T.J.Watson Research CenterYorktown HeightsUSA

Personalised recommendations