中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

A (very) Brief Introduction to Lattice-Based Cryptography and the Complexity of the BKW Algorithm for Solving LWE

:::

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.