Home Schools Computational Sciences Publications
- A polynomial time algorithm for breaking NTRU encryption with multiple keys
- KIAS Author
- Lee, Changmin
- DESIGNS CODES AND CRYPTOGRAPHY, 2023
- 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.