TY - GEN
T1 - An Improved Practical Key Mismatch Attack Against NTRU
AU - Liu, Zhen
AU - Vishakha,
AU - Ding, Jintai
AU - Cheng, Chi
AU - Pan, Yanbin
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - NTRU is a very famous lattice-based public key cryptosystem, whose security has undergone analysis for the past two decades. Hoffstein, Pipher and Silverman firstly proposed a key recovery attack against the original NTRU with a key mismatch oracle that helps to determine whether the ciphertext can be decrypted correctly or not. However, some additional assumptions are needed to make their attack work. In this paper, we present a key mismatch attack against NTRU that eliminates these assumptions. Using polynomials with coefficients satisfying a fixed ℓ1 norm to construct ciphertexts, we can keep recovering the coefficients of consecutive positions until the private key is fully recovered. In our experiment, we always succeeded to recover the private keys of NTRUEncrypt and NTRU-HPS with the recommended parameters, which were submitted to the NIST Post-Quantum Cryptography Standardization. Above all, regrading NTRU, our attack has the minimum number of queries to the oracle so far, which is also closest to the theoretical lower bound on the minimum average number of queries analyzed in Qin et al.’s work at Asiacrypt 2021.
AB - NTRU is a very famous lattice-based public key cryptosystem, whose security has undergone analysis for the past two decades. Hoffstein, Pipher and Silverman firstly proposed a key recovery attack against the original NTRU with a key mismatch oracle that helps to determine whether the ciphertext can be decrypted correctly or not. However, some additional assumptions are needed to make their attack work. In this paper, we present a key mismatch attack against NTRU that eliminates these assumptions. Using polynomials with coefficients satisfying a fixed ℓ1 norm to construct ciphertexts, we can keep recovering the coefficients of consecutive positions until the private key is fully recovered. In our experiment, we always succeeded to recover the private keys of NTRUEncrypt and NTRU-HPS with the recommended parameters, which were submitted to the NIST Post-Quantum Cryptography Standardization. Above all, regrading NTRU, our attack has the minimum number of queries to the oracle so far, which is also closest to the theoretical lower bound on the minimum average number of queries analyzed in Qin et al.’s work at Asiacrypt 2021.
KW - NTRU
KW - decryption failure
KW - key mismatch attack
KW - key recovery
UR - http://www.scopus.com/inward/record.url?scp=85197241845&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-62743-9_11
DO - 10.1007/978-3-031-62743-9_11
M3 - Conference Proceeding
AN - SCOPUS:85197241845
SN - 9783031627422
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 322
EP - 342
BT - Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings
A2 - Saarinen, Markku-Juhani
A2 - Smith-Tone, Daniel
A2 - Smith-Tone, Daniel
PB - Springer Science and Business Media Deutschland GmbH
T2 - 15th International Conference on Post-Quantum Cryptography, PQCrypto 2024
Y2 - 12 June 2024 through 14 June 2024
ER -