Self-dual DeepBKZ for finding short lattice vectors

Journal of mathematical cryptology

article

Masaya Yasuda¹ 

[1] Institute of Mathematics for Industry, Kyushu University

关键词: Lattice basis reduction;    SVP;    BKZ;    DeepLLL;   

DOI  :  10.1515/jmc-2015-0053

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

In recent years, the block Korkine-Zolotarev (BKZ) and its variants such as BKZ 2.0 have been used as de facto algorithms to estimate the security of a lattice-based cryptosystem. In 2017, DeepBKZ was proposed as a mathematical improvement of BKZ, which calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. DeepBKZ can find a short lattice vector by smaller blocksizes than BKZ. In this paper, we develop a self-dual variant of DeepBKZ, as in the work of Micciancio and Walter for self-dual BKZ. Like DeepBKZ, our self-dual DeepBKZ calls both DeepLLL and its dual variant as main subroutines in order to accelerate to find a very short lattice vector. We also report experimental results of DeepBKZ and our self-dual DeepBKZ for random bases on the Darmstadt SVP challenge.

【 授权许可】

CC BY|CC BY-NC-ND