Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions

Satoshi Nakamura, Yasuhiko Ikematsu, Masaya Yasuda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


Lattice basis reduction is a mandatory tool to solve lattice problems such as the shortest vector problem (SVP), whose hardness assures the security of lattice-based cryptography. The most famous reduction is the celebrated algorithm by Lenstra-Lenstra–Lovász (LLL), and the block Korkine–Zolotarev (BKZ) is its blockwise generalization. At present, BKZ and its variants such as BKZ 2.0 are a de facto standard reduction algorithm to estimate the security level of lattice-based cryptosystems. Recently, DeepBKZ was proposed as a mathematical improvement of BKZ, in which LLL with deep insertions (DeepLLL) is called as a subroutine alternative to LLL. In this paper, we develop a new self-dual variant of DeepBKZ to obtain a reduced basis. Different from conventional self-dual algorithms, we select suitable free dimensions to reduce primal and dual lattice bases in our variant. We also report experimental results to compare our self-dual DeepBKZ with primal BKZ and DeepBKZ for several random lattice bases.

Original languageEnglish
Title of host publicationProceedings of the Sixth International Conference on Mathematics and Computing - ICMC 2020
EditorsDebasis Giri, Rajkumar Buyya, S. Ponnusamy, Debashis De, Andrew Adamatzky, Jemal H. Abawajy
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages15
ISBN (Print)9789811580604
Publication statusPublished - 2021
Event6th International Conference on Mathematics and Computing, ICMC 2020 - Sikkim, India
Duration: Sept 23 2020Sept 25 2020

Publication series

NameAdvances in Intelligent Systems and Computing
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365


Conference6th International Conference on Mathematics and Computing, ICMC 2020

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • General Computer Science


Dive into the research topics of 'Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions'. Together they form a unique fingerprint.

Cite this