Institute of Information Science, Academia Sinica

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.