The Quantum Algorithm Analysis Of NTRU Cryptography And The Research Of Quantum Lattice Sieving Algorithm

Quantum computing is based on the fundamental principles of quantum mechanics,and it uses quantum superposition characteristic to show its super computing power in computational complexity,which poses a threat to the modern cryptography which is based on mathematical computational complexity.With the significant acceleration advantage of quantum computing in solving large-scale integer factorization and unstructured database search,the research on quantum security of modern cryptography is crucial to the development of cryptography.Thesis focus on the shortest vector problem in lattice problems and the quantum computing security of the corresponding lattice cryptography,which the specific contents include:1.Aiming at the quantum security problem of NTRU in product form,we design a quantum attack algorithm.Thesis applies quantum phase estimation and amplitude amplification technology to propose a modified version of Claw-Finding algorithm based on quantum walk,and uses it in NTRU public key cryptanalysis.It is proved that the modified Claw-Finding algorithm can effectively solve the NTRU private key under the condition of lower than the security parameters.Compared with the direct application of Grover algorithm to analyze NTRU,this attack scheme avoids the assumption of strong quantum Oracle and does not need to maintain an exponential list.2.Based on the quantum collision search algorithm,we propose a quantum version of lattice heuristic sieving method.Heuristic sieving method is an effect ive stochastic algorithm for solving lattice problems proposed by Nguyen and Vi dick,which is often called NV sieving method.The NV sieving method is divid ed into two parts.One is to retain the lattice points that meet the reduction condi tions,and the other is to reduce the "short vector" of the lattice points that do no t meet the conditions with a central point to achieve the sieving effect.The comp lexity of the sieving method is mainly in the search part of the second part of the central point set.Thesis presents a quantum heuristic sieving method using the c ollision search algorithm in the quantum BHT algorithm.Under the assumption that the quantum Oracle can be effectively implemented,this method reduces th e complexity of searching for the central point set in the NV sieving method,so that the time complexity of the overall algorithm is reduced from 0(200415n)to O(20.259n),where n denotes the rank of the lattice.3.Based on quantum clustering algorithm,we optimize the classical version of lattice heuristic sieving method based on K-means Local Sensitive Hashing(LSH).The K-means LSH algorithm reduces the search cost by calculating the hash value of the center point set of the heuristic sieving method,and introduces the cluster center parameter K,which makes the algorithm better balance the time and space complexity in different environments,and has better flexibility and practical value.However,the classical K-means LSH increases the time and space complexity of heuristic sieving.We present a quantum heuristic sieving method based on quantum clustering algorithm.Compared with the classical clustering algorithm,the quantum clustering algorithm has exponential acceleration effect on the parameter d of the vector dimension,and nearly quadratic acceleration effect on clustering category k.Therefore,in the case of quantum hardware device QRAM can be efficiently implemented,the heuristic sieving method based on quantum clustering algorithm not only has better flexibility,compared with the classical algorithm time complexity from O(n2)to O(n3/2),where n represents the rank of lattice.