Post Quantum Cryptography from the Lattice Perspective

Lead Research Organisation: Royal Holloway University of London
Department Name: Information Security

Abstract

Project plans to implement cryptanalysis for lattice based post quantum cryptography, so as to determine security from a practical perspective, contribute and critique standardisation efforts, estimate the concrete resource requirements for cryptanalysis aided by quantum computers and advance the theory and understanding of secure lattice based cryptography.

Planned Impact

The most significant impact of the renewal of Royal Holloway's CDT in Cyber Security will be the production of at least 30 further PhD-level graduates. In view of the strong industry involvement in both the taught and research elements of the programme, CDT graduates are "industry-ready": through industry placements, they have exposure to real-world cyber security problems and working environments; because of the breadth of our taught programme, they gain exposure to cyber security in all its forms; through involvement of our industrial partners at all stages of the programme, the students are regularly exposed to the language and culture of industry. At the same time, they will continue to benefit from generic skills training, equipping them with a broad set of skills that will be of use in their subsequent workplaces (whether in academia, industry or government). They will also engage in PhD-level research projects that will lead to them developing deep topic-specific knowledge as well as general analytical skills.

One of the longer-term impacts of CDT research, expressed directly through research outputs, is to provide mechanisms that help to enhance confidence and trust in the on-line society for ordinary citizens, leading in turn to quality of life enhancement. CDT research has the potential of directly impacting the security of deployed system, for example helping to make the Internet a more secure place to do business. Moreover the work on the socio-technical dimensions of security and privacy also gives us the means to influence government policy to the betterment of society at large. Through the training component of the CDT, and subsequent engagement with industry, our PhD students are exposed to the widest set of cyber security issues and forced to think beyond the technical boundaries of their research. In this way, our CDT is training a generation of cyber security researchers who are equipped - philosophically as well as technically - to cope with whatever cyber security threats the future may bring. The programme equip students with skills that will enable them to understand, represent and solve complex engineering questions, skills that will have an impact in UK industry and academic long beyond the lifetime of the CDT.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/P009301/1 01/10/2016 31/12/2026
1811420 Studentship EP/P009301/1 01/10/2016 20/06/2021 Eamonn Postlethwaite
 
Description The majority of the work done under this award is concerned with "lattice sieve algorithms", which solve a problem (the "shortest vector problem") that underlies the security of cryptographic schemes built from lattices.

A key finding from this award, specifically the "The General Sieve Kernel..." paper, is that these lattice sieves are both theoretically (previously known) and practically (not previously known) the most performant class of algorithm for solving the shortest vector problem.

This, alongside the other works published under this award and many works of the wider cryptographic community, has fed into the ongoing cryptanalysis of schemes submitted to NIST's "Post Quantum Standardisation" effort, which will in turn influence much of the cryptography used by anyone browsing the internet in the future.
Exploitation Route Better, e.g. custom hardware/more heavily optimised, implementations of various lattice sieve algorithms based on the blueprint we give will further expand our understanding of which instances of lattice based cryptography can be practically attacked. This will continue to feed into holistic security analyses of cryptographic schemes based on lattices both in design and in standardisation efforts.
Sectors Digital/Communication/Information Technologies (including Software)

 
Title The General Sieve Kernel (G6K) 
Description Lattice reduction software that implements the most recent theoretical and practical advancements. 
Type Of Technology Software 
Year Produced 2019 
Open Source License? Yes  
Impact It (or variants of it) - at the time of writing - hold records for the largest instances of certain lattice reduction tasks critical to security evaluation of post quantum cryptography. It has already spurred on development of implementations on different hardware and shown the community which research directions seem to lead to the best practical performance of lattice based cryptanalytic tasks. 
URL https://eprint.iacr.org/2019/089