A New Attack on NTRU Public Key Cryptosystem Depend on Using Public Key and Public Information

Abstract

This paper proposed a new method to attack the NTRU cryptosystem [Hof00a,Hof98b]. It tried to exploit the public information about the parameters of NTRUcryptosystem and using the public key, to recover the private keys without delvingin the detail of encryption and decryption. It depended on extant knowledge aboutthe number of 1’s and -1’s in the private keys coefficients, f and g, which areused in public key generation. It tried to make use of the polynomial that hasprivate key coefficients properties. The proposed attack was able to recover aunique polynomial that represented the private key f and corresponding to privatekey g, or their rotations. But, this attack remains expensive in time and depends onthe way of how to start in choice the permutation