TY - JOUR
T1 - Analysis of DeepBKZ reduction for finding short lattice vectors
AU - Yasuda, Masaya
AU - Nakamura, Satoshi
AU - Yamaguchi, Junpei
N1 - Funding Information:
This work was supported by JST CREST Grant Number JPMJCR14D6, Japan. A part of this work was also supported by JSPS KAKENHI Grant Number JP16H02830.
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/10/1
Y1 - 2020/10/1
N2 - Lattice basis reduction is a mandatory tool for solving lattice problems such as the shortest vector problem. The Lenstra–Lenstra–Lovász reduction algorithm (LLL) is the most famous, and its typical improvements are the block Korkine–Zolotarev algorithm and LLL with deep insertions (DeepLLL), both proposed by Schnorr and Euchner. In BKZ with blocksize β, LLL is called many times to reduce a lattice basis before enumeration to find a shortest non-zero vector in every block lattice of dimension β. Recently, “DeepBKZ” was proposed as a mathematical improvement of BKZ, in which DeepLLL is called as a subroutine alternative to LLL. In this paper, we analyze the output quality of DeepBKZ in both theory and practice. Specifically, we give provable upper bounds specific to DeepBKZ. We also develop “DeepBKZ 2.0”, an improvement of DeepBKZ like BKZ 2.0, and show experimental results that it finds shorter lattice vectors than BKZ 2.0 in practice.
AB - Lattice basis reduction is a mandatory tool for solving lattice problems such as the shortest vector problem. The Lenstra–Lenstra–Lovász reduction algorithm (LLL) is the most famous, and its typical improvements are the block Korkine–Zolotarev algorithm and LLL with deep insertions (DeepLLL), both proposed by Schnorr and Euchner. In BKZ with blocksize β, LLL is called many times to reduce a lattice basis before enumeration to find a shortest non-zero vector in every block lattice of dimension β. Recently, “DeepBKZ” was proposed as a mathematical improvement of BKZ, in which DeepLLL is called as a subroutine alternative to LLL. In this paper, we analyze the output quality of DeepBKZ in both theory and practice. Specifically, we give provable upper bounds specific to DeepBKZ. We also develop “DeepBKZ 2.0”, an improvement of DeepBKZ like BKZ 2.0, and show experimental results that it finds shorter lattice vectors than BKZ 2.0 in practice.
UR - http://www.scopus.com/inward/record.url?scp=85085976387&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85085976387&partnerID=8YFLogxK
U2 - 10.1007/s10623-020-00765-4
DO - 10.1007/s10623-020-00765-4
M3 - Article
AN - SCOPUS:85085976387
SN - 0925-1022
VL - 88
SP - 2077
EP - 2100
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 10
ER -