Research On Orthogonality Of Lattice Basis And Its Related Algorithms

Recently,lattice-based cryptosystem,regarded as one of the main post-quantum public-key cryptosystems,has been drawn great attention.The efficienty of the hard problems in lattices plays a decisive role in the cryptanalysis and the construction of public-key cryptography,especially based on lattices.To solve the hard problem of lattice need better algorithms and to find the better algorithms need have a profound understanding of the structure of the lattice.Therefore,it is of great significance to study the structure of lattice and the algorithms of solving hard problems in lattices.The first work of this thesis is to study the algorithm of finding the shortest vector in the lattice.We compare the different performance of different algorithms for the same matrix,including the angles between the vector and the hyperplane,the length of the base vector and their orthogonality defect.We propose a full vector-to-vector Gaussian reduction algorithm that can be used for any dimensions.This algorithm is polynomial time and can find the better basis than the other algorithm in most of the time.At the same time,we study the Gaussian algorithm and prove that if the two-dimensional lattice has an orthogonal basis,then the Gaussian algorithm outputs the orthogonal basis of the lattice.If the lattice has no orthogonal basis,the Gaussian algorithm outputs the basis which the sine value of the angle between the base vectors is the biggest.In this paper,the full vector-to-vector Gaussian algorithm is used to do the parallel design,then the parallel full vector-to-vector Gaussian algorithm is obtained.In this thesis,we propose a lattice reduction algorithm based on QR decomposition,and add one reduction condition,so that the basis that we can not be reduced by the full vector-to-vector Gaussian lattice get further reduced.Then,using the advantages of the LLL algorithm,the full vector-to-vector Gaussian algorithm and the QR decomposition algorithm,we combine them to get a hybrid algorithm,which is named as H-reduction algorithm.The basis thus obtained has the advantages of three algorithms.The second work of this thesis is to study the orthogonality and nearly orthogonality of lattice.It is described that the construction of the orthogonal basis of a rational lattice can be reduced to the construction of the orthogonal basis of some integer lattices,and the sufficient conditions for the existence of the orthogonal basis of the integer lattice are given.For a two-dimensional integer lattice,the existence criterion of the orthogonal lattice is given,and some properties of the nearly orthogonal lattice are discussed.The relationship between the Minkowski reduction basis and the nearly orthogonal lattice is discussed.We prove that the two-dimensional lattice must have a?/3 orthogonal basis,We prove that the angle between any two Minkowski-reduced basis vectors is more than ?/3;if the orthogonal defect of 3-dimension lattice is less than 2/3^1/2,the Minkowski-reduced basis of the lattice is?/3-orthogonal;if a weakly?-orthogonal basis for a lattice with ?/3 has been ordered by the Euclidean norm of the vectors,and the minimum length ratio maximum length is more than 2cos?,the basis is Minkowski reduced.We improve an algorithm used in JPEG CHEst by changing it from heuristic one to deterministic one,furthermore we add a constraint to reduce the number of unimodular matrix that need to determine.Since not every lattice has an orthogonal basis,we try to measure its orthogonal by its sublattice.It can be proved that there exist full-rank orthogonal sub-lattices for every rational lattice.In this thesis,we define the minimal indices of the orthogonal sub-lattices.For a two-dimensional lattice,the abundant and essential condition for the existence of the orthogonal sub-lattice is given.We study the minimal indices of the orthogonal sub-lattices for some important rational lattices,including the root lattices A_n,D_n,E₆,E₇,E₈,Barnes-Wall lattice?₁₆ and Leech lattice ?₂₄.They are all important objects in several areas of mathematics,such as the number of geometry,Lie algebra and group theory,etc.This is the third work of the thesis.The fourth work of this thesis is to study the probability distribution of SVP solutions of the cyclic generation lattice in low-dimensional case.Solving SVP solution is difficult,we begin to study the special lattice.The cyclic generation lattice is a very special kind of lattice,which is the lattice of the cyclic matrix.Due to the particularity of the lattice,the shortest vector also exhibits a special property when the dimension is low.For general lattice,the bound for the basis integer coefficient of the shortest lattice vector is exponentially large,while the bound for the integer coefficient of SVP under its cyclic basis would be really small;the probability of the shortest vector's coefficients for the low-dimensional cyclic generated lattice is discussed.It implies that SVP over these lattices within constant steps can be solved.This offers a new method to design a a more effective algorithm to solve the SVP in the cyclic generated lattice.