Lattice Sieving With G6K

Abstract

Recent advances in quantum computing threaten the cryptography we use today. This has led to a need for new cryptographic algorithms that are safe against quantum computers. The American standardization organization NIST has now chosen four quantum-safe algorithms in their process of finding new cryptographic standards. Three out of the four algorithms are based on the hardness of finding a shortest vector in a lattice. The biggest threat to such schemes is lattice reduction. One of the best tools used for lattice reduction is the G6K framework. In this thesis, we study sieving algorithms and lattice reduction strategies implemented in G6K. After an introduction to cryptography, we go over the necessary preliminary lattice theory, important concepts, and related problems. Further, we look at lattice reduction where we study different approaches with a main focus on lattice sieving. We then explore the G6K framework, before finally performing some experiments using G6K. The results we get often depend on what type of lattice we are working on. Our experiments show that it is still possible to improve G6K for solving the shortest vector problem for some lattice types.