Institute of Information Science Academia Sinica
Topic: A (very) Brief Introduction to Lattice-Based Cryptography and the Complexity of the BKW Algorithm for Solving LWE
Speaker: Mr. Robert Fitzpatrick (University of London, Royal Holloway)
Date: 2012-10-02 (Tue) 10:00 – 12:00
Location: Auditorium 122 at CITI Building
Host: Bo-Yin Yang


Lattice-based Cryptography is one of the most promising alternatives/replacements for traditional number-theoretic cryptography in the event of a post-quantum world. Besides resilience against quantum computers, lattice-based cryptography is also attractive for its lightweight nature, requiring only modular multiplications and additions. The Learning with Errors (LWE) problem is a learning problem to which (assumed) hard lattice problems can be reduced. The field of lattice-based cryptography is relatively young and fast-moving and, due to being a young area, precise security estimates of proposed cryptosystems are sometimes loose or absent entirely. We present a detailed complexity analysis of the adaptation of a combinatorial decoding-based algorithm (BKW) for solving LWE and give a brief comparison to the estimated complexity of alternative approaches.