TY - GEN
T1 - New Result for Breaking NTRU Encryption with Multiple Keys in Polynomial Time
AU - Song, Zijian
AU - Xu, Jun
AU - Xiang, Binwu
AU - Li, Weijie
AU - Ye, Dingfeng
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
PY - 2025
Y1 - 2025
N2 - The initial NTRU problem was generally recognised to be intractable, followed by several variants such as the multi-key NTRU problem. Briefly, the problem refers to one generating multiple instances of NTRU public keys hi = fi/g from the same denominato g and different fi, the task is to recover private keys g (thus fi) through these public key instances hi. At DCC 2023, Kim et al. proposed the first polynomial time algorithm to solve this problem, which requires N instances in ring Z[x]/(xN-1). We point out the weaknesses of Kim’s work, that is, the algorithm fails to work due to the impossibility of constructing equations with full rank. Moreover, even with more instances than N, the algorithm is unable to work. Then we propose a new polynomial time algorithm using linearization technique that requires half the number of instances, i.e., ⌈ N/2 ⌉+1.WiththesameparametersasintheworkofKimetal.,the time required in the phase of solving equations is only tens of seconds, which indicates that our algorithm is efficient and practical.
AB - The initial NTRU problem was generally recognised to be intractable, followed by several variants such as the multi-key NTRU problem. Briefly, the problem refers to one generating multiple instances of NTRU public keys hi = fi/g from the same denominato g and different fi, the task is to recover private keys g (thus fi) through these public key instances hi. At DCC 2023, Kim et al. proposed the first polynomial time algorithm to solve this problem, which requires N instances in ring Z[x]/(xN-1). We point out the weaknesses of Kim’s work, that is, the algorithm fails to work due to the impossibility of constructing equations with full rank. Moreover, even with more instances than N, the algorithm is unable to work. Then we propose a new polynomial time algorithm using linearization technique that requires half the number of instances, i.e., ⌈ N/2 ⌉+1.WiththesameparametersasintheworkofKimetal.,the time required in the phase of solving equations is only tens of seconds, which indicates that our algorithm is efficient and practical.
KW - Key Recovery Attack
KW - Linearization Technique
KW - NTRU
UR - https://www.scopus.com/pages/publications/85215566581
U2 - 10.1007/978-981-97-8798-2_2
DO - 10.1007/978-981-97-8798-2_2
M3 - 会议稿件
AN - SCOPUS:85215566581
SN - 9789819787975
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 25
EP - 39
BT - Information and Communications Security - 26th International Conference, ICICS 2024, Proceedings
A2 - Katsikas, Sokratis
A2 - Xenakis, Christos
A2 - Lambrinoudakis, Costas
A2 - Kalloniatis, Christos
PB - Springer Science and Business Media Deutschland GmbH
T2 - 26th International Conference on Information and Communications Security, ICICS 2024
Y2 - 26 August 2024 through 28 August 2024
ER -