Basis Reduction over Algebraic Lattices

Lead Research Organisation: Imperial College London
Department Name: Electrical and Electronic Engineering


Lattices, in the geometric sense, are an infinite set of discrete points in space with a certain structure. Not only are these objects useful mathematically, but they are also of great importance for coding and cryptographic purposes. When used for the purpose of cryptography, breaking the cryptographic scheme is as hard as solving the closest vector problem (CVP), which goes as follows: "Given a lattice and a vector, which lattice point is closest to the vector?" The CVP has been well studied for geometric lattices, however research remains fruitful for generalisations of geometric lattices, such as "ideal lattices" and "module lattices" which have more of an algebraic flavour than geometric lattices. As these structures seem to be the prime candidates for practical lattice cryptosystems, it makes sense to investigate the CVP (or for ideal lattices, the shortest-generator problem) for ideal and module lattices. Certain questions will be addressed in order to further research into this field, such as recovering close integers over so-called "norm-Euclidean domains", which could be approached by analysing the problem in a geometric setting using hyperbolae at lattice points.

This research aligns with EPSRC research areas of Number theory and Theoretical Computer Science.


10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509486/1 01/10/2016 31/03/2022
2030404 Studentship EP/N509486/1 01/10/2017 31/03/2021 Christian John Porter
Description Proved that Gauss's algorithm, which is polynomial in time (fast by cryptographic standards) finds the shortest lattice vectors for two-dimensional lattices spanned over Euclidean imaginary quadratic rings. Moreover, we proved that the shortest lattice vectors form a basis for lattices of these types.
Exploitation Route Provide insight into the structure of the Minkowski region of algebraic lattice structures, and could also provide a basis on which more complicated lattices could be attacked using lattice algorithms.
Sectors Digital/Communication/Information Technologies (including Software)

Description Helps to assess the security of Lattice-based cryptosystems, an (assumedly) quantum-safe cryptography scheme which may be implemented on a large scale in the near future.