In this article we present a lattice attack done on a NTRU-like scheme introduced by Verkhovsky in . We show how, based on the relation between the public and private key, we can construct an attack which allows any passive adversary to decrypt the encrypted messages. We explain, step by step, how an attacker can construct an equivalent private key and guess what the original plaintext was. Our attack is efficient and provides good experimental results.
D. Coppersmith and A. Shamir, “Lattice Attacks on NTRU,” Advances in Cryptology—EUROCRYPT ’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, 11-15 May 1997, pp. 52-61.
D. Stehle and R. Steinfeld, “Making NTRU as Secure as Worst-Case Problems over Ideal Lattices,” Advances in Cryptology—EUROCRYPT 2011—30th Annual International Conference on the Theory and applications of Cryptographic Techniques, Tallinn, 15-19 May 2011, pp. 27-47.
C. Gentry, J. Jonsson, J. Stern and M. Szydlo, “CryptANALYSIS of the NTRU Signature Scheme (NSS) from Eurocrypt 2001,” Advances in Cryptology—ASIACRYPT’01, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, 9-13 December 2001, pp. 1-20.
P. Q. Nguyen and J. Stern, “Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations,” Advances in Cryptology—CRYPTO’97, 17th Annual International Cryptology Conference, Santa Barbara, 17-21 August 1997, pp. 198-212.