Modular Form Approach To Solving Extreme Lattice Problems And Its Application

We constmct new randomized algorithms to find the exact solutions to the shortest and closest vector problems(SVP and CVP)in Euclfdean norm(12)for integral lattices.Not only the minimal12.norm of non-zero lattice vectors in SVP and the minimal I2-distance in CVP, but also how many lattice vectors reach those minimums can be simultaneously computed by the algorithms.Such function’s modular properties are exploited to develop our SVP and CVP solvers.In computational complexity perspective and take our SVP solver as an example,for the integral lattice family{An} of dimension dimAn=n and level hn=1(an)(the minimal positive integer such that the dual lattice scaled by h1n/2is integral)polynomial in n,this algorithm can find the minimal12.norm of non-zero lattice vectors and the number of such shortest vectors in n with success probability1-ε in the asymptotic space-complexity of polynomial in n and asymptotic time-complexity of (loglog(n2hn))o(n)log(1/ε).In addition,the only contribution to the algorithm’s exponential time complexity (loglog(n2hn))o(n)log(1/ε)comes from independently repeating a randomized lattice vector sampler((loglog(n2hn))o(n)log(1/ε)times.All the rest of operations contribute to the algorithm’s time-complexity only with an additive pilynomial in n.Similar situations occur when soloving the exact CVP by our algorithm.Based on the construction of two operators and intersection calculations for the relational database,the main method is to use an anonymous public key encryption scheme and zero-knowledge proof protocol.Currently known for the two security solution efficiency construction method is the use of lattice problems and extreme complexity.The results of modular form approach to solving extreme lattice problems provide a guarantee for extreme kinds of security methods.