On Learning With Errors From Non-Associative Cyclic Division Algebras

Malikov, Valeriy (2026) On Learning With Errors From Non-Associative Cyclic Division Algebras. Master's Thesis / Essay, Mathematics.

Preview

Text mMA2026MalikovV.pdf Download (704kB) | Preview

Abstract

Lattice-based cryptography is a leading candidate for post-quantum security, with much recent work introducing algebraic structure into the Learning With Errors (LWE) problem to improve efficiency, progressing from LWE to its ring, module, and cyclic-algebra variants (RLWE, MLWE, CLWE). This thesis studies Non-Associative Cyclic LWE (NCLWE), which replaces CLWE’s associative cyclic algebra with a non-associative one, removing a secret-space restriction inherent to CLWE while saving a storage factor of d over MLWE. We recall and expand on the algebraic theory needed to work with non-associative cyclic division algebras and give explicit number field constructions suitable for instantiating NCLWE. We then study the public-key encryption scheme proposed for NCLWE in the degree 2 setting, correcting a perceived error in its original correctness proof, and show that the non-multiplicativity of its matrix representation forces d encryptions per message for an algebra of degree d, undermining the efficiency gains motivating the construction. Finally, we prove that for d ≥ 3, no non-associative cyclic algebra admits the structure required by the degree 2 scheme’s security proof, ruling out this construction strategy at higher degree.

Item Type:	Thesis (Master's Thesis / Essay)
Supervisor name:	Top, J.
Degree programme:	Mathematics
Thesis type:	Master's Thesis / Essay
Language:	English
Date Deposited:	16 Jul 2026 14:27
Last Modified:	16 Jul 2026 14:27
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/37439

Actions (login required)

View Item