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

Communications in Theoretical Physics

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

Xiang-Qun Fu, Wan‐Su Bao, Xiang 翔 Wang 汪, Jianhong Shi

Published Oct 1, 2016• 1 citation
Publisher

Abstract

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.

DOI
10.1088/0253-6102/66/4/401

Related papers

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

Hong Wang, Zhi Ma, Chuan-gui Ma

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.

Chinese Science Bulletin•Oct 1, 2013•11 citations

A quantum algorithm for searching a target solution of fixed weight

Bao Wan

To search for a target n-product Boolean of fixed weight d, we propose an important method involving the notion of a fixed-weight vector accompanied with a label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O ((Cdn+1)~(1/2)) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.

Chinese Science Bulletin•Jan 1, 2011•0 citations

A quantum algorithm for searching a target solution of fixed weight

Xiang Wang, Wan‐Su Bao, Xiang-Qun Fu

To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight “vector label” accompanied with a vector label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically $$ O\left( {\sqrt {C_{n + 1}^d } } \right) $$ , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.

Chinese Science Bulletin•Feb 1, 2011•12 citations

Quantum mechanical meet-in-the-middle search algorithm for Triple-DES

Zhong Pu

We present a quantum mechanical meet-in-the-middle search algorithm inosculating the quantum computing theory with crypt-analysis method and basing on the Grover’s algorithm and the meet-in-the-middle attack, which can solve the three-key triple-DES in O(56 256) steps and with O(256) memory cost. The computational complexity is apparently reduced, compared with that of the existing algorithms.

Chinese Science Bulletin•Jan 1, 2010•0 citations

Parameter security characterization of knapsack public-key crypto under quantum computing

Xiang-Qun Fu, Wan‐Su Bao, Jianhong Shi +2 more

In order to research the security of the knapsack problem under quantum algorithm attack, we study the quantum algorithm for knapsack problem over Z_r based on the relation between the dimension of the knapsack vector and r. First, the oracle function is designed based on the knapsack vector B and S, and the quantum algorithm for the knapsack problem over Z_r is presented. The observation probability of target state is not improved by designing unitary transform, but oracle function. Its complexity is polynomial. And its success probability depends on the relation between n and r. From the above discussion, we give the essential condition for the knapsack problem over Z_r against the existing quantum algorithm attacks, i.e. r

arXiv:1402.7032•Feb 24, 2014•0 citations

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
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.
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.
To search for a target n-product Boolean of fixed weight d, we propose an important method involving the notion of a fixed-weight vector accompanied with a label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O ((Cdn+1)~(1/2)) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.
To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight “vector label” accompanied with a vector label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O(Cn+1d) O\left( {\sqrt {C_{n + 1}^d } } \right) O(Cn+1d​​) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.
In order to research the security of the knapsack problem under quantum algorithm attack, we study the quantum algorithm for knapsack problem over Z_r based on the relation between the dimension of the knapsack vector and r. First, the oracle function is designed based on the knapsack vector B and S, and the quantum algorithm for the knapsack problem over Z_r is presented. The observation probability of target state is not improved by designing unitary transform, but oracle function. Its complexity is polynomial. And its success probability depends on the relation between n and r. From the above discussion, we give the essential condition for the knapsack problem over Z_r against the existing quantum algorithm attacks, i.e. r
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.