Paper 2019/1022

A Simple Key Reuse Attack on Ntru Cryptosystem

Jintai Ding and Joshua Deaton and Zheng Zhang and Kurt Schmidt and Vishakha

Abstract

In 1998, Jerey Hostein, Jill Pipher, and Joseph H. Silverman introduced the famous Ntru cryptosystem, and called it "A ring-based public key cryptosystem". Actually it turns out to be a lattice based cryptosystem that is resistant to Shor's algorithm. There are several modifications to the original Ntru and two of them are selected as round 2 candidates of NIST post quantum public key scheme standardization. In this paper, we present a simple attack on the original Ntru scheme. The idea comes from Ding et al.'s key mismatch attack. Essentially, an adversary can find information on the private key of a KEM by not encrypting a message as intended but in a manner which will cause a failure in decryption if the private key is in a certain form. In the present, Ntru has the encrypter generating a random polynomial with "small" coefficients, but we will have the coefficients be "large". After this, some further work will create an equivalent key.