Skip to main navigation Skip to search Skip to main content

New Result for Breaking NTRU Encryption with Multiple Keys in Polynomial Time

  • Zijian Song
  • , Jun Xu*
  • , Binwu Xiang
  • , Weijie Li
  • , Dingfeng Ye
  • *Corresponding author for this work
  • CAS - Institute of Information Engineering
  • University of Chinese Academy of Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original languageEnglish
Title of host publicationInformation and Communications Security - 26th International Conference, ICICS 2024, Proceedings
EditorsSokratis Katsikas, Christos Xenakis, Costas Lambrinoudakis, Christos Kalloniatis
PublisherSpringer Science and Business Media Deutschland GmbH
Pages25-39
Number of pages15
ISBN (Print)9789819787975
DOIs
StatePublished - 2025
Externally publishedYes
Event26th International Conference on Information and Communications Security, ICICS 2024 - Mytilene, Greece
Duration: 26 Aug 2024 → 28 Aug 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume15056 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Information and Communications Security, ICICS 2024
Country/TerritoryGreece
CityMytilene
Period26/08/24 → 28/08/24

Keywords

  • Key Recovery Attack
  • Linearization Technique
  • NTRU

Fingerprint

Dive into the research topics of 'New Result for Breaking NTRU Encryption with Multiple Keys in Polynomial Time'. Together they form a unique fingerprint.

Cite this