Katsuya Nakashima
The modern internet and cloud services involve the exchange of various types of sensitive information. The foundational technology for maintaining the confidentiality of this information is cryptography, which includes public-key cryptography, symmetric-key cryptography, and digital signatures. Among these, cryptographic algorithms based on the difficulty of factoring large numbers and the discrete logarithm problem (such as DSA) are widely used in public-key cryptography and digital signatures. Recently, the advancement of quantum computing, which can efficiently solve these problems, poses a threat to the security of cryptographic technologies. As a result, research, development, and standardization of various quantum-resistant cryptographic technologies are underway. Among these, lattice-based cryptography is notable for its wide applicability and high security. However, to evaluate the practical application security of this new cryptographic technology, research on efficient attack algorithms against lattices is essential. The security of lattice cryptography is based on the difficulty of the Shortest Vector Problem (SVP), which involves finding the shortest non-zero vector in a lattice. Various lattice basis reduction algorithms have been proposed for SVP, with representative algorithms including the LLL (Lenstra-Lenstra-Lovasz) reduction algorithm and the BKZ (block Korkin-Zolotarev) reduction algorithm. Among these, the BKZ reduction algorithm is considered the most powerful, disregarding computational complexity. The computational cost of the BKZ algorithm largely depends on the ENUM algorithm, a subroutine for enumerating lattice points. In this study, we improved the mechanism proposed by Yamamura et al. at SCIS 2021 for reducing the computational cost of ENUM by changing the order of the input basis. Specifically, we analyzed the impact of repeated updates to the input basis on ENUM and applied this approach to various variations of the BKZ algorithm to examine its effectiveness.
Keyword: lattice based cryptography, BKZ, basis reordering
