Analysis of the Extended Search Space for the Shortest Vector in Lattice

Lattice reduction algorithms have been used for crypt-analysis of many public key cryptosystems. Several lattice reduction algorithms have been proposed in the literature while the most popular among them is the BKZ algorithm. When BKZ fails to find a shortest vector, typically it returns a much longer vector than the shortest. We proposed the extended search space to find a shortest vector in such a case in our previous paper and confirmed the effectiveness of it experimentally. In this paper, we justify the effectiveness of the extended search space by additional analysis. For that, we analyzed coefficients of the shortest vector in a lattice based on some heuristic assumptions. Moreover, we examined the distribution of the coefficients that highly affect the inclusion probability in the extended search space. We showed that the inclusion probability can be estimated based on the distribution, and the estimated probability reflected the experimental results in our previous paper