时 间: 2011年7月6日（周三）上午9:00

地 点: 清华大学高等研究院 科学馆322报告厅

题 目: Lower bounds of shortest vector lengths in random NTRU lattices

报 告 人: Qi Cheng (University of Oklahoma)

报告摘要: Finding the shortest vector of a lattice is one of the most important problems in computational lattice theory. For a random lattice, one can estimate the length of the shortest vector using the Gaussian heuristic. However, no rigorous proof can be provided for some classes of lattices, as the Gaussian heuristic may not hold for them. In the talk, we prove that for a random NTRU lattice, with an overwhelming probability, the ratio between the length of the shortest vector and the length of the target vector, which corresponds to the secret key, is at least a constant, independent of the rank of the lattice. The main technique we use is the incompressibility method from the theory of Kolmogorov complexity.

This is a joint work with Jingguo Bi from Shandong University.