Paper 2021/168

Small Leaks Sink a Great Ship: An Evaluation of Key Reuse Resilience of PQC Third Round Finalist NTRU-HRSS

Xiaohan Zhang, Chi Cheng, and Ruoyu Ding


NTRU is regarded as an appealing finalist due to its long history against all known attacks and relatively high efficiency. In the third round of the NIST competition, the submitted NTRU cryptosystem is the merger of NTRU-HPS and NTRU-HRSS. In 2019, Ding et al. have analyzed the case when the public key is reused for the original NTRU scheme. However, NTRU-HRSS selects coefficients in an arbitrary way, instead of fixed-weight sample spaces in the original NTRU and NTRU-HPS. Therefore, their method cannot be applied to NTRU-HRSS. To address this problem, we propose a full key mismatch attack on NTRU-HRSS. Firstly, we find a longest chain which helps us in recovering the following coefficients. Next, the most influential interference factors are eliminated by increasing the weight of targeted coefficients. In this step, we adaptively select the weights according to the feedbacks of the oracle to avoid errors. Finally, experiments show that we succeed in recovering all coefficients of the secret key in NTRU-HRSS with a success rate of $93.6\%$. Furthermore, we illustrate the trade-off among the success rate, average number of queries, and average time. Particularly, we show that when the success rate is 93.6\%, it has the minimum number of queries at the same time.

Available format(s)
Public-key cryptography
Publication info
Post-quantum cryptographyand Lattice based cryptographyNTRUPublic key reuseKey mismatch attack
Contact author(s)
chengchizz @ qq com
2021-08-01: last of 2 revisions
2021-02-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaohan Zhang and Chi Cheng and Ruoyu Ding},
      title = {Small Leaks Sink a Great Ship: An Evaluation of Key Reuse Resilience of {PQC} Third Round Finalist {NTRU}-{HRSS}},
      howpublished = {Cryptology ePrint Archive, Paper 2021/168},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.