Research in Lattice-Based Cryptography

Current cryptosystems are based on computationally difficult problems such as factorisation and the discrete logarithm problem. However, recent advances in the development of quantum computers threaten these existing schemes which protect data, communications, and form the backbone of many, if not all, online processes, such as digital transactions. As such, research into post-quantum cryptography has become increasingly active and relevant. Post-quantum cryptography involves the construction and analysis of new cryptographic primitives that are difficult enough that a quantum computer cannot solve them easily and are therefore secure against quantum attacks.

There are several candidate problems for making post-quantum cryptography secure enough against quantum computers. One class of these are lattice problems, such as finding the shortest vector in a lattice. A lattice is the set of all integer linear combinations of its basis vectors. Multiple bases can represent the same lattice, and lattice-based cryptography uses this fact to its advantage. Often, breaking a lattice-based cryptosystem requires finding vectors which are close to a certain target or finding short vectors, which is difficult without some secret knowledge. This secret knowledge could be a "good" basis, a basis containing short vectors, which makes the problem easier to solve. However, this secret information is protected by the fact that it is hard to recover it.

The project aims to investigate a lattice problem known as the Lattice Isomorphism Problem, which has not yet gotten as much attention as others. This problem's hardness comes from the nontrivial task of distinguishing if two lattices are isomorphic, or in other words, similar in structure and properties. If an attacker knew the transformation which relates two lattices to each other, any schemes using this problem would easily be broken. However, it is believed that finding this transformation or even just deciding if two lattices are isomorphic is difficult even for quantum computers.

Particularly, this problem is looked at in the context of signature schemes. The advantages of a signature scheme using the Lattice Isomorphism Problem is simplicity compared to signature schemes using different lattice problems, but there is still much to be done to improve its efficiency and test its security. To achieve these goals, the approaches used in this project will be mathematical, borrowing methods from number theory, coding theory, probability theory, and algorithmic analysis. The novelty of this research will come from the combination of techniques used to improve important algorithms in the signature scheme.

This project aligns with EPSRC's research in information and communications technologies, as well as number theory and mathematical sciences which the methods used to analyse the security of lattice-based cryptographic schemes rely heavily on.