任意范数格基分段规约

Lattice basis segment reduction for arbitrary norms

目前常见的格基规约理论主要集中在欧几里德范数上,涉及到任意范数的不多.本文把Koy等人提出的分段LLL规约推广到任意范数上.给出了任意范数分段规约基的定义,讨论了规约基的界并给出相应证明.设计了求解任意范数分段规约基的SR算法,算法具有维数n的多项式时间复杂度.最后把SR应用到NTRU格上,使用并行处理得到更高效的适用于高维格的PSR算法.实验结果表明,PSR算法在运行时间上比SR算法快2倍以上.

The known lattice basis reduction concepts and algorithms are mainly based on the Euclidean norm, rarely based on arbitrary norms. The concept of Koy＇s segment LLL-reduction is generalized from Euclidean norm to arbitrary norms. The definition of segment reduction for arbitrary norms is presented. Bounds for the quality of segment reduction bases are proved and SR algorithm to construct the reduction basis efficiently is given. SR algorithm executes in a polynomial number time of lattice rank n. At last, a parallel algorithm PSR for high rank lattice reduction is designed. Experiments on NTRU lattices show that PSR is at least twice as effective as SR.