Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chinese Science Bulletin

An efficient quantum meet-in-the-middle attack against NTRU-2005

Hong Wang, Zhi Ma, Chuan-gui Ma

Published Oct 1, 2013• 11 citations
Publisher

Abstract

NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic. This paper proposes a new way to find NTRU-2005 private key. The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target. Compared with the current classical and quantum meet-in-the-middle attacks, our algorithm has lower time and space complexity. Moreover, this attack can also be applied against different versions of NTRU. The result can help to understand the security of NTRU better.

DOI
10.1007/s11434-013-6020-y

Related papers

General Quantum Meet-in-the-Middle Search Algorithm Based on Target Solution of Fixed Weight*

Xiang-Qun Fu, Wan‐Su Bao, Xiang 翔 Wang 汪 +1 more

Abstract Similar to the classical meet-in-the-middle algorithm, the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm. Aiming at the target vector of fixed weight, based on the quantum meet-in-the-middle algorithm, the algorithm for searching all n-product vectors with the same weight is presented, whose complexity is better than the exhaustive search algorithm. And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm. Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d, we present a general quantum meet-in-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight, the computational complexity of the algorithm is lower. And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.

Communications in Theoretical Physics•Oct 1, 2016•1 citation

Improved quantum differential Meet-In-The-Middle attack and some applications

Jichen Wei, Jian Xiao Zou, Rongwei Lin

To enhance the efficiency of the quantum differential Meet-In-The-Middle attack, an improved scheme based on quantum collision search is proposed. The traditional quantum search steps were replaced with Ambainis’ quantum collision search algorithm. This replacement optimized the matching process between candidate keys and plaintexts in the Meet-in-the-Middle phase and significantly reduced time complexity. The improved attack scheme is applied to PIPO-128, SKINNY-128-384, and AES-256, achieving key recovery attacks for 8, 23, and 12 rounds, respectively. Analysis results under both Q1 and Q2 models demonstrate that the proposed scheme outperforms existing classical and quantum attacks in both time and memory complexity, validating its effectiveness and superiority in cryptanalysis.

International Conference on Communication and Network Security (ICCNS)•Dec 19, 2025•0 citations

NTRU cryptosystem a solution to the quantum threat

Guiot Cusidó, Miquel, Guitart Morales, Xavier

Most of the current public key cryptosystems’ security is based on the integer factorization and the discrete logarithm, which are mathematical problems that are considered difficult to solve. However, the publication in 1994 of the Shor’s algorithm [1] was a major setback for the world of cryptography, since it provided a quantum algorithm capable of solving efficiently these mathematical problems. Therefore, in recent years many governments and technology companies have put a lot of effort into developing what is known as post-quantum cryptography, i.e. the science that studies cryptosystems that are resistant to quantum attacks. Along these lines, in 2016 the National Institute of Standards & Technology launched a competition with the aim of establishing and standardising the best performing post-quantum cryptosystems, being the NTRU (Nth Degree Truncated polynomial Ring Units) cryptosystem one of the candidates still on the table. The aim of this project is to study the quantum-resistant cryptosystem NTRU, both from a theoretical and practical point of view. Firstly, the mathematical results on which it is based are presented and the existing attacks against it are analyzed. Finally, a practical implementation of the cryptosystem and four of its attack is carried out, from which experimental results are extracted.

•May 1, 2023•0 citations

The Impact of Quantum Search Algorithms on NTRU Cryptosystem

JunYao, GuihuaZeng, FuchenZhu

Lattice-based cryptosystems rely on certain lattice problems for their socurity, such as the shortest vector and the closest vector probtems. NTRU is a kind of lattice based public key cryptosysytem gaining much attention because of its high efficiency. Its encryption and decryption use a mixing system suggested by polynomial algebra combined with a clustering principle based on elementary probability theory. With the availability of quantum computers, the security of cryptosystems based on classical mathematic problems needs to be reevaluated. Since lattice reduction is the main threat to lattice-based cryptosystems, lattice reduction using quantum search algorithms are analyzed to evaluate the security of NTRU in this paper. According to our results, original security paratneters proposed for NTRU should be increased in the event that Grover's quantum search algorithm is used for lattice reduction.

信息安全与通信保密•Jan 1, 2005•0 citations

Quantum Differential Meet‐In‐The‐Middle Attack and Some Applications to Lightweight Ciphers

Yinsong Xu, Bin‐Bin Cai, Zheng Yuan +3 more

Abstract At CRYPTO 2023, Boura et al. proposed a new cryptanalysis technique, differential meet‐in‐the‐middle (MITM) attack. They used MITM technique to make the key recovery step of a differential attack more efficient. In this study, a quantum differential meet‐in‐the‐middle attack is proposed by using nested quantum search algorithm, which can achieve up to a quadratic speed‐up compared to the classical version. Besides, the time complexity of the attack can be reduced by at least a factor of ( is the guessed key length and is the block size) compared to the first quantum differential attack proposed by Kaplan et al. at ToSC 2016. Finally, to demonstrate the efficiency of our attack, it is applied to two reduced‐round lightweight block ciphers, PIPO and SIMON , to evaluate their post‐quantum security. When attacking the same number of rounds, the time complexity of our attack is significantly lower than that of classical attacks. For the 8‐round PIPO‐128 , the attack significantly improves efficiency, reducing the time complexity from to , cutting down the required qRAM size by a factor of and obtaining the data complexity instead of compared to the best quantum attack proposed by Schrottenloher at CRYPTO 2023. For the 19‐round SIMON‐32‐64 , the time complexity here will be instead of compared to the other quantum attack, and the attack can target more rounds than using Grover‐meets‐Simon technique.

Advanced Quantum Technologies•Aug 7, 2024•6 citations

Quantum polynomial-time fixed-point attack for RSA

Yahui Wang, Huanguo Zhang, Houzhen Wang

Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a well-known factoring algorithm by finding the prime factors of a number n = pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd(ar/2± 1, n) = p or q. For odd values of r it is assumed that the factors of n cannot be found (since ar/2is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ(r)/π2r, exceeding that of the existing quantum algorithm for attacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.

China Communications•Feb 1, 2018•38 citations
NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic. This paper proposes a new way to find NTRU-2005 private key. The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target. Compared with the current classical and quantum meet-in-the-middle attacks, our algorithm has lower time and space complexity. Moreover, this attack can also be applied against different versions of NTRU. The result can help to understand the security of NTRU better.
Abstract Similar to the classical meet-in-the-middle algorithm, the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm. Aiming at the target vector of fixed weight, based on the quantum meet-in-the-middle algorithm, the algorithm for searching all n-product vectors with the same weight is presented, whose complexity is better than the exhaustive search algorithm. And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm. Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d, we present a general quantum meet-in-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight, the computational complexity of the algorithm is lower. And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.
To enhance the efficiency of the quantum differential Meet-In-The-Middle attack, an improved scheme based on quantum collision search is proposed. The traditional quantum search steps were replaced with Ambainis’ quantum collision search algorithm. This replacement optimized the matching process between candidate keys and plaintexts in the Meet-in-the-Middle phase and significantly reduced time complexity. The improved attack scheme is applied to PIPO-128, SKINNY-128-384, and AES-256, achieving key recovery attacks for 8, 23, and 12 rounds, respectively. Analysis results under both Q1 and Q2 models demonstrate that the proposed scheme outperforms existing classical and quantum attacks in both time and memory complexity, validating its effectiveness and superiority in cryptanalysis.
Most of the current public key cryptosystems’ security is based on the integer factorization and the discrete logarithm, which are mathematical problems that are considered difficult to solve. However, the publication in 1994 of the Shor’s algorithm [1] was a major setback for the world of cryptography, since it provided a quantum algorithm capable of solving efficiently these mathematical problems. Therefore, in recent years many governments and technology companies have put a lot of effort into developing what is known as post-quantum cryptography, i.e. the science that studies cryptosystems that are resistant to quantum attacks. Along these lines, in 2016 the National Institute of Standards & Technology launched a competition with the aim of establishing and standardising the best performing post-quantum cryptosystems, being the NTRU (Nth Degree Truncated polynomial Ring Units) cryptosystem one of the candidates still on the table. The aim of this project is to study the quantum-resistant cryptosystem NTRU, both from a theoretical and practical point of view. Firstly, the mathematical results on which it is based are presented and the existing attacks against it are analyzed. Finally, a practical implementation of the cryptosystem and four of its attack is carried out, from which experimental results are extracted.
Lattice-based cryptosystems rely on certain lattice problems for their socurity, such as the shortest vector and the closest vector probtems. NTRU is a kind of lattice based public key cryptosysytem gaining much attention because of its high efficiency. Its encryption and decryption use a mixing system suggested by polynomial algebra combined with a clustering principle based on elementary probability theory. With the availability of quantum computers, the security of cryptosystems based on classical mathematic problems needs to be reevaluated. Since lattice reduction is the main threat to lattice-based cryptosystems, lattice reduction using quantum search algorithms are analyzed to evaluate the security of NTRU in this paper. According to our results, original security paratneters proposed for NTRU should be increased in the event that Grover's quantum search algorithm is used for lattice reduction.
Abstract At CRYPTO 2023, Boura et al. proposed a new cryptanalysis technique, differential meet‐in‐the‐middle (MITM) attack. They used MITM technique to make the key recovery step of a differential attack more efficient. In this study, a quantum differential meet‐in‐the‐middle attack is proposed by using nested quantum search algorithm, which can achieve up to a quadratic speed‐up compared to the classical version. Besides, the time complexity of the attack can be reduced by at least a factor of ( is the guessed key length and is the block size) compared to the first quantum differential attack proposed by Kaplan et al. at ToSC 2016. Finally, to demonstrate the efficiency of our attack, it is applied to two reduced‐round lightweight block ciphers, PIPO and SIMON , to evaluate their post‐quantum security. When attacking the same number of rounds, the time complexity of our attack is significantly lower than that of classical attacks. For the 8‐round PIPO‐128 , the attack significantly improves efficiency, reducing the time complexity from to , cutting down the required qRAM size by a factor of and obtaining the data complexity instead of compared to the best quantum attack proposed by Schrottenloher at CRYPTO 2023. For the 19‐round SIMON‐32‐64 , the time complexity here will be instead of compared to the other quantum attack, and the attack can target more rounds than using Grover‐meets‐Simon technique.
Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a well-known factoring algorithm by finding the prime factors of a number n = pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd(ar/2± 1, n) = p or q. For odd values of r it is assumed that the factors of n cannot be found (since ar/2is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ(r)/π2r, exceeding that of the existing quantum algorithm for attacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.