Reduction Theory of Algebraic Modules and their Successive Minima
This work addresses a gap in reduction theory for algebraic modules, relevant to cryptography and coding theory, but is incremental as it extends existing reduction concepts to a new algebraic setting.
The paper tackles the problem of generalizing classical lattice reduction notions (Minkowski, HKZ, BKZ) to free modules over algebraic orders, avoiding embedding distortions, and shows that HKZ reduced bases have vector lengths polynomially close to the successive minima in terms of module dimension.
Lattices defined as modules over algebraic rings or orders have garnered interest recently, particularly in the fields of cryptography and coding theory. Whilst there exist many attempts to generalise the conditions for LLL reduction to such lattices, there do not seem to be any attempts so far to generalise stronger notions of reduction such as Minkowski, HKZ and BKZ reduction. Moreover, most lattice reduction methods for modules over algebraic rings involve applying traditional techniques to the embedding of the module into real space, which distorts the structure of the algebra. In this paper, we generalise some classical notions of reduction theory to that of free modules defined over an order. Moreover, we extend the definitions of Minkowski, HKZ and BKZ reduction to that of such modules and show that bases reduced in this manner have vector lengths that can be bounded above by the successive minima of the lattice multiplied by a constant that depends on the algebra and the dimension of the module. In particular, we show that HKZ reduced bases are polynomially close to the successive minima of the lattice in terms of the module dimension. None of our definitions require the module to be embedded and thus preserve the structure of the module.