Hard Problems In Lattice-based Cryptosystems

With the rapid development of computers and internet, the security of commu-nication becomes an important issue; as the key technology of information security,cryptography attracts the attention of the academic community.Nowadays, lattice-based cryptography is a very trendy topic, which has a poten-tial to resist quantum computer attacks. Hard problems in lattice, design and analysisof lattice-based cryptographic algorithms become the core of public-key cryptogra-phy. On the one hand, as a new type of cryptosystems, the security of lattice-basedcryptography relies on solving the hard problems in lattice. On the other hand, latticealgorithms have arguably emerged as the most popular tool in public-key cryptanalysis.A number of efcient attacks on many popular schemes are based on lattice algorithms.Therefore, the research on algorithms of hard problems in lattice is of important sig-nificance in both theory and practice.In this dissertation, we mainly focus on the algorithms for the shortest vectorproblem and LWE problem.First, we present a new heuristic randomized sieve for shortest vector prob-lem in general lattices. The algorithm needs20.3836npolynomial time operations and20.2557n+o（n）space. It is an improvement of the Nguyen-Vidick heuristic sieve. We in-troduce a new sieve technique （two-level sieve instead of the previous one-level sieve）to reduce the time complexity and achieve some balance between time and space. Thecomplexity estimation is based on calculating the irregular spherical cap covering. Sec-ond, we propose a reduced-dimension algorithm for the shortest vector problem of lat-tice with gaps among successive minima. This algorithm first collects sufciently manyshort vectors by modifying List-birthday sieve to an approximate SVP algorithm. Next,after constructing sublattices by these short vectors, the shortest vector in the originallattice can be found by solving the SVP problems in these sublattices. In addition, aλ2-gap estimation of LWE lattice with cryptographic significance is given. Further- more, we analyze the efciency of the attack on LWE by finding the shortest vectorin embedding lattice. For some parameters, a better reduction from BDD to uSVP isobtained in the presence of largerλ2-gap.The Learning with Errors （LWE） problem is a major tool in lattice-based cryptog-raphy, because it allows to build provably-secure encryption schemes based on worst-case lattice problems. It is therefore important to know what are the best attacks onLWE. At CT-RSA’11, Lindner and Peikert presented a simple variant of Babai’s near-est plane algorithm, which was claimed to be the best attack on LWE in practice. First,we present a simple randomized variant of the algorithm, which already provides sub-stantial speedups, e.g.2³²for certain parameters. Next, we show that further speedupscan be obtained by adapting the extreme pruning technique of Gama, Nguyen andRegev （EUROCRYPT’10） to LWE. Our speedups are theoretically exponential.