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

2014/02/24 by Xiang-Qun Fu, Wan‐Su Bao, Fu, Xiangqun +7
Computer Science · #Chaos-based Image/Signal Encryption #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1402.7032

openalex publication_date 2014/02/24 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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

Citations

• Lattice basis reduction: Improved practical algorithms and solving subset sum problems

Related

• Security Notions for Quantum Public-Key Cryptography
• New Approach for CCA2-Secure Post-Quantum Cryptosystem Using Knapsack Problem
• Quantum Algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis
• Quantum Learning Algorithms and Post-Quantum Cryptography
• Quantum Lifting for Invertible Permutations and Ideal Ciphers