TY - GEN
T1 - Explicit formula for gram-schmidt vectors in LLL with deep insertions and its applications
AU - Yamaguchi, Junpei
AU - Yasuda, Masaya
N1 - Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - Lattice basis reduction algorithms have been used as a strong tool for cryptanalysis. The most famous one is LLL, and its typical improvements are BKZ and LLL with deep insertions (DeepLLL). In LLL and DeepLLL, at every time to replace a lattice basis, we need to recompute the Gram-Schmidt orthogonalization (GSO) for the new basis. Compared with LLL, the form of the new GSO vectors is complicated in DeepLLL, and no formula has been known. In this paper, we give an explicit formula for GSO in DeepLLL, and also propose an efficient method to update GSO in DeepLLL. As another work, we embed DeepLLL into BKZ as a subroutine instead of LLL, which we call “DeepBKZ”, in order to find a more reduced basis. By using our DeepBKZ with blocksizes up to β = 50, we have found a number of new solutions for the Darmstadt SVP challenge in dimensions from 102 to 123.
AB - Lattice basis reduction algorithms have been used as a strong tool for cryptanalysis. The most famous one is LLL, and its typical improvements are BKZ and LLL with deep insertions (DeepLLL). In LLL and DeepLLL, at every time to replace a lattice basis, we need to recompute the Gram-Schmidt orthogonalization (GSO) for the new basis. Compared with LLL, the form of the new GSO vectors is complicated in DeepLLL, and no formula has been known. In this paper, we give an explicit formula for GSO in DeepLLL, and also propose an efficient method to update GSO in DeepLLL. As another work, we embed DeepLLL into BKZ as a subroutine instead of LLL, which we call “DeepBKZ”, in order to find a more reduced basis. By using our DeepBKZ with blocksizes up to β = 50, we have found a number of new solutions for the Darmstadt SVP challenge in dimensions from 102 to 123.
KW - LLL with deep insertions
KW - Lattice basis reduction
KW - Shortest vector problem (SVP)
UR - https://www.scopus.com/pages/publications/85044083062
UR - https://www.scopus.com/pages/publications/85044083062#tab=citedBy
U2 - 10.1007/978-3-319-76620-1_9
DO - 10.1007/978-3-319-76620-1_9
M3 - Conference contribution
AN - SCOPUS:85044083062
SN - 9783319766195
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 142
EP - 160
BT - Number-Theoretic Methods in Cryptology - 1st International Conference, NuTMiC 2017, Revised Selected Papers
A2 - Pieprzyk, Josef
A2 - Pieprzyk, Josef
A2 - Kaczorowski, Jerzy
A2 - Pomykała, Jacek
PB - Springer Verlag
T2 - 1st International Conference on Number-Theoretic Methods in Cryptology, NuTMiC 2017
Y2 - 11 September 2017 through 13 September 2017
ER -