TY - JOUR

T1 - New orthogonality criterion for shortest vector of lattices and its applications

AU - Lee, Hyang Sook

AU - Lim, Seongan

AU - Song, Kyunghwan

AU - Yie, Ikkwon

N1 - Funding Information:
Hyang-Sook Lee was supported by the National Research Foundation of Korea grant funded by the Korea government (Grant Number: NRF-2018R1A2A1A05079095 ). Seongan Lim was supported by the National Research Foundation of Korea grant funded by the Korea government (Grant Number: NRF-2016R1D1A1B01008562 ). Kyunghwan Song was supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education (Grant Number: NRF-2019R1A6A1A11051177 ). Ikkwon Yie was supported by the National Research Foundation of Korea grant funded by the Korea government (Grant Number: NRF-2017R1D1A1B03034721 ).
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2020/9/15

Y1 - 2020/9/15

N2 - The security of most lattice based cryptography relies on the hardness of computing a shortest nonzero vector of lattices. We say that a lattice basis is SV-reduced if it contains a shortest nonzero vector of the lattice. In this paper, we prove that, π∕6 orthogonality between the shortest vector of the basis and the vector space spanned by other vectors of the basis is enough to be SV-reduced under the assumption that a plausible condition Cn holds. By using the π∕6 orthogonality under C2, we prove a new complexity bound log3[Formula presented]+1 for Gauss–Lagrange algorithm which clarifies why the currently known complexity is so far fall short to expose the efficiency of the algorithm we experience in practice. Our experiments suggest that our complexity bound of Gauss–Lagrange algorithm is somewhat close to actual efficiency of the algorithm. We also show that LLL(δ) algorithm outputs a SV-reduced basis if δ≥1∕3 for two dimensional lattice. We present an efficient three dimensional SV-reduction algorithm by using the condition C3 and π∕6 orthogonality and how to generalize the algorithm for higher dimension.

AB - The security of most lattice based cryptography relies on the hardness of computing a shortest nonzero vector of lattices. We say that a lattice basis is SV-reduced if it contains a shortest nonzero vector of the lattice. In this paper, we prove that, π∕6 orthogonality between the shortest vector of the basis and the vector space spanned by other vectors of the basis is enough to be SV-reduced under the assumption that a plausible condition Cn holds. By using the π∕6 orthogonality under C2, we prove a new complexity bound log3[Formula presented]+1 for Gauss–Lagrange algorithm which clarifies why the currently known complexity is so far fall short to expose the efficiency of the algorithm we experience in practice. Our experiments suggest that our complexity bound of Gauss–Lagrange algorithm is somewhat close to actual efficiency of the algorithm. We also show that LLL(δ) algorithm outputs a SV-reduced basis if δ≥1∕3 for two dimensional lattice. We present an efficient three dimensional SV-reduction algorithm by using the condition C3 and π∕6 orthogonality and how to generalize the algorithm for higher dimension.

KW - Lattice

KW - Orthogonality of basis

KW - Shortest vector problem

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

U2 - 10.1016/j.dam.2020.01.023

DO - 10.1016/j.dam.2020.01.023

M3 - Article

AN - SCOPUS:85079176638

SN - 0166-218X

VL - 283

SP - 323

EP - 335

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -