Scholarlink

<p>The block Korkine–Zolotarev (BKZ) algorithm is a strong reduction algorithm for solving lattice problems such as the shortest vector problem (SVP) and the closest vector problem (CVP). For a large blocksize <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation>, the BKZ algorithm requires many calls to an exact-SVP algorithm over a local projected block lattice of rank <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation>, and thus in practice it is customary to terminate the reduction process prematurely. In this paper, we propose a new BKZ-type algorithm with provable termination. We name it “PotBKZ" since we use the potential of a lattice basis. Specifically, we develop “PotENUM", an enumeration algorithm to find lattice vectors whose insertion can reduce the potential. In PotBKZ, we call PotENUM instead of an exact-SVP algorithm to reduce the potential <i>monotonically</i>. We prove that PotBKZ terminates in a polynomial number of calls to PotENUM. Furthermore, we develop a self-dual variant of PotBKZ to reduce the potential more effectively with provable termination.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A new BKZ-type reduction with provable termination and development of its self-dual variant

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月11日

查看全文
  • Arata Sato,
  • Masaya Yasuda

摘要

The block Korkine–Zolotarev (BKZ) algorithm is a strong reduction algorithm for solving lattice problems such as the shortest vector problem (SVP) and the closest vector problem (CVP). For a large blocksize \(\beta \) β , the BKZ algorithm requires many calls to an exact-SVP algorithm over a local projected block lattice of rank \(\beta \) β , and thus in practice it is customary to terminate the reduction process prematurely. In this paper, we propose a new BKZ-type algorithm with provable termination. We name it “PotBKZ" since we use the potential of a lattice basis. Specifically, we develop “PotENUM", an enumeration algorithm to find lattice vectors whose insertion can reduce the potential. In PotBKZ, we call PotENUM instead of an exact-SVP algorithm to reduce the potential monotonically. We prove that PotBKZ terminates in a polynomial number of calls to PotENUM. Furthermore, we develop a self-dual variant of PotBKZ to reduce the potential more effectively with provable termination.