Lattice Attacks for Variants of LWE

The learning with errors (LWE) problem introduced by Regev (STOC’05) is one of the fundamental problems in lattice-based cryptography. It has been used extensively as a security foundation, for public-key encryption, signatures, fully homomorphic encryption (FHE), pseudo-random functions (PRF) and many others. One standard strategy to solve the LWE problem is to reduce it to a unique SVP (uSVP) problem via Kannan’s embedding and then apply a lattice reduction to solve the uSVP problem. In this talk, we will discuss and compare various lattice algorithms for solving LWE, and then give some concrete estimates for breaking various variants of LWE (e.g. generic, small secrets, restricted samples). In the end, we will discuss some recent developments on algorithms for solving LWE.

[SLIDES]

Speaker Details

Shi Bai is an assistant professor in the Department of Mathematical Sciences at Florida Atlantic University. His research fields are in cryptography and computational number theory. He received his PhD degree in Computer Science from the Australian National University in 2012. He worked as postdoctoral researchers at the University of Auckland (2013-2014) and then at the Ecole Normale Superieure Lyon (2015-2016). He is currently interested in number theoretical algorithms in the cryptanalysis for lattice-based cryptography.