The bit security and Paillier’s encryption scheme and its applications

Abstract. 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¤N2 is hard. Similarly the scheme can be proven to be semantically secure under a much stronger decisional assumption: given w 2 Z¤N2 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 signi¯cant bit of its class signi¯cantly 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 e±ciency we then turn to the problem of simulta-neous security of many bits. We prove that Paillier's scheme hides n ¡ b (up to O(n)) bits if one assumes that computing the class c of a ran-dom 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 ¯rst trapdoor function that hides super-logarithmically (up to O(n)) many bits. We generalize our techniques to provide su±cient conditions for a trapdoor function to have this property.