A (very) Brief Introduction to Lattice-Based Cryptography and the Complexity of the BKW Algorithm for Solving LWE
- 講者Robert Fitzpatrick 先生 (University of London, Royal Holloway)
邀請人:楊柏因 - 時間2012-10-02 (Tue.) 10:00 ~ 12:00
- 地點資創中心122演講廳
摘要
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.