Quantum Augmented Lattice Attack on NTRU with Side Information

NTRU is one of the most important lattice-based public key cryptosystems, and a potential candidate for post-quantum cryptography. This paper derives a generic lattice-based attack on NTRU assisted by side information and a quantum augmented lattice basis reduction algorithm. We first exploit the various situations of side information to transforming the NTRU lattice, and produce a smaller lattice basis containing the target vector. Then, we adopt a new variant of BKZ algorithm to solve the NTRU cases, and further construct a quantum augmented version of lattice-based attack with quantum sieve oracles. With the new lattice reduction techniques, our attack only requires a smaller fraction of the secret polynomial’s coefficients to successfully recover the NTRU key.