EPSRC Reference: 
EP/P009417/1 
Title: 
Bit Security of Learning with Errors for PostQuantum Cryptography and Fully Homomorphic Encryption 
Principal Investigator: 
Albrecht, Professor M 
Other Investigators: 

Researcher CoInvestigators: 

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 Date  Panel Name  Outcome 
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 assumedtobehard 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 DiffieHellman key exchange. It is wellknown 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 longterm security mission, to actively seek alternative algorithms which promise postquantum security. As a result, postquantum 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 postquantum 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 privacypreserving 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 nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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: 
