Reduction theory of lattices and its applications to cryptography and coding theory
File(s)
Author(s)
Porter, Christian John Donald
Type
Thesis
Abstract
Lattices are fascinating mathematical structures that unify the fields of geometry and number
theory. In recent years, lattices have risen to prominence outside of pure mathematical study,
taking on a more practical application in the fields of cryptography and coding theory due to
their fine repeating structure. Intrinsic to the security of cryptosystems and the efficiency of
coding schemes based on lattices are so-called lattice problems, which, broadly speaking, ask
a user (or assailant) to describe a given lattice by a basis with “desirable” properties. Lattice
basis that fulfil these properties are said to be reduced.
In this thesis, we study a variety of topics in the field of reduction theory of lattices. Focus is
primarily placed on lattices whose structures are intricately linked to the structure of algebraic
number fields and division algebras, which have begun to be used more frequently in the fields
of cryptography and coding theory due to their compact key sizes. Our techniques vary widely,
from computing the so-called “Minkowski reduction region” of specific examples of lattices, to
deducing properties of reduced bases for general lattices and constructing algorithms to reduce
lattice bases in this manner.
theory. In recent years, lattices have risen to prominence outside of pure mathematical study,
taking on a more practical application in the fields of cryptography and coding theory due to
their fine repeating structure. Intrinsic to the security of cryptosystems and the efficiency of
coding schemes based on lattices are so-called lattice problems, which, broadly speaking, ask
a user (or assailant) to describe a given lattice by a basis with “desirable” properties. Lattice
basis that fulfil these properties are said to be reduced.
In this thesis, we study a variety of topics in the field of reduction theory of lattices. Focus is
primarily placed on lattices whose structures are intricately linked to the structure of algebraic
number fields and division algebras, which have begun to be used more frequently in the fields
of cryptography and coding theory due to their compact key sizes. Our techniques vary widely,
from computing the so-called “Minkowski reduction region” of specific examples of lattices, to
deducing properties of reduced bases for general lattices and constructing algorithms to reduce
lattice bases in this manner.
Version
Open Access
Date Issued
2022-11
Date Awarded
2023-01
Copyright Statement
Creative Commons Attribution NonCommercial Licence
Advisor
Ling, Cong
Sponsor
Engineering and Physical Sciences Research Council
Publisher Department
Electrical & Electronic Engineering
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)