Paper 2016/439

A Measure Version of Gaussian Heuristic

Hao Chen

Abstract

Most applicable lattice reduction algorithms used in practice are BKZ (Block-Korkine-Zolotarev) type algorithms as the blockwise generalizations of the LLL algorithm (Lenstra-Lenstra-Lovasz). Its original version was proposed by Schnorr and Euchner in 1991. The quality of reduced lattice bases is measured by the Hermitian factor $\frac{||{\bf b}_1||}{vol({\bf L})^{1/d}}$ and the $d$-th root of this factor which is called root Hermitian factor. In Asiacrypt 2011 paper Y. Chen and Phong Q. Nguyen used BKZ with extreme pruning enumeration subroutine to handle the large block size lattice reduction with the purpose that the better root Hermitian factors can be expected. This BKZ 2.0 algorithm has been served as a base stone for the security evaluation of recent lattice-based cryptosystems such as fully homomorphic encryption and cryptographic multilinear mappings. In this paper we propose a measure version of Gaussian heuristic. This is a strict mathematical proven theorem. It can be used to give a strict mathematical proof for conjectured or simulated root Hermitian factors in BKZ 2.0 type algorithms and BKZ or slide reduction with large block-sizes. The theoretical analysis of these heuristic assumptions in the simulator of BKZ 2.0 type algorithms are also given.