Numerous algorithms for solving the Shortest Vector Problem (SVP) have been proposed, with the General Sieve Kernel (G6K) currently recognized for its high performance. However, its exponential time and space complexity impose substantial limitations in high-dimensional settings. In this work, we introduce a novel SVP solver, termed ENUM-Sieve Reduction (ESR), which integrates enumeration algorithm (ENUM) and G6K-based sieving algorithm. ESR is designed to improve lattice basis quality by exploiting both CPU and GPU resources in parallel. Experimental evaluations demonstrate that ESR outputs vectors with norms less than or equal to those produced by G6K in 87.5% of cases for dimensions ranging from 96 to 130. Moreover, ESR exhibits comparable trends in memory and time consumption to G6K, offering a practical alternative for high-dimensional ideal lattices.

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

Proposal of An SVP Solver on Prime Cyclotomic Lattices

  • Kazutaka Toda,
  • Yuntao Wang

摘要

Numerous algorithms for solving the Shortest Vector Problem (SVP) have been proposed, with the General Sieve Kernel (G6K) currently recognized for its high performance. However, its exponential time and space complexity impose substantial limitations in high-dimensional settings. In this work, we introduce a novel SVP solver, termed ENUM-Sieve Reduction (ESR), which integrates enumeration algorithm (ENUM) and G6K-based sieving algorithm. ESR is designed to improve lattice basis quality by exploiting both CPU and GPU resources in parallel. Experimental evaluations demonstrate that ESR outputs vectors with norms less than or equal to those produced by G6K in 87.5% of cases for dimensions ranging from 96 to 130. Moreover, ESR exhibits comparable trends in memory and time consumption to G6K, offering a practical alternative for high-dimensional ideal lattices.