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

活動訊息

友善列印

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

Combinatorial Algorithms for LWE-type Problems

:::

Combinatorial Algorithms for LWE-type Problems

  • 講者Robert Fitzpatrick 博士 (London University at Royal Holloway)
    邀請人:楊柏因
  • 時間2013-04-17 (Wed.) 16:00 ~ 17:00
  • 地點資訊所新館106演講廳
摘要

The hardness of the Learning with Errors (LWE) problem is usually considered solely from a lattice-reduction perspective. While lattice-reduction approaches appear to be most competitive, understanding of running-times for BKZ (and other basis-reduction algorithms) leaves much to be desired. In this talk, we give an outline of the main combinatorial methods for solving the LWE problem. While uncompetitive at present, these methods have the practical advantage that their running-times are relatively straightforward to deduce. We then give an example of an application of such a method to an LWE-type scheme proposed at PKC '12, illustrating that such approaches can perform in the `real world'. Finally, we highlight a connection to the recent result of Brakerski, Langlois, Peikert, Regev and Stehle on the classical hardness of LWE.