Tailoring LWE attacks to RLWE/MLWE and NIST standardisation

Virtually all currently used cryptosystems rely on classically hard problems such as the discrete log problem or factorisation. Both have been shown to be broken given a sufficiently large quantum computer through the utilisation of Shor's algorithm, and so the search for quantum-resistant alternatives has begun. At the centre of this is the use of believed hard lattice problems, which currently are believed to resist a quantum adversary.

In the pursuit of efficient and useful schemes, authors of such schemes have turned to structured variants of lattices in an effort to reduce the disparity in proficiency and runtime between classical schemes and their own; whilst the study of both classical and quantum algorithms for the attack of plain lattices has seen lots of attention, their more structured counterparts less so (particularly from a quantum hardness point of view).

In general, the state-of-the-art cryptanalysis of structured lattice problems is to first convert them to a standard representation, which is then attacked utilising well known and understood methods. The same is true for a quantum approach to the same issue; a classical approach broadly used, with the addition of the occasional use of quantum methods, e.g. basis reduction, but this does little to improve the overall complexity. The improvement of either of these is likely to dramatically improve current approaches to tackle practical schemes - the utilisation of both is therefore promising.

As such, I will study attacks that exploit the structured nature of lattices commonly used to construct cryptosystems from the perspective of a quantum adversary, with a focus on understanding the underlying number-theoretic structures. With this, I aim to be able to construct efficient algorithms for lattice reduction, the shortest/closest vector problem(s), or the lattice isomorphism problem that abuse/preserve the structure present, with a particular focus on the practical applications of these towards the those used in NIST standardisation candidates.

The goal of this is not to violate the security of a given scheme or the users of said scheme, but to further the understanding of these lattice problems as well as ensure that the implementations of them are trusted. In order to do so we must understand the weaknesses of a given scheme and ensure any vulnerabilities are addressed before their widespread usage to aid the NIST post quantum cryptography standardisation and these schemes' widespread adoption.
This research will be aligned with number theory and algebra, the use of which will be heavily relied upon to gain an insight into the problem described.