Security Analysis of Naccache-Stern Public Key Cryptosystem

This paper analyzes the security of the Naccache-Stern public key cryptosystem by providing an attack. The basic idea of the attack is that the decryption of the cryptosystem can be viewed as a group factorization problem and the solution to the problem gives rise to an equivalent plaintext. It is also shown that if all the entries of the equivalent plaintext vector are small enough, the equivalent plaintext is the exact plaintext corresponding to the ciphertext. In general, the success probability of the proposed attack is much higher than that of solving the discrete logarithm problem directly. The success probability of the attack relies on with what probability it can successfully transform a random integer into a smooth number.