On the use of cyclic algebras in lattice-based cryptography
File(s)
Author(s)
Mendelsohn, Andrew
Type
Thesis
Abstract
This thesis studies the role of cyclic algebras in lattice-based cryptography. It analyses the security of the mathematical problems underlying a public key encryption (PKE) scheme called CLWE, a variant of Learning with Errors defined over cyclic division algebras (CDAs), obtaining a clearer picture of its security level. This includes relating CLWE to a new module variant of CLWE, and also relating CLWE to ideal lattice problems obtained from one-sided ideals in the natural order of certain CDAs. It then studies three variants of CLWE, corresponding to different parameter choices in the construction of the algebras. These include CDAs which are central over cyclotomic fields of arbitrary conductor, CDAs with fractional non-norm element, and nonassociative CDAs with non-norm element lying in the ring of integers of the maximal subfield of the algebra. This latter (nonassociative) variant is notable for permitting a full search-to-decision reduction for the CLWE problems obtained, for well-chosen moduli. It then turns to a second PKE scheme, based on group rings, called GRLWE, and proposes an attack on the scheme via a transformation which turns samples from the group rings used into samples from structurally-weak cyclic algebras, whose weakness can be cryptographically exploited. A patch is then proposed by replacing the original choice of integral dihedral group rings with integral generalised quaternionic group rings. Finally, it defines a new provably-secure variant of NTRUEncrypt in quaternion algebras, and demonstrates the IND-CPA security of the scheme in algebras of bounded discriminant, via a proof that the distribution of the public keys in the scheme is indistinguishable from uniform, assuming the hardness of CLWE.
Version
Open Access
Date Issued
2023-09-15
Date Awarded
01/01/2024
License URL
Advisor
Ling, Cong
Sponsor
Academic Centres of Excellence in Cyber Security Research
Publisher Department
Electrical and Electronic Engineering
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)