Notes on the generalized Gauss reduction algorithm

Abstract

The hypothetical possibility of building a quantum computer in the near future has forced a revision of the foundations of modern cryptography. The fact is that many difficult algorithmic problems, such as the discrete logarithm, factoring a (large) natural number into prime factors, etc., on the complexity of which many cryptographic protocols are based these days, have turned out to be relatively easy to solve using quantum algorithms.
          Intensive research is currently underway to find problems that are difficult even for a quantum computer and have potential applications for cryptographic protocols. Our article contains notes related to the so-called generalized Gauss algorithm, which calculates the reduced basis of a twodimensional lattice [8], [2]. Note that researchers are increasingly putting forward difficult algorithmic problems from lattice theory as candidates for the foundation of post-quantum cryptography. The majority of algorithmic problems related to lattice reduction become NP-hard as the lattice dimension increases [3], [1]. Fundamental problems such as the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), and Bounded Distance Decoding (BDD) are conjectured to remain hard even for quantum algorithms [4], [6]. Although the generalized Gauss reduction algorithm applies to two-dimensional lattices, where exact analysis is feasible (dimensions 3 and 4 are studied in [7], [5]), understanding such low-dimensional reductions provides important insights into the structure and complexity of lattice-based cryptographic constructions.