Research On Quantum Algorithms For LWE Solving

Quantum computing is a rapidly emerging technology.It follows basic rules of quantum mechanics to control qubits for computation,uses quantum superposition to achieve strong parallelism,and uses interference to change the probability distribution of results,posing a threat to the modern cryptosystem based on hard problems.In this context,how to transition from existing cryptography to post-quantum cryptography has become a hot topic in scientific research.The current post-quantum cryptography can be roughly divided into several categories,such as lattice-based problems,code-based problems,hash-based digital signature protocols,and multivariable-based hard problems.This thesis mainly researches the LWE(Learning with Errors)problem,which belongs to lattice-based problems.The LPN(Learning Parity with Noise)problem is a binary domain application of LWE,which can be regarded as a kind of code-based problem.Studying LWE algorithms includes studying its special case,LPN algorithms.And it is of great theoretical and practical significance to study LWE algorithms when analyzing and evaluating the security of related cryptosystems.Based on the research and analysis for LWE algorithms,this thesis improves and explores the application of quantum learning algorithms,quantum algebraic attacks,and variational quantum algorithms in LWE solving.The main research contents are as follows:(1)There is still a lack of research on the impact of quantum learning algorithms on the security of high-dimensional LPN instances under realistic attacks,so this thesis focuses on the impact of quantum learning algorithms on practical security.The quantum learning algorithm GKZ(Grilo-Kerenidis-Zijlstra)solves LPN with quantum samples with high probability,but it cannot solve the LPN problem under the realistic quantum computing model with few quantum resources.This paper designs the initial state preparation process and improves the candidate testing method of the original GKZ.The improved quantum learning algorithm solves LPN with classical samples with lower time complexity.When attacking high-dimensional LPN instances,this paper introduces the improved quantum learning algorithm into the classical solving algorithm framework.Compared with classical LPN algorithms,the hybrid algorithm has lower space complexity and at least 1 times faster attack time.(2)At present,the quantum algorithm POSSOB(Solving Boolean Solutions of Polynomial Systems)for solving polynomial systems in the complex field has been proposed,but POSSOB cannot be directly used to solve LWE.To solve the above problem,this thesis presents a quantum algebraic attack on LWE.This paper firstly replaces the Macaulay matrix in POSSOB with the Boolean Macaulay matrix and calculates the time complexity in detail.Using the improved POSSOB algorithm,this paper proposes a quantum algorithm for solving the Max-Po SSo(Maxpolynomial System Solving)problem.Finally,this paper applies the idea of the Max-Po SSo quantum algorithm to LWE.The time complexity of the quantum attack algorithm shows that the condition number can be used as a new standard for evaluating the security of the cryptosystem based on the LWE problem.(3)This paper focuses on the attack algorithm for LWE based on the variational quantum algorithm(VQA)framework.This paper presents two solutions and estimates the number of qubits required respectively.First,from the perspective of decoding method when solving LWE,QAOA(Quantum Approximate Optimization Algorithm)is used to optimize Babai’s nearest plane algorithm.Second,from the perspective of primal method when solving LWE,VQE(Variational Quantum Eigensolver)is used to solve the u SVP(Unique Shortest Vector Problem)problem.Finally,this paper conducts small-scale simulations for the two methods,and the experimental results prove that VQA can effectively improve the quality of classical solutions.