Paillier's Trapdoor Function Hides up to O ( n ) Bits |
| |
Authors: | Dario Catalano Rosario Gennaro and Nick Howgrave-Graham |
| |
Affiliation: | (1) Département d'Informatique, Ecole Normale Supérieure, 45 Rue d'Ulm, 75230 Paris, France Dario.Catalano@ens.fr, FR;(2) I.B.M. T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, U.S.A. rosario@watson.ibm.com, US;(3) NTRU Cryptosystems, 5 Burlington Woods, Burlington, MA 01803, U.S.A. NHowgraveGraham@ntru.com, US |
| |
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 ∈ Z
N2
*
it is impossible 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 n-b (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<2
b
. 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. |
| |
Keywords: | , Trapdoor functions, Bit security, Semantic security, |
本文献已被 SpringerLink 等数据库收录! |
|