TY - JOUR

T1 - Minimal condition for shortest vectors in lattices of low dimension

AU - Lee, Juhee

AU - Chang, Seunghwan

AU - Kim, Taewan

AU - Lee, Hyang Sook

AU - Lim, Seongan

N1 - Funding Information:
Hyang-Sook Lee and Seongan Lim were supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (NRF-2018R1A2A1A05079095). Seunghwan Chang was supported by the Ministry of Science, ICT and Future Planning (NRF-2013R1A1A2062121). Taewan Kim was supported by the Ministry of Science, ICT and Future Planning (NRF-2013R1A1A2063279). Juhee Lee was supported by the Ministry of Science, ICT and Future Planning (NRF-2016R1A6A3A11933335).
Publisher Copyright:
© 2019 Elsevier B.V.

PY - 2019/3

Y1 - 2019/3

N2 - For a lattice, finding a nonzero shortest vector is computationally difficult in general. The problem becomes quite complicated even when the dimension of the lattice is five. There are two related notions of reduced bases, say, Minkowski-reduced basis and greedy-reduced basis. When the dimension becomes d = 5, there are greedy-reduced bases without achieving the first minimum while any Minkowski-reduced basis contains the shortest four linearly independent vectors. This suggests that the notion of Minkowski-reduced basis is somewhat strong and the notion of greedy-reduced basis is too weak for a basis to achieve the first minimum of the lattice. In this work, we investigate a more appropriate condition for a basis to achieve the first minimum for d = 5. We present a minimal sufficient condition, APG + , for a five dimensional lattice basis to achieve the first minimum in the sense that any proper subset of the required inequalities is not sufficient to achieve the first minimum.

AB - For a lattice, finding a nonzero shortest vector is computationally difficult in general. The problem becomes quite complicated even when the dimension of the lattice is five. There are two related notions of reduced bases, say, Minkowski-reduced basis and greedy-reduced basis. When the dimension becomes d = 5, there are greedy-reduced bases without achieving the first minimum while any Minkowski-reduced basis contains the shortest four linearly independent vectors. This suggests that the notion of Minkowski-reduced basis is somewhat strong and the notion of greedy-reduced basis is too weak for a basis to achieve the first minimum of the lattice. In this work, we investigate a more appropriate condition for a basis to achieve the first minimum for d = 5. We present a minimal sufficient condition, APG + , for a five dimensional lattice basis to achieve the first minimum in the sense that any proper subset of the required inequalities is not sufficient to achieve the first minimum.

KW - greedy-reduced basis

KW - lattice

KW - Minkowski-reduced basis

KW - shortest vector problem

UR - http://www.scopus.com/inward/record.url?scp=85063104223&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2019.02.002

DO - 10.1016/j.endm.2019.02.002

M3 - Article

AN - SCOPUS:85063104223

SN - 1571-0653

VL - 71

SP - 9

EP - 14

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -