A polynomial time algorithm for breaking NTRU encryption with multiple keys

We present a polynomial time algorithm for breaking NTRU encryption schemes with multiple keys. Our algorithm takes advantage of the specific sampling regime used in NTRU encryption, which samples secret polynomials with a fixed number of coefficients of 1 and -1 . By constructing an equation system on the secret keys, we are able to recover the unique secret key when n multiple keys sharing a common denominator are given for an extension degree n . This result shows that NTRU encryption schemes with multiple keys can be solved in polynomial time in n .