Analysis of Lattice Reduction Algorithms : Solving SVP Challenges

Sammanfattning: Lattice-based cryptography which holds a great promise for post-quantum cryptographyis naturally concerned by lattice reduction algorithms, the essential tools in the algorithmicstudy of lattices and its applications. In order to precisely estimate the securityparameters of these cryptosystems, it is a necessity to assess the practical diculty of theshortest vector problem (SVP) by analyzing the known ecient algorithms for solvingit.In this thesis project, we revisit a recursive lattice reduction methodology going back toPlantard & Susilo's work (SCN 2010) and analyze practicality of an SVP algorithm byCheon and Lee (Cryptology ePrint Archive 2015). We show that the SVP algorithm is,in general, a theoretical progress, with little practical implications in somehow. Moreover,we have performed experimental analysis of a recent progressive BKZ algorithmproposed by Aono et al. (Eurocrypt 2016) on the Darmstadt's SVP Challenge (TUD10).From our experiments, using its open source library, we found that the simple blocksizestrategy of the algorithm is better in terms of output quality than the optimized strategy.Applying the recursive reduction methodology to the simple blocksize strategy andsome heuristics to the LLL preprocess, we have improved all of the previous records inthe SVP Challenge that are obtained by the algorithm. Moreover, our improved resultsin dimensions 117, 119 and 121 are the current best records published in the Hall ofFame of the challenge that outperformed previous records by other algorithms.