LWE over cyclic algebras: a novel structure for lattice cryptography
File(s)
Author(s)
Grover, Charles Everitt
Type
Thesis
Abstract
The work done in this thesis is an introduction to the use of cyclic algebras in post quantum cryptography, with a particular focus on lattice cryptography and the Learning With Errors (LWE) problem. Algebraic variants of the LWE problem are some of the most promising candidates for quantum resistant public key and signature schemes. Since different variants come with their own strengths and weaknesses, adding a version over cyclic algebras provides another flavour to study.
The first part of the thesis establishes the hardness of the Learning With Errors Over Cyclic Algebras (CLWE) problem, basing its difficulty on short vector problems over certain structured lattices in the same manner as the analogous Ring and Module LWE problems. These structured lattices are applied in cryptography for the first time.
The second part of the thesis constructs concrete families of cyclic algebras suitable for use in practice. The requirements on dimensions of ambient spaces for lattice cryptography are considered and precise cyclic algebras are constructed using a collection of novel techniques.
The final part of this thesis explains carefully how to convert the theoretical construction of the CLWE problem into a form appropriate for real world cryptography. The problem is rephrased as a discrete problem, following which an example public key cryptosystem based on the CLWE problem is built in the style of other LWE based schemes.
Overall, the thesis introduces and thoroughly justifies the construction of the CLWE problem, the first instance of non-commutative ring cryptography based on lattices, and provides the basic requirements and functionalities needed to construct cryptographic primitives in these algebras. It also leaves behind a substantial quantity of new open questions regarding the use of cyclic algebras in more intricate cryptographic constructions.
The first part of the thesis establishes the hardness of the Learning With Errors Over Cyclic Algebras (CLWE) problem, basing its difficulty on short vector problems over certain structured lattices in the same manner as the analogous Ring and Module LWE problems. These structured lattices are applied in cryptography for the first time.
The second part of the thesis constructs concrete families of cyclic algebras suitable for use in practice. The requirements on dimensions of ambient spaces for lattice cryptography are considered and precise cyclic algebras are constructed using a collection of novel techniques.
The final part of this thesis explains carefully how to convert the theoretical construction of the CLWE problem into a form appropriate for real world cryptography. The problem is rephrased as a discrete problem, following which an example public key cryptosystem based on the CLWE problem is built in the style of other LWE based schemes.
Overall, the thesis introduces and thoroughly justifies the construction of the CLWE problem, the first instance of non-commutative ring cryptography based on lattices, and provides the basic requirements and functionalities needed to construct cryptographic primitives in these algebras. It also leaves behind a substantial quantity of new open questions regarding the use of cyclic algebras in more intricate cryptographic constructions.
Version
Open Access
Date Issued
2019-11
Date Awarded
2020-06
Copyright Statement
Creative Commons Attribution NonCommercial Licence
License URL
Advisor
Ling, Cong
Sponsor
National Cyber Security Centre
Grant Number
EESB_P52328
Publisher Department
Electrical and Electronic Engineering
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)