Research On Grid-based Protocol Related Algorithms

With the rapid development of information age,information security problem is closely related to us.Thus cryptography has gradually become the focus that people increasingly concern about.The security and privacy of data elements is the core of the password techniques,and lattice reduction algorithm is the important embodiment of the core elements in cryptography.It is a kind of typical analysis technology of cryptography.At present,LLL is the most classic lattice reduction algorithm.The improved algorithms based on LLL are numerous.Their purposes are to optimize algorithms.Lattice reduction algorithm has a wide range of applications,such as number theory,an integer programming,diophantine approximation,cryptography and so on.This article mainly elaborates from the optimized algorithm for lattice reduction.Parameter initialized through lattice reduction algorithm is to solve the sphere decoding algorithm(SDA).Lattice theory is used in 0-1 integer knapsack and parallelization of knapsack algorithm.Detailed content is as follows:Firstly,lattice reduction is to solve the nonzero approximate shortest vector problem(appr-SVP)in lattice.The famous LLL algorithm can solve the provable reduction base in polynomial time.l reduction is a variant of the LLL algorithm,which has a higher quality of reduction base.However,the running time significantly increases.The effect of the block LLL is slightly inferior,but the running time obviously decreases a lot.Therefore,we put forward the thought that l reduction is added to the block LLL lattice reduction.It can effectively absorb the advantages of both,and form a relative balance algorithm of time and quality.Secondly,the sphere decoding algorithm is an effective method to solve the problem of integer least squares,and the key problem of the sphere decoding algorithm is the choice of initial radius in the search space.First,this paper puts forward that using the Hadamard ratio is to select a group of high quality base.Second,using QR decomposition,LLL optimization reduction and breadth first search algorithm(K-Best,that is BFS+PEDS)with prediction technology to reduce the selected the base.The last,reusing sphere decoding algorithm(SDA)is to find a solution.The process is equivalent to solve the Closest Vector Problem(CVP)in lattice.Thirdly,the knapsack problem is a NP-complete problem which is also a classic combinatorial optimization problem.Using the optimized reduction algorithm of above is not only to improve the efficiency of the cryptographic analysis,but also to shorten the time of password analysis.Reduction algorithm can be used in knapsack password system analysis based on lattice as well.In order to further understand the knapsack principle,the idea of the conventional algorithm is studied.Thus,for 0-1 integer knapsack problem,we put forward the parallel of a new generation algorithm to accelerate the speed of solving knapsack problem.