Academic Journals Database
Disseminating quality controlled scientific knowledge

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

Author(s): Masaharu Fukase | Kazunori Yamaguchi

Journal: Journal of Systemics, Cybernetics and Informatics
ISSN 1690-4532

Volume: 9;
Issue: 6;
Start page: 42;
Date: 2011;
Original page

Keywords: Extended Search Space | Shortest Vector | 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.
Why do you need a reservation system?      Affiliate Program