Cryptology ePrint Archive: Report 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.

Category / Keywords: Lattice and Encryption and Ntru and Cryptanalysis and KEM.

Date: received 10 Sep 2019

Contact author: jintai ding at gmail com,deatonju@mail uc edu,zhang2zh@mail uc edu,schmidku@mail uc edu,sharmav4@mail uc edu

Available format(s): PDF | BibTeX Citation

Version: 20190911:071922 (All versions of this report)

Short URL: ia.cr/2019/1022


[ Cryptology ePrint archive ]