Schools

Publications

Home Schools Computational Sciences Publications

Title
A polynomial time algorithm for breaking NTRU encryption with multiple keys
KIAS Author
Lee, Changmin
Journal
DESIGNS CODES AND CRYPTOGRAPHY, 2023
Archive
Abstract
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.