EPSRC logo

Details of Grant 

EPSRC Reference: EP/P009417/1
Title: Bit Security of Learning with Errors for Post-Quantum Cryptography and Fully Homomorphic Encryption
Principal Investigator: Albrecht, Professor M
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Information Security
Organisation: Royal Holloway, Univ of London
Scheme: First Grant - Revised 2009
Starts: 04 January 2017 Ends: 03 January 2019 Value (£): 80,215
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
09 Sep 2016 EPSRC ICT Prioritisation Panel Sep 2016 Announced
Summary on Grant Application Form
LWE can be summarised as: given a matrix `A` and a vector `b` modulo `q`, decide if `b` is uniform or if `b = A * s + e` for some small error `e`. Hence, the problem is essentially to solve a noisy linear system of equations modulo `q`. It was shown by Regev that this problem is as hard as assumed-to-be-hard problems. The problem has become a central building block of modern cryptographic constructions.

1. Modern cybersecurity relies on cryptographic algorithms such as RSA encryption and digital signatures as well as the Diffie-Hellman key exchange. It is well-known that the hard mathematical problems underlying these algorithms can be solved efficiently on a quantum computer. While the advent of quantum computers has been promised many times before, recent developments in the area have convinced many actors, especially those with a long-term security mission, to actively seek alternative algorithms which promise post-quantum security. As a result, post-quantum cryptography has recently developed from a niche area of cryptography to a mainstream concern. With the American standards body NIST announcing it would hold a competition for post-quantum proposals, the field is posed to become a central area of cryptographic research in the coming years. LWE is one of the central candidates for a hard problem withstanding attacks using quantum computers and first proposals for key exchange algorithms for Internet communication based on LWE are available.

2. Fully homomorphic encryption, the ability to compute with encrypted data, has progressed considerably since a first solution was proposed in Gentry's seminal work. The most recent generation of such schemes have become efficient enough to the point that first prototype applications, such as privacy-preserving computations with genome data, are being developed. All such constructions rely on the difficulty of solving LWE.

While it is encouraging to have Regev's proof that solving LWE is no easier than solving problems widely believed to be hard as we increase parameters, this does not settle the question of how big we should choose our parameters to provide security against real world attacks. The purpose of this project is to provide more refined answers to this question, allowing us to rely on LWE with more confidence.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: