A Simple and Efficient Key Reuse Attack on NTRU Cryptosystem

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

Paper 2019/1022

A Simple and Efficient Key Reuse Attack on NTRU Cryptosystem

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

Abstract

In 1998, Jeffrey Hoffstein, 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): jintai ding @ gmail com
deatonju @ mail uc edu
schmidku @ mail uc edu
sharmav4 @ mail uc edu
zhang2zh @ mail uc edu
History: 2020-06-10: last of 3 revisions; 2019-09-11: received; See all versions
Short URL: https://ia.cr/2019/1022
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1022,
      author = {Jintai Ding and Joshua Deaton and Kurt Schmidt and Vishakha and Zheng Zhang},
      title = {A Simple and Efficient Key Reuse Attack on NTRU Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1022},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1022}},
      url = {https://eprint.iacr.org/2019/1022}
}