Scholarlink

<p>As a generalization of the shortest vector problem (SVP) in lattices, the <i>k</i>-dimensional densest sublattice problem (<i>k</i>-DSP) plays an important role in lattice theory. The hardness of <i>k</i>-DSP is at least that of SVP and there are lattices such that no solution to <i>k</i>-DSP contains the shortest lattice vector. As a result, it is not clear how to use the algorithms for SVP to solve <i>k</i>-DSP. Lattice reduction algorithms appear to be a feasible way to approximate <i>k</i>-DSP because they aim to output short and nearly orthogonal basis vectors. To take the first step toward understanding the approximation behavior of lattice reduction algorithms for solving <i>k</i>-DSP, we develop provable upper bounds on the approximation factors of Hermite–Korkine–Zolotarev (HKZ) reduction, blockwise Korkine–Zolotarev (BKZ) reduction, and Slide reduction. These bounds serve as a theoretical reference for assessing the potential of these reductions to approximate <i>k</i>-DSP. According to our analysis, the upper bound for HKZ reduction is smaller than that of BKZ reduction when the block size satisfies <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\beta \le n - k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo>≤</mo> <mi>n</mi> <mo>-</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>, and the two bounds coincide when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\beta \ge n - k + 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo>≥</mo> <mi>n</mi> <mo>-</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, where <i>n</i> denotes the lattice dimension. Furthermore, BKZ reduction achieves a smaller upper bound than Slide reduction. Our results also provide a positive answer to the question posed by Pataki et al., namely, whether the upper bounds for HKZ and BKZ reductions can be sharper than that of LLL reduction. At last, experiments are conducted to illustrate the theoretical results.</p>

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

On the ability to approximate k-DSP of HKZ, BKZ and Slide reduction

  • 期刊论文

  • 发表日期：

    2026年2月4日

查看全文
  • Kang Li,
  • Shancheng Zhao,
  • Jie Chen,
  • Jinming Wen

摘要

As a generalization of the shortest vector problem (SVP) in lattices, the k-dimensional densest sublattice problem (k-DSP) plays an important role in lattice theory. The hardness of k-DSP is at least that of SVP and there are lattices such that no solution to k-DSP contains the shortest lattice vector. As a result, it is not clear how to use the algorithms for SVP to solve k-DSP. Lattice reduction algorithms appear to be a feasible way to approximate k-DSP because they aim to output short and nearly orthogonal basis vectors. To take the first step toward understanding the approximation behavior of lattice reduction algorithms for solving k-DSP, we develop provable upper bounds on the approximation factors of Hermite–Korkine–Zolotarev (HKZ) reduction, blockwise Korkine–Zolotarev (BKZ) reduction, and Slide reduction. These bounds serve as a theoretical reference for assessing the potential of these reductions to approximate k-DSP. According to our analysis, the upper bound for HKZ reduction is smaller than that of BKZ reduction when the block size satisfies \(\beta \le n - k\) β ≤ n - k , and the two bounds coincide when \(\beta \ge n - k + 1\) β ≥ n - k + 1 , where n denotes the lattice dimension. Furthermore, BKZ reduction achieves a smaller upper bound than Slide reduction. Our results also provide a positive answer to the question posed by Pataki et al., namely, whether the upper bounds for HKZ and BKZ reductions can be sharper than that of LLL reduction. At last, experiments are conducted to illustrate the theoretical results.