报告题目：Slide reduction, revisited—filling the gaps in svp approximation

报告人：李建伟 Research fellow

主持人：曹珍富 教授

报告时间：3月22日16:00-17:00

报告地点：理科大楼B1002（线上讲座，现场参加）

报告摘要：

Lattice reduction is a key tool in cryptanalysis at large, and is of course a central interest for the cryptanalysis of lattice-based cryptography. In this talk, we present how to generalize Gama and Nguyen’s slide reduction algorithm [STOC ’08] for solving the approximate Shortest Vector Problem over lattices (SVP) to allow for arbitrary block sizes, rather than just block sizes that divide the rank n of the lattice. This leads to significantly better running times for most approximation factors. We also show a different algorithm that works when the block size is quite large—at least half the total rank. This yields the first non-trivial algorithm for sublinear approximation factors.

报告人简介：

李建伟 (Jianwei Li ), Research fellow at Department of Information Security，Royal Holloway University of London。

2010年本科毕业于吉林大学数学与应用数学系。2015年博士毕业于清华大学高等研究院，导师王小云院士，合作导师Phong Q. Nguyen 教授(巴黎高师)。2015年至2019年期间先后在中国科学院国家数学与交叉科学中心和新加坡国立大学量子技术中心从事博士后研究工作。

主要研究兴趣为计算数论，尤其是格上算法问题和格密码分析。

作为主要贡献者，近三年来的主要研究成果有：

1. 设计了当前理论上最好的格基提取算法和正定二次型提取算法:

Jianwei Li, Phong Q. Nguyen. Computing a Lattice Basis Revisited. ISSAC 2019.

2. 发现了当前理论上最好的格基约化算法(包括第一个次线性近似因子的格基约化算法):

Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz. Slide Reduction, Revisited -- Filling the Gaps in SVP Approximation. CRYPTO 2020.

3. 历经五年的努力，首次给出了被视为格基密码分析中心工具的BKZ算法(Claus-Peter Schnorr and M. Euchner 1991; citations 1698)的worst-case分析，从而解决了这一长达近30年的公开难题。比如，去年加州大学伯克利分校Simons Workshop的多个报告涉及/用到BKZ算法(see the 2th and 7-10th talks of https://simons.berkeley.edu/workshops/schedule/10563 ; and the 6th, 9th and 10th talks of https://simons.berkeley.edu/workshops/schedule/10564 ),BKZ算法在格基密码邻域的流行性和重要性由此可见一斑。

Jianwei Li, Phong Q. Nguyen: A Complete Analysis of the BKZ Lattice Reduction Algorithm. https://eprint.iacr.org/2020/1237. 2020.