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

arXiv:1402.7032

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

Xiang-Qun Fu, Wan‐Su Bao, Jianhong Shi, Fada Li, Yuchao Zhang

Published Feb 24, 2014• 0 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.1402.7032

Related papers

Quantum-based algorithm and circuit design for bounded Knapsack optimization problem

Wenjun Hou, Marek A. Perkowski

The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.

Quantum Information and Computation•Aug 1, 2020•6 citations

New Approach for CCA2-Secure Post-Quantum Cryptosystem Using Knapsack Problem

Roohallah Rastaghi

Chosen-ciphertext security, which guarantees confidentiality of encrypted messages even in the presence of a decryption oracle, has become the defacto notion of security for public-key encryption under active attack. In this manuscript, for the first time, we propose a new approach for constructing post-quantum cryptosystems secure against adaptive chosen ciphertext attack (CCA2-secure) in the standard model using the knapsack problem. The computational version of the knapsack problem is NP-hard. Thus, this problem is expected to be difficult to solve using quantum computers. Our construction is a precoding-based encryption algorithm and uses the knapsack problem to perform a permutation and pad some random fogged data to the message bits. Compared to other approaches were introduced today, our approach is very simple and more efficient.

arXiv:1211.6984•Nov 29, 2012•2 citations

Quantum mechanical algorithm to solve knapsack problem

Hao Xu, Pla Information

Knapsack problem is one of the NP complete problems.Its computational complexity is O( 2n).This paper presents the quantum mechanical algorithm based on the fixed phase quantum search to solve the knapsack problem,and the algorithm also gets probability of success at least 98% in O((N/M)~(1/2)) quantum mechanical steps( Where M is the number of matches).This quantum algorithm has higher probability of success than the algorithm based on Grover algorithm with multiple matches in the search space.

Computer Engineering and Applications Journal•Jan 1, 2009•0 citations

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

SOLVING THE 0/1-KNAPSACK PROBLEM ON QUANTUM COMPUTER

Jin Hu

The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism, quantum computer can solve many problems more efficiently. 0/1 knapsack problem is a typical NPC problem. Its computing complexity is O(2 n ) steps. This paper gives a quantum mechanical algorithm to solve 0/1 knapsack problem, which is based on Grover algorithm and quantum exponential searching algorithm. The algorithm doesn't involve any classical method to improve search efficiency and the solution can be obtained in O(c2 n2 ) steps with a probability of at least 1-12 c.

Chinese Journal of Computers•Jan 1, 1999•1 citation

Quantum computing and the security of public key cryptography

Kai Li, Pei-Gen Yan, Qing-yu Cai

Compared with electronic computers, quantum parallelism has led to a significant increase in the computing power of quantum computers.However, the computing power of quantum computers will also be limited by the laws of physics, and hence there is no doubt that the computing power of quantum computers is not unlimited.For an algorithm, we need to consider both its space complexity and time complexity.This not only requires quantum computers to achieve large-scale integration, but also requires the quantum coherence time to be sufficiently long.If either of the above two conditions is not met, the task cannot be completed.Shor's algorithm [1] reduced the computational complexity of large integer factorization to the polynomial level.This complexity is of the same order as that of the encryption and decryption for the RSA public key cryptography protocol, which leads to the insecurity of the RSA in universal quantum computing.In addition, some other quantum algorithms show different kinds of enhanced speeds for solving different problems, such as the Grover's search algorithm [2] and its improved works [ 3 , 4 ], and the HHL algorithm [5] .With the remarkable computational power of these quantum algorithms, physicists have begun to seek suitable physical systems for the implementation of quantum computing.The implementation of quantum computing includes several basic technologies, such as preparation, precise control, measurement of the physical qubits, and construction of logical qubits.At present, there are many experimental candidate quantum computing platforms, including the superconducting system [6] , trapped ions system [7] , nitrogenvacancy centers in diamonds [8] , and ultra-cold atoms [9] .Recently, Google experimentally demonstrated quantum supremacy with a superconducting quantum computer [10] , thus placing the research on quantum computing at the forefront.With the booming development of quantum computing technology, the public key cryptosystem also needs to be updated periodically.Thus, cryptographers have to constantly look for public key protocols to resist quantum computing attacks, which leads to the emergence of postquantum cryptography.It is worth noting that although the name of post-quantum cryptography contains the word 'quantum', it essentially consists of protocols of classical cryptography.The current research on post-quantum cryptography mainly includes protocols based on the following four frameworks: the protocols based on Hash function, the pro- * Corresponding author.

Fundamental Research•Jan 1, 2021•23 citations
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
The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.
Chosen-ciphertext security, which guarantees confidentiality of encrypted messages even in the presence of a decryption oracle, has become the defacto notion of security for public-key encryption under active attack. In this manuscript, for the first time, we propose a new approach for constructing post-quantum cryptosystems secure against adaptive chosen ciphertext attack (CCA2-secure) in the standard model using the knapsack problem. The computational version of the knapsack problem is NP-hard. Thus, this problem is expected to be difficult to solve using quantum computers. Our construction is a precoding-based encryption algorithm and uses the knapsack problem to perform a permutation and pad some random fogged data to the message bits. Compared to other approaches were introduced today, our approach is very simple and more efficient.
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.
The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism, quantum computer can solve many problems more efficiently. 0/1 knapsack problem is a typical NPC problem. Its computing complexity is O(2 n ) steps. This paper gives a quantum mechanical algorithm to solve 0/1 knapsack problem, which is based on Grover algorithm and quantum exponential searching algorithm. The algorithm doesn't involve any classical method to improve search efficiency and the solution can be obtained in O(c2 n2 ) steps with a probability of at least 1-12 c.
Compared with electronic computers, quantum parallelism has led to a significant increase in the computing power of quantum computers.However, the computing power of quantum computers will also be limited by the laws of physics, and hence there is no doubt that the computing power of quantum computers is not unlimited.For an algorithm, we need to consider both its space complexity and time complexity.This not only requires quantum computers to achieve large-scale integration, but also requires the quantum coherence time to be sufficiently long.If either of the above two conditions is not met, the task cannot be completed.Shor's algorithm [1] reduced the computational complexity of large integer factorization to the polynomial level.This complexity is of the same order as that of the encryption and decryption for the RSA public key cryptography protocol, which leads to the insecurity of the RSA in universal quantum computing.In addition, some other quantum algorithms show different kinds of enhanced speeds for solving different problems, such as the Grover's search algorithm [2] and its improved works [ 3 , 4 ], and the HHL algorithm [5] .With the remarkable computational power of these quantum algorithms, physicists have begun to seek suitable physical systems for the implementation of quantum computing.The implementation of quantum computing includes several basic technologies, such as preparation, precise control, measurement of the physical qubits, and construction of logical qubits.At present, there are many experimental candidate quantum computing platforms, including the superconducting system [6] , trapped ions system [7] , nitrogenvacancy centers in diamonds [8] , and ultra-cold atoms [9] .Recently, Google experimentally demonstrated quantum supremacy with a superconducting quantum computer [10] , thus placing the research on quantum computing at the forefront.With the booming development of quantum computing technology, the public key cryptosystem also needs to be updated periodically.Thus, cryptographers have to constantly look for public key protocols to resist quantum computing attacks, which leads to the emergence of postquantum cryptography.It is worth noting that although the name of post-quantum cryptography contains the word 'quantum', it essentially consists of protocols of classical cryptography.The current research on post-quantum cryptography mainly includes protocols based on the following four frameworks: the protocols based on Hash function, the pro- * Corresponding author.